Geometric bounds for eigenvalues of Markov chains. (English) Zbl 0731.60061

Consider an irreducible Markov chain with a finite state space x and denote by P(x,y), x,y\(\in X\), its transition probability. Assume that it has a stationary distribution \(\pi\) and P(x,y) is reversible with respect to \(\pi\). If so, as well-known, the Markov associated operator P is a self-adjoint contraction \(L^ 2(\pi)\), whose eigenvalues are \(1=\beta_ 0>\beta_ 1\geq...\geq \beta_{m-1}\geq -1\), where \(m=| X|\). The first aim of this paper is to develop methods for deriving bounds for \(\beta_ 1\), \(\beta_{m-1}\) and \(\beta_*=\max (\beta_ 1,| \beta_{m-1}|).\) The bounds depend on geometric quantities such as the maximum degree, diameter and covering number of associated graphs. Then simple examples (involving random walks on graphs) are given where the bounds are easily obtained and compared with the exact values. These examples seem to point out that the bounds obtained by the present authors are better than those derived through Cheeger-like inequalities. Finally, the bounds are used to get improved rates of convergence for a random walk associated with a problem of interest in theoretical computer science.


60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G50 Sums of independent random variables; random walks
60C05 Combinatorial probability
Full Text: DOI