Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems

Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We begin by observing that (discrete-time) Quasi-Birth-Death Processes (QBDs) are equivalent, in a precise sense, to (discrete-time) probabilistic 1-Counter Automata (p1CAs), and both Tree-Like QBDs (TL-QBDs) and Tree-Structured QBDs (TS-QBDs) 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 null-recurrent one), we can approximate its termination probabilities (i.e., its G matrix) to within i bits of precision (i.e., within additive error 1/2i), in time polynomial in both the encoding size of the QBD and in i, in the unit-cost 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 well-known "linear/quadratic convergence" of numerical analysis, known for QBDs and TL-QBDs, 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 TL-QBDs this bound fails badly. Specifically, in the worst case Newton's method "converges linearly" to the termination probabilities for TL-QBDs, but requires exponentially many iterations in the encoding size of the TL-QBD to approximate these probabilities within any non-trivial constant error c < 1. Our upper bound proof for QBDs combines several ingredients: a detailed analysis of the structure of 1-counter 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.
Original languageEnglish
Title of host publicationFifth International Conference on the Quantitative Evaluaiton of Systems (QEST 2008), 14-17 September 2008, Saint-Malo, France
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages11
ISBN (Print)978-0-7695-3360-5
Publication statusPublished - Sept 2008


Dive into the research topics of 'Quasi-Birth-Death Processes, Tree-Like QBDs, Probabilistic 1-Counter Automata, and Pushdown Systems'. Together they form a unique fingerprint.

Cite this