Independent coupling constructs the joint chain

$$ \{(X_n^{(1)}, X_n^{(2)})\} $$

so that the two coordinates move independently at each step according to the same transition matrix $P$.

If $P$ has stationary measure $\pi$, then the stationary measure of the joint chain is the product measure

$$ \pi \otimes \pi. $$

Recurrence of the marginal chains does not imply recurrence of the independent joint chain. For example, if each marginal chain is a 2-D simple random walk, then the joint chain is a 4-D simple random walk, which is transient.


General coupling introduces dependence between

$$ X_n^{(1)} \quad \text{and} \quad X_n^{(2)} $$

to make the coupling time

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

as small as possible.

The total variation distance to stationarity is bounded by

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

Example: coordinate update on $\{0,1\}^N$

Construct the coupling so that both chains update the same coordinate with the same sampled value at each step. Then the coupling time $T$ is the first time by which every coordinate has been selected at least once.

Using the coupon collector tail bound,

$$ \mathbb{P}(T > n) \le N\left(1 - \frac{1}{N}\right)^n. $$

Therefore the convergence rate satisfies

$$ \sum_{j \in S} \left|p_{ij}^{(n)} - \pi_j\right| \le 2N\left(1 - \frac{1}{N}\right)^n. $$