Publication details
Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Paper in proceedings |
| Conference | Principles of Verification: Cycling the Probabilistic Landscape : Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday |
| MU Faculty or unit | |
| Citation | |
| web | DOI |
| Doi | https://doi.org/10.1007/978-3-031-75783-9_4 |
| Keywords | probabilistic programs; expected runtime |
| Description | The computational complexity of a probabilistic program C is traditionally measured by the expected values of certain random variables defined over the runs of C. However, in some cases, this approach may lead to misleading conclusions about the actual runtime behavior of the program. Furthermore, the analysis of expected values is not compositional in general. In this paper, we propose alternative complexity measures for probabilistic programs that overcome some of these difficulties. |