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

The time is a random variable, and we can define a new stochastic process , depending on , , and , by

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.

### Like this:

Like Loading...

*Related*

## About Vaughn Climenhaga

I'm an assistant professor of mathematics at the University of Houston. I'm interested in dynamical systems, ergodic theory, thermodynamic formalism, dimension theory, multifractal analysis, non-uniform hyperbolicity, and things along those lines.