Geometric bounds for eigenvalues of Markov chains (Q808102): Difference between revisions

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.