Let @math be a discrete time Markov chain on a general state space. It is well-known that if @math is aperiodic and satisfies a drift and minorization condition, then it converges to its stationary distribution @math at an exponential rate. We consider the problem of computing upper bounds for the distance from stationarity in terms of the drift and minorization data. Baxendale showed that these bounds improve significantly if one assumes that @math is reversible with nonnegative eigenvalues (i.e. its transition kernel is a self-adjoint operator on @math with spectrum contained in @math ). We identify this phenomenon as a special case of a general principle: for a reversible chain with nonnegative eigenvalues, any strong random time gives direct control over the convergence rate. We formulate this principle precisely and deduce from it a stronger version of Baxendale's result. Our approach is fully quantitative and allows us to convert drift and minorization data into explicit convergence bounds. We show that these bounds are tighter than those of Rosenthal and Baxendale when applied to a well-studied example.
The most important feature of Theorem and its @math -norm version, Theorem , is that the exponential rate @math is the same as the decay rate in Theorem . As we will see in Section , this conclusion can only be drawn for reversible Markov chains with nonnegative eigenvalues and does not hold in general. Baxendale @cite_11 was the first to observe this consequence of reversibility. For a key argument, he credits a comment of Meyn on a previous draft of @cite_11 . In the case @math , Theorem is very similar to [Theorem 1.3] B05 : both theorems have the same hypotheses, and both prove @math -norm convergence of the chain with the same exponential rate @math .
@cite_11
2122337269
We give computable bounds on the rate of convergence of the transition probabilities to the stationary distribution for a certain class of geometrically ergodic Markov chains. Our results are dierent from earlier estimates of Meyn and Tweedie, and from estimates using coupling, although we start from essentially the same assumptions of a drift condition towards a “small set”. The estimates show a noticeable improvement on existing results if the Markov chain is reversible with respect to its stationary distribution, and especially so if the chain is also positive. The method of proof uses the first-entrance last-exit decomposition, together with new quantitative versions of a result of Kendall from discrete renewal theory.