Bounds on expected coupling times in Markov chains

Abstract

In the author’s paper “Coupling and Mixing Times in Markov Chains” (RLIMS, 11, 1- 22, 2007) it was shown that it is very difficult to find explicit expressions for the expected time to coupling in a general Markov chain. In this paper simple upper and lower bounds are given for the expected time to coupling in a discrete time finite Markov chain. Extensions to the bounds under additional restrictive conditions are also given with detailed comparisons provided for two and three state chains.