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

dc.contributor.advisor | Sanguinetti, Guido | en |

dc.contributor.advisor | Mayr, Richard | en |

dc.contributor.advisor | Etessami, Kousha | en |

dc.contributor.author | Stewart, Alistair Mark | en |

dc.date.accessioned | 2015-03-13T14:36:16Z | |

dc.date.available | 2015-03-13T14:36:16Z | |

dc.date.issued | 2015-06-29 | |

dc.identifier.uri | http://hdl.handle.net/1842/10001 | |

dc.description.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. | en |

dc.contributor.sponsor | Engineering and Physical Sciences Research Council (EPSRC) | en |

dc.language.iso | en | |

dc.publisher | The University of Edinburgh | en |

dc.relation.hasversion | Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis. Polynomial time algorithms for branching markov decision processes and probabilistic min(max) polynomial Bellman equations. ICALP, 2012. see full Arxiv version, http://arxiv.org/abs/1202.4798. | en |

dc.relation.hasversion | Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis. Polynomial time algorithms for multi-type branching processes and stochastic context-free grammars. STOC, 2012. see full Arxiv version, http://arxiv.org/abs/1201.2374. | en |

dc.relation.hasversion | K. Etessami, A. Stewart, and M. Yannakakis. Stochastic context-free grammars, regular languages, and newton’s method. In Proc. 40th Int. Coll. on Automata, Languages, and Programming (ICALP’13), pages 199–211, 2013. see full Arxiv version, http://arxiv.org/abs/1302.6411. | en |

dc.relation.hasversion | Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis. Upper bounds for Newton’s method on monotone polynomial systems, and Ptime model checking of probabilistic one-counter automata. CAV, 2013. | en |

dc.subject | Newton’s method | en |

dc.subject | Markov Decision Processes | en |

dc.subject | statistical natural language processing | en |

dc.subject | monotone polynomial equations | en |

dc.title | Efficient algorithms for infinite-state recursive stochastic models and Newton’s method | en |

dc.type | Thesis or Dissertation | en |

dc.type.qualificationlevel | Doctoral | en |

dc.type.qualificationname | PhD Doctor of Philosophy | en |