A polynomial time algorithm for computing extinction probabilities of multi-type branching processes

Kousha Etessami, A Sinclair, Mihalis Yannakakis

Research output: Contribution to journalArticlepeer-review

Abstract

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1=), where > 0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.) We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and well studied stochastic processes, including multi-type branching processes and stochastic context-free grammars.
Original languageEnglish
Pages (from-to)1515-1553
Number of pages38
JournalSIAM Journal on Scientific Computing
Volume46
Issue number5
Early online date26 Sep 2017
DOIs
Publication statusPublished - 26 Sep 2017

Fingerprint

Dive into the research topics of 'A polynomial time algorithm for computing extinction probabilities of multi-type branching processes'. Together they form a unique fingerprint.

Cite this