BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA and Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. Journal of Computer and System Sciences. Academic Press, 2015, vol. 81, No 1, p. 288-310. ISSN 0022-0000. Available from: https://dx.doi.org/10.1016/j.jcss.2014.06.005.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Runtime analysis of probabilistic programs with unbounded recursion
Authors BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Stefan KIEFER (276 Germany), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution) and Ivana HUTAŘOVÁ VAŘEKOVÁ (203 Czech Republic, belonging to the institution).
Edition Journal of Computer and System Sciences, Academic Press, 2015, 0022-0000.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
Impact factor Impact factor: 1.583
RIV identification code RIV/00216224:14330/15:00080655
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1016/j.jcss.2014.06.005
UT WoS 000342481400020
Keywords (in Czech) zásobníkové automaty; rekurze
Keywords in English pushdown automata; recursion
Tags formela-journal
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Changed: 29/1/2015 19:00.
Abstract
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.
Links
GBP202/12/G061, research and development projectName: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)
Investor: Czech Science Foundation
PrintDisplayed: 5/5/2024 07:18