COMPUTABLE BOUNDS FOR GEOMETRIC CONVERGENCE RATES OF MARKOV CHAINS

Recent results for geometrically ergodic Markov chains show that there exist constants R < infinity, rho < 1 such that sup(vertical bar f vertical bar <= V) vertical bar integral P-n(x, dy)f(y) - integral pi(dy)f(y)vertical bar <= RV(x)rho(n), where pi is the invariant probability measure and V is any solution of the drift inequalities integral P(x, dy)V(y) <= lambda V(x) + b1(c)(x), which are known to guarantee geometric convergence for lambda < 1, b < infinity and a suitable small set C. In this paper we identify for the first time computable bounds on R and rho in terms of lambda, b and the minorizing constants which guarantee the smallness of C. In the simplest case where C is an atom a with P(alpha, alpha) >= delta we can choose any rho > nu, where [1- (sic)](-1) = 1/(1 - lambda)(2) [1 - lambda + b + b(2) + zeta(alpha)(b(1 - lambda) + b(2))] and zeta(alpha) <= (32 - 8 delta(2/)delta(3)) (b/1 - lambda)(2) and we can then choose R <= rho/(rho - nu) The bounds for general small sets C are similar but more complex. We apply these to simple queuing models and Markov chain Monte Carlo algorithms, although in the latter the bounds are clearly too large for practical application in the case considered.