14.1 Coupling

Consider a finite-state chain in discrete or continuous time. Fix states $i,j$. Suppose we construct a joint process $(X^{(i)}_{t},X^{(j)}_{t};t\geq 0)$ such that

And suppose there is a random time $T\leq\infty$ such that

Call such a $T$ a coupling time. Then the coupling inequality is

The inequality is clear once we observe $P(X_{t}^{(i)}\in\cdot,T\leq t)=P(X_{t}^{(j)}\in\cdot,T\leq t)$. The coupling inequality provides a method of bounding the variation distance $\bar{d}(t)$ of Chapter 2 section yyy.

The most common strategy for constructing a coupling satisfying (14.3) is via Markov couplings, as follows. Suppose the underlying chain has state space $I$ and (to take the continuous-time case) transition rate matrix ${\bf Q}=(q(i,j))$. Consider a transition rate matrix $\tilde{{\bf Q}}$ on the product space $I\times I$. Write the entries of $\tilde{{\bf Q}}$ as $\tilde{q}(i,j;k,l)$ instead of the logical-but-fussy $\tilde{q}((i,j),(k,l))$. Suppose that, for each pair $(i,j)$ with $j\neq i$,

in other words $\sum_{l}\tilde{q}(i,j;k,l)=q(i,k)$ and $\sum_{k}\tilde{q}(i,j;k,l)=q(j,l)$. And suppose that

Take $(X^{(i)}_{t},X^{(j)}_{t})$ to be the chain on $I\times I$ with transition rate matrix $\tilde{{\bf Q}}$ and initial position $(i,j)$, Then (14.3) must hold, and $T\equiv\min\{t:X^{(i)}_{t}=X^{(j)}_{t}\}$ is a coupling time. This construction gives a Markov coupling, and all the examples where we use the coupling inequality will be of this form. In practice it is much more understandable to define the joint process in words

xxx red and black particles.

A particular choice of $\tilde{{\bf Q}}$ is

in which case the joint process is called to Doeblin coupling. In words, the Doeblin coupling consists of starting one particle at $i$ and the other particle at $j$, and letting the two particles move independently until they meet, at time $M_{i,j}$ say, and thereafter letting them stick together. In the particular case of a birth-and-death process, the particles cannot cross without meeting (in continuous time), and so if $i<j$ then $X^{(i)}_{t}\leq X^{(j)}_{t}$ for all $t$, the property we used at (14.2).

Use of the coupling inequality has nothing to do with reversibility. In fact it finds more use in the irreversible setting, where fewer alternative methods are available for quantifying convergence to stationarity. In the reversible setting, coupling provides a quick way to get bounds which usually (but not always) can be improved by other methods. Here are two examples we have seen before.

For ${\bf i}=(i_{1},\ldots,i_{d})$ and ${\bf j}=(j_{1},\ldots,j_{d})$ in $I=\{0,1\}^{d}$, let $D({\bf i},{\bf j})$ be the set of coordinates $u$ where ${\bf i}$ and ${\bf j}$ differ. Write ${\bf i}^{u}$ for the state obtained by changing the $i$’th coordinate of ${\bf i}$. Recall that in continuous time the components move independently as $2$-state chains with transition rates $1/d$. In words, the coupling is “run unmatched coordinates independently until they match, and then run them together”. Formally, the non-zero transitions of the joint process are

For each coordinate which is initially unmatched, it takes exponential (rate $2/d$) time until it is matched, and so the coupling time $T$ satisfies

where the $(\xi_{u})$ are independent exponential (rate $2/d$) and $d_{0}=d({\bf i},{\bf j})$ is the initial number of unmatched coordinates. So

and the coupling inequality bounds variation distance as

This leads to an upper bound on the variation threshold time

In this example we saw in Chapter 5 that in fact

so the coupling bound is off by a factor of $2$.

Consider a $r$-regular $n$-vertex graph. Write $\mbox{${\cal N}$}(v)$ for the set of neighbors of $v$. For any pair $v,w$ we can define a $1-1$ map $\theta_{v,w}:\mbox{${\cal N}$}(v)\rightarrow\mbox{${\cal N}$}(w)$ such that $\theta_{v,w}(x)=x$ for $x\in\mbox{${\cal N}$}(v)\cap\mbox{${\cal N}$}(w)$. We can now define a “greedy coupling” by

In general one cannot get useful bounds on the coupling time $T$. But consider the dense case, where $r>n/2$. As observed in Chapter 5 Example yyy, here $|\mbox{${\cal N}$}(v)\cap\mbox{${\cal N}$}(w)|\geq 2r-n$ and so the coupled processes $(X_{t},Y_{t})$ have the property that for $w\neq v$

implying that $T$ satisfies

So the coupling inequality implies $\bar{d}(t)\leq\exp(-(2r-n)t/r)$, and in particular the variation threshold satisfies

We now give two examples of coupling in the wide sense, to compare different processes. The first is a technical result (inequality (14.8) below) which we needed in Chapter 6 yyy. The second is the proof of Proposition 14.1(b).

Let $(X_{t})$ be discrete-time random walk on a graph $G$, let $A$ be a subset of the vertices of $G$ and let $(Y_{t})$ be random walk on the subgraph induced by $A$. Given $B\subset A$, let $S$ be the first hitting time of $(Y_{t})$ on $B$, and let $T$ be the first hitting time of $(X_{t})$ on $B\cup A^{c}$. Then

This is “obvious”, and the reason it’s obvious is by coupling. We can construct coupled processes $(X^{\prime},Y^{\prime})$ with the property that, if both particles are at the same position $a$ in $A$, and if $X$ jumps to another state $b$ in $A$, then $Y$ jumps to the same state $b$. This property immediately implies that, for the coupled processes started at the same state in $A$, we have $T^{\prime}\leq S^{\prime}$ and hence (14.8).

In words, here is the coupling $(X^{\prime},Y^{\prime})$. When the particles are at different positions they jump independently. When they are at the same position, first let $X^{\prime}$ jump; if $X^{\prime}$ jumps to a vertex in $A$ let $Y^{\prime}$ jump to the same vertex, and otherwise let $Y^{\prime}$ jump to a uniform random neighbor in $A$. Formally, the coupled process moves according to the transition matrix $\tilde{{\bf P}}$ on $G\times A$ defined by

where $p_{A}$ and $p_{G}$ refer to transition probabilities for the original random walks on $A$ and $G$.

Proof of Proposition 14.1(b). Fix $i\geq 1$. By reversibility it is sufficient to prove

Consider the Doeblin coupling $(X^{(0)}_{t},X^{(i)}_{t})$ of the processes started at $0$ and at $i$, with coupling time $T$. Since $X^{(0)}_{t}\leq X^{(i)}_{t}$ we have

and so we have to prove

It suffices to show that, for $t_{1}>t$,

and thus, by considering the conditional distribution of $X^{(0)}_{t}$ given $X^{(0)}_{t_{1}}=0$, it suffices to show that

for $j\geq 0$. So fix $j$ and $t$. Write $(X^{(0,j)}_{s},0\leq s\leq t)$ for the process conditioned on $X_{0}=0,X_{t}=j$. By considering time running backwards from $t$ to $0$, the processes $X^{(0,0)}$ and $X^{(0,j)}$ are the same non-homogeneous Markov chain started at the different states $0$ and $j$, and we can use the Doeblin coupling in this non-homogeneous setting to construct versions of these processes with

Now introduce an independent copy of the original process, started at time $0$ in state $i$. If this process meets $X^{(0,0)}$ before time $t$ then it must also meet $X^{(0,j)}$ before time $t$, establishing (14.9).