Coupling

A coupling is a stochastic process

$$ \{(X_n^{(1)}, X_n^{(2)})\}_{n \ge 0} $$

constructed on the joint state space $S \times S$ such that, for each $k \in \{1,2\}$, the marginal process

$$ \{X_n^{(k)}\} $$

is itself a Markov chain with transition matrix $P$.

The coupling time is defined by

$$ T = \inf\{n \ge 0 : X_n^{(1)} = X_n^{(2)}\}. $$

If after time $T$ the two chains move together, that is,

$$ X_{T+k}^{(1)} = X_{T+k}^{(2)}, \quad \forall k \ge 0, $$

then the total variation distance at time $n$ satisfies the coupling bound

$$ \sum_{j \in S} \left|p_{ij}^{(n)} - \pi_j\right| \le 2 \mathbb{P}(T > n). $$

So coupling converts convergence to stationarity into a bound on the probability that the two chains have not yet met by time $n$.