On approximating the stationary distribution of time-reversible Markov chains

Abstract

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require $\tilde{O}(\tau /\pi (v))$ operations to approximate the probability $\pi (v)$ of a state $v$ in a chain with mixing time $\tau$, and even the best available techniques still have complexity $\tilde{O}({\tau }^{1.5}/\pi (v{)}^{0.5})$, and since these complexities depend inversely on $\pi (v)$, they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-$\pi (v)$ barrier".

Full version of a paper accepted at STACS 2018. 18 pages, 1 figure