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 method of proof in @cite_11 uses analytic properties of generating functions for renewal sequences. In principle the argument could be extended to the case @math , but the resulting bound on the exponential convergence rate of the chain would be worse than the rate @math from Theorem . Intuitively, this is because the law of @math might introduce artificial periodicity. Our approach using Theorem is probabilistic and puts all cases @math on the same footing.
@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.