Asymptotic Analysis of Probabilistic Programs : When
Expectations Do Not Meet Our Expectations

D 2025

Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations

AJDARÓW, Michal; Antonín KUČERA a Petr NOVOTNÝ

Základní údaje

Originální název

Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations

Autoři

AJDARÓW, Michal; Antonín KUČERA a Petr NOVOTNÝ

Vydání

Berlin, Germany, Principles of Verification: Cycling the Probabilistic Landscape : Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday, od s. 85-97, 13 s. 2025

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

DOI

Impakt faktor

Impact factor: 0.402 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00144015

Organizační jednotka

Fakulta informatiky

ISBN

978-3-031-75782-2

ISSN

DOI

https://doi.org/10.1007/978-3-031-75783-9_4

EID Scopus

2-s2.0-85212134802

Klíčová slova anglicky

probabilistic programs; expected runtime

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 4. 2026 11:17, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

AJDARÓW, Michal; Antonín KUČERA a Petr NOVOTNÝ. Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations. In Nils Jansen, Sebastian Junges, Benjamin Lucien Kaminski, Christoph Matheja, Thomas Noll, Tim Quatmann, Mariëlle Stoelinga, Matthias Volk. Principles of Verification: Cycling the Probabilistic Landscape : Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday. Berlin, Germany: Springer, 2025, s. 85-97. ISBN 978-3-031-75782-2. Dostupné z: https://doi.org/10.1007/978-3-031-75783-9_4.

@inproceedings{2561464,
   author = {Ajdarów, Michal and Kučera, Antonín and Novotný, Petr},
   address = {Berlin, Germany},
   booktitle = {Principles of Verification: Cycling the Probabilistic Landscape : Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday},
   doi = {https://doi.org/10.1007/978-3-031-75783-9_4},
   editor = {Nils Jansen, Sebastian Junges, Benjamin Lucien Kaminski, Christoph Matheja, Thomas Noll, Tim Quatmann, Mariëlle Stoelinga, Matthias Volk},
   keywords = {probabilistic programs; expected runtime},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin, Germany},
   isbn = {978-3-031-75782-2},
   pages = {85-97},
   publisher = {Springer},
   title = {Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations},
   url = {https://doi.org/10.1007/978-3-031-75783-9_4},
   year = {2025}
}

TY  - CONF
ID  - 2561464
AU  - Ajdarów, Michal - Kučera, Antonín - Novotný, Petr
PY  - 2025
TI  - Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations
PB  - Springer
CY  - Berlin, Germany
SN  - 9783031757822
KW  - probabilistic programs
KW  - expected runtime
UR  - https://doi.org/10.1007/978-3-031-75783-9_4
N2  - 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.
ER  -

AJDARÓW, Michal; Antonín KUČERA a Petr NOVOTNÝ. Asymptotic Analysis of Probabilistic Programs : When Expectations Do Not Meet Our Expectations. In Nils Jansen, Sebastian Junges, Benjamin Lucien Kaminski, Christoph Matheja, Thomas Noll, Tim Quatmann, Mari\"elle Stoelinga, Matthias Volk. \textit{Principles of Verification: Cycling the Probabilistic Landscape : Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday}. Berlin, Germany: Springer, 2025, s.~85-97. ISBN~978-3-031-75782-2. Dostupné z: https://doi.org/10.1007/978-3-031-75783-9\_{}4.

Přehled o publikaci