Runtime analysis of probabilistic programs with unbounded recursion

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Runtime analysis of probabilistic programs with unbounded recursion

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Runtime analysis of probabilistic programs with unbounded recursion

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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

Rok uplatnění

2015

Kód důvěrnosti údajů

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

Název periodika

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

81

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

23

Strana od-do

288-310

Kód UT WoS článku

000342481400020

EID výsledku v databázi Scopus

—