Další formáty:
BibTeX
LaTeX
RIS
@article{1219109,
author = {Brázdil, Tomáš and Kiefer, Stefan and Kučera, Antonín and Hutařová Vařeková, Ivana},
article_number = {1},
doi = {http://dx.doi.org/10.1016/j.jcss.2014.06.005},
keywords = {pushdown automata; recursion},
language = {eng},
issn = {0022-0000},
journal = {Journal of Computer and System Sciences},
title = {Runtime analysis of probabilistic programs with unbounded recursion},
volume = {81},
year = {2015}
}
TY - JOUR
ID - 1219109
AU - Brázdil, Tomáš - Kiefer, Stefan - Kučera, Antonín - Hutařová Vařeková, Ivana
PY - 2015
TI - Runtime analysis of probabilistic programs with unbounded recursion
JF - Journal of Computer and System Sciences
VL - 81
IS - 1
SP - 288-310
EP - 288-310
PB - Academic Press
SN - 00220000
KW - pushdown automata
KW - recursion
N2 - We study the runtime in probabilistic programs with unbounded recursion. As underlying formal model for such programs we use probabilistic pushdown automata (pPDAs) 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.
ER -
BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. \textit{Journal of Computer and System Sciences}. Academic Press, roč.~81, č.~1, s.~288-310. ISSN~0022-0000. doi:10.1016/j.jcss.2014.06.005. 2015.
|
