Runtime analysis of probabilistic programs with unbounded recursion

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00080655" target="_blank" >RIV/00216224:14330/15:00080655 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.jcss.2014.06.005" target="_blank" >http://dx.doi.org/10.1016/j.jcss.2014.06.005</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2014.06.005" target="_blank" >10.1016/j.jcss.2014.06.005</a>

Result language

angličtina

Original language name

Runtime analysis of probabilistic programs with unbounded recursion

Original language description

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 theprobability 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 areasymptotically tight. Our tail bounds on the runtime are generic, i.e., applicable to any probabilistic program with unbounded recursion.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2015

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Volume of the periodical

81

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

23

Pages from-to

288-310

UT code for WoS article

000342481400020

EID of the result in the Scopus database

—