Computing stationary distribution locally

Computing stationary probabilities of states in a large countable state space Markov Chain (MC) has become central to many modern scientific disciplines, whether in statistical inference problems, or in network analyses. Standard methods involve large matrix multiplications as in power iterations, or long simulations of random walks to sample states from the stationary distribution, as in Markov Chain Monte Carlo (MCMC). However, these approaches lack clear guarantees for convergence rates in the general setting. When the state space is prohibitively large, even algorithms that scale linearly in the size of the state space and require computation on behalf of every node in the state space are too expensive. In this thesis, we set out to address this outstanding challenge of computing the stationary probability of a given state in a Markov chain locally, efficiently, and with provable performance guarantees. We provide a novel algorithm, that answers whether a given state has stationary probability smaller or larger than a given value [delta] [epsilon] (0, 1). Our algorithm accesses only a local neighborhood of the given state of interest, with respect to the graph induced between states of the Markov chain through its transitions. The algorithm can be viewed as a truncated Monte Carlo method. We provide correctness and convergence rate guarantees for this method that highlight the dependence on the truncation threshold and the mixing properties of the graph. Simulation results complementing our theoretical guarantees suggest that this method is effective when our interest is in finding states with high stationary probability.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Lee, Christina (Christina Esther)

Advisor dc:contributor.advisor

• Asuman Ozdaglar and Devavrat Shah.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/82410

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/82410