NDLI: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations

Content Provider	ACM Digital Library
Author	Etessami, Kousha Yannakakis, Mihalis
Copyright Year	2009
Abstract	We define Recursive Markov Chains (RMCs), a class of finitely presented denumerable Markov chains, and we study algorithms for their analysis. Informally, an RMC consists of a collection of finite-state Markov chains with the ability to invoke each other in a potentially recursive manner. RMCs offer a natural abstract model for probabilistic programs with procedures. They generalize, in a precise sense, a number of well-studied stochastic models, including Stochastic Context-Free Grammars (SCFG) and Multi-Type Branching Processes (MT-BP). We focus on algorithms for $\textit{reachability}$ and $\textit{termination}$ analysis for RMCs: what is the probability that an RMC started from a given state reaches another target state, or that it terminates? These probabilities are in general irrational, and they arise as (least) fixed point solutions to certain (monotone) systems of nonlinear equations associated with RMCs. We address both the qualitative problem of determining whether the probabilities are 0, 1 or in-between, and the quantitative problems of comparing the probabilities with a given bound, or approximating them to desired precision. We show that all these problems can be solved in PSPACE using a decision procedure for the Existential Theory of Reals. We provide a more practical algorithm, based on a decomposed version of multi-variate Newton's method, and prove that it always converges monotonically to the desired probabilities. We show this method applies more generally to any monotone polynomial system. We obtain polynomial-time algorithms for various special subclasses of RMCs. Among these: for SCFGs and MT-BPs (equivalently, for $\textit{1-exit}$ RMCs) the qualitative problem can be solved in P-time; for linearly recursive RMCs the probabilities are rational and can be computed exactly in P-time. We show that our PSPACE upper bounds cannot be substantially improved without a breakthrough on long standing open problems: the square-root sum problem and an arithmetic circuit decision problem that captures P-time on the unit-cost rational arithmetic RAM model. We show that these problems reduce to the qualitative problem and to the approximation problem (to within any nontrivial error) for termination probabilities of general RMCs, and to the quantitative decision problem for termination (extinction) of SCFGs (MT-BPs).
Starting Page	1
Ending Page	66
Page Count	66
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1462153.1462154
Journal	Journal of the ACM (JACM)
Volume Number	56
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-02-03
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Newton's method Recursive Markov chains Monotone nonlinear systems Multi-type branching processes Stochastic context-free grammars
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Recursive Markov Decision Processes and Recursive Stochastic Games

Recursive Markov chains, stochastic grammars, and monotone systems of non-linear equations (2005)

Recursive Markov chains, stochastic grammars, and monotone systems of non-linear equations (2005)

Matrix Equations and Normal Forms for Context-Free Grammars

Indexed Grammars—An Extension of Context-Free Grammars

Linear and Context-Free Graph Grammars

Size complexity in context-free grammars forms

Simulating Stable Stochastic Systems, II: Markov Chains

TEG—a hybrid approach to information extraction

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations

Similar Documents

Recursive Markov Decision Processes and Recursive Stochastic Games

Recursive Markov chains, stochastic grammars, and monotone systems of non-linear equations (2005)

Recursive Markov chains, stochastic grammars, and monotone systems of non-linear equations (2005)

Matrix Equations and Normal Forms for Context-Free Grammars

Indexed Grammars—An Extension of Context-Free Grammars

Linear and Context-Free Graph Grammars

Size complexity in context-free grammars forms

Simulating Stable Stochastic Systems, II: Markov Chains

TEG—a hybrid approach to information extraction

Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations