BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA a Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. Journal of Computer and System Sciences. Academic Press, 2015, roč. 81, č. 1, s. 288-310. ISSN 0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2014.06.005. |
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, 2015, roč.~81, č.~1, s.~288-310. ISSN~0022-0000. Dostupné z: https://dx.doi.org/10.1016/j.jcss.2014.06.005.
|