The previous post introduced the idea of coupling for Markov chains as a method for estimating mixing times. Here we mention a particular example of a coupling that is often useful — this is the classical coupling, or Doeblin coupling, after Wolfgang Doeblin.
Let be a Markov chain with state space and transition probability matrix . As usual, assume that is irreducible and aperiodic, so that there is a unique stationary distribution , and let be the initial distribution of .
Let be another Markov chain over , with initial distribution . Let and evolve independently of each other, and consider the stopping time
Now the pair is a coupling of the Markov chain. Each of , evolves according to the transition probabilities in , but after time the pair lives on the diagonal of , and so in particular if we write for the distribution of , the general coupling bound from the previous post gives
This bound can be computed directly as follows: for any we have
where the third equality uses the fact (from the definition of ) that whenever .
Now suppose that instead of beginning in the stationary distribution , the Markov chain begins in another distribution . We would like to estimate the distance between the distributions and , which corresponds to memory loss in the Markov chain. If we define the hitting time by (1) and the coupling by (2), then the same argument gives
and so we see that coupling techniques also estimate the memory loss in the Markov chain.
We remark that it can be shown that for each , not only does the quantity converge to , but it does so monotonically.
Later on in this series, we will explore the connection between these techniques and smooth dynamics. For uniformly hyperbolic maps, Markov partitions can be used to connect the dynamics of a diffeomorphism to a finite-state Markov chain. For non-uniformly hyperbolic maps, the situation is more subtle and a countable-state Markov chain must be used — this will lead us to a discussion of Young towers and subexponential decay of correlations, for which coupling techniques can be used to get results even when spectral techniques fail because the transfer operator does not act with a spectral gap.