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.

[发布机构] Massachusetts Institute of Technology