 Abstract:
 We begin by observing that (discretetime) QuasiBirthDeath Processes (QBDs) are equivalent, in a precise sense, to (discretetime) probabilistic 1Counter Automata (p1CAs), and both TreeLike QBDs (TLQBDs) and TreeStructured QBDs (TSQBDs) are equivalent to both probabilistic Pushdown Systems (pPDSs) and Recursive Markov Chains (RMCs). We then proceed to exploit these connections to obtain a number of new algorithmic upper and lower bounds for central computational problems about these models. Our main result is this: for an arbitrary QBD (even a nullrecurrent one), we can approximate its termination probabilities (i.e., its G matrix) to within i bits of precision (i.e., within additive error 1/2^i), in time polynomial in both the encoding size of the QBD and in i, in the unitcost rational arithmetic RAM model of computation. Specifically, we show that a decomposed Newton's method can be used to achieve this. We emphasize that this bound is very different from the wellknown ``linear/quadratic convergence'' of numerical analysis, known for QBDs and TLQBDs, which typically gives no constructive bound in terms of the encoding size of the system being solved. In fact, we observe (based on recent results for pPDSs) that for the more general TLQBDs this bound fails badly. Specifically, in the worst case Newton's method ``converges linearly'' to the termination probabilities for TLQBDs, but requires exponentially many iterations in the encoding size of the TLQBD to approximate these probabilities within any nontrivial constant error c < 1. Our upper bound proof for QBDs combines several ingredients: a detailed analysis of the structure of 1counter automata, an iterative application of a classic condition number bound for errors in linear systems, and a very recent constructive bound on the performance of Newton's method for monotone systems of polynomial equations.
 Links To Paper
 1st Link
 Bibtex format
 @Misc{EDIINFRR1249,
 author = {
Kousha Etessami
and Dominik Wojtczak
and Mihalis Yannakakis
},
 title = {QuasiBirthDeath Processes, TreeLike QBDs, Probabilistic 1Counter Automata, and Pushdown Systems},
 year = 2008,
 url = {http://homepages.inf.ed.ac.uk/kousha/qbd_tree_1counter_pushdown.pdf},
 }
