Bounds on regeneration times and convergence rates for Markov chains

In many applications of Markov chains, and especially in Markov chain Monte Carlo algorithms, the rate of convergence of the chain is of critical impo rtance. Most techniques to establish such rates require bounds on the distr ibution of the random regeneration time T that can be constructed, via spli tting techniques, at times of return to a "small set" C satisfying a minori sation condition P(x, .) greater than or equal to epsilon phi(.), x is an e lement of C. Typically, however, it is much easier to get bounds on the tim e tau(C) of return to the small set itself, usually based on a geometric dr ift function PV less than or equal to lambda V + b1(C), where PV(x) = E-x(V (X-1)). We develop a new relationship between T and tau(C), and this gives a bound on the tail of T, based on epsilon, lambda and b, which is a strict improvement on existing results. When evaluating rates of convergence we s ee that our bound usually gives considerable numerical improvement on previ ous expressions. (C) 1999 Elsevier Science B.V. All rights reserved.