Runtime analysis of probabilistic programs with unbounded
recursion

J 2015

Runtime analysis of probabilistic programs with unbounded recursion

BRÁZDIL, Tomáš, Stefan KIEFER, Antonín KUČERA and Ivana HUTAŘOVÁ VAŘEKOVÁ

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

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

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

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

Abstract

V originále

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 project

Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation

Citovat

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.

@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 and Ivana HUTAŘOVÁ VAŘEKOVÁ. Runtime analysis of probabilistic programs with unbounded recursion. \textit{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.

Detailed Information on Publication Record