×

zbMATH — the first resource for mathematics

Computable bounds for geometric convergence rates of Markov chains. (English) Zbl 0812.60059
Summary: Recent results for geometrically ergodic Markov chains show that there exist constants \(R < \infty\), \(\rho < 1\) such that \[ \sup_{| f | \leq V} \Bigl | \int P^ n (x,dy) f(y) - \int \pi (dy) f(y) \Bigr | \leq RV(x) \rho^ n, \] where \(\pi\) is the invariant probability measure and \(V\) is any solution of the drift inequalities \[ \int P(x,dy) V(y) \leq \lambda V (x) + b \mathbf{1}_ C(x), \] which are known to guarantee geometric convergence for \(\lambda < 1\), \(b < \infty\) and a suitable small set \(C\). 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 \(\alpha\) with \(P (\alpha, \alpha) \geq \delta\) we can choose any \(\rho > \vartheta\), where \[ [1 - \vartheta]^{-1} = {1 \over (1 - \lambda)^ 2} \biggl[ 1 - \lambda + b + b^ 2 + \zeta_ \alpha \bigl( b(1-\lambda) + b^ 2 \bigr) \biggr] \] and \[ \zeta_ \alpha \leq \left( {32 - 8 \delta^ 2 \over \delta^ 3} \right) \left( {b \over 1-\lambda} \right)^ 2, \] and we can then choose \(R \leq \rho/(\rho - \vartheta)\). The bounds for general small sets \(C\) are similar but more complex. We apply these to simple queueing models and Markov chain Monte Carlo algorithms, although in the latter the bounds are clearly too large for practical application in the case considered.

MSC:
60J25 Continuous-time Markov processes on general state spaces
PDF BibTeX XML Cite
Full Text: DOI