## Efficient algorithms for infinite-state recursive stochastic models and Newton’s method

##### Abstract

Some well-studied infinite-state stochastic models give rise to systems of nonlinear
equations. These systems of equations have solutions that are probabilities, generally
probabilities of termination in the model. We are interested in finding efficient, preferably
polynomial time, algorithms for calculating probabilities associated with these
models. The chief tool we use to solve systems of polynomial equations will be Newton’s
method as suggested by [EY09]. The main contribution of this thesis is to the
analysis of this and related algorithms. We give polynomial-time algorithms for calculating
probabilities for broad classes of models for which none were known before.
Stochastic models that give rise to such systems of equations include such classic
and heavily-studied models as Multi-type Branching Processes, Stochastic Context-
Free Grammars(SCFGs) and Quasi Birth-Death Processes. We also consider models
that give rise to infinite-state Markov Decision Processes (MDPs) by giving algorithms
for approximating optimal probabilities and finding policies that give probabilities
close to the optimal probability, in several classes of infinite-state MDPs. Our
algorithms for analysing infinite-state MDPs rely on a non-trivial generalization of
Newton’s method that works for the max/min polynomial systems that arise as Bellman
optimality equations in these models. For SCFGs, which are used in statistical
natural language processing, in addition to approximating termination probabilities,
we analyse algorithms for approximating the probability that a grammar produces a
given string, or produces a string in a given regular language.
In most cases, we show that we can calculate an approximation to the relevant
probability in time polynomial in the size of the model and the number of bits of
desired precision.
We also consider more general systems of monotone polynomial equations. For
such systems we cannot give a polynomial-time algorithm, which pre-existing hardness
results render unlikely, but we can still give an algorithm with a complexity upper
bound which is exponential only in some parameters that are likely to be bounded for
the monotone polynomial equations that arise for many interesting stochastic models.