Reference:

Tomáš Brázdil, Stefan Kiefer, Antonín Kučera, and Ivana Hutařová Vařeková. Runtime analysis of probabilistic programs with unbounded recursion. In L. Aceto, M. Henzinger, and J. Sgall, editors, Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), volume 6756 of LNCS, pages 319–331, Zürich, Switzerland, 2011. Springer.

Abstract:

We study the runtime in probabilistic programs with unbounded recursion. As underlying formal model for such programs we use probabilistic pushdown automata (pPDA) which exactly correspond to recursive Markov chains. We show that every pPDA can be transformed into a stateless pPDA (called ``pBPA'') whose runtime and further properties are closely related to those of the original pPDA. This result substantially simplifies the analysis of runtime and other pPDA properties. We prove that for every pPDA the probability of performing a long run decreases exponentially in the length of the run, if and only if the expected runtime in the pPDA is finite. If the expectation is infinite, then the probability decreases ``polynomially''. We show that these bounds are asymptotically tight. Our tail bounds on the runtime are generic, i.e., applicable to any probabilistic program with unbounded recursion. An intuitive interpretation is that in pPDA the runtime is exponentially unlikely to deviate from its expected value.

Suggested BibTeX entry:

@inproceedings{BKKV:ICALP11,
    address = {Z\"{u}rich, Switzerland},
    author = {Tom\'{a}\v{s} Br\'{a}zdil and Stefan Kiefer and Anton\'{\i}n Ku\v{c}era and Ivana Huta\v{r}ov\'{a} Va\v{r}ekov\'{a}},
    booktitle = {Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP)},
    editor = {L. Aceto and M. Henzinger and J. Sgall},
    pages = {319--331},
    publisher = {Springer},
    series = {LNCS},
    title = {Runtime Analysis of Probabilistic Programs with Unbounded Recursion},
    volume = {6756},
    year = {2011}
}