# 14.7 Other coupling examples

###### Example 14.32

An $m$-particle process on the circle.

Fix $m. Consider $m$ indistinguishable balls distributed amongst $K$ boxes, at most one ball to a box, and picture the boxes arranged in a circle. At each step, pick uniformly at random a box, say box $i$. If box $i$ is occupied, do nothing. Otherwise, pick uniformly at random a direction (clockwise or counterclockwise) search from $i$ in that direction until encountering a ball, and move that ball to box $i$. This specifies a Markov chain on the $\left(\begin{array}[]{c}K\\ m\end{array}\right)$ possible configurations of balls. The chain is reversible and the stationary distribution is uniform. Can we estimate the “mixing time” parameters $\tau_{1}$ and $\tau_{2}$? Note that as $K\rightarrow\infty$ there is a limit process involving $m$ particles on the continuous circle, so we seek bounds which do not depend on $K$.

There is a simple-to-describe coupling, where for each of the two versions we pick at each time the same box and the same direction. The coupling has the usual property (c.f. the proof of Proposition 14.30) that the number of “matched” balls (i.e. balls in the same box in both processes) can only increase. But analyzing the coupling time seems very difficult. Cuellar-Montoya [105] carries through a lengthy analysis to show that $\tau_{1}=O(m^{10})$. In the other direction, the bound

 $\tau_{2}\geq\frac{m^{3}}{8\pi^{2}}$

is easily established, by applying the extremal characterization (Chapter 3 yyy) to the function

 $g({\bf x})=\sum_{i=1}^{m}\sin(2\pi x_{i}/m)$

where ${\bf x}=(x_{1},\ldots,x_{m})$ denotes the configuration with occupied boxes $\{x_{1},\ldots,x_{m}\}$. It is natural to conjecture $\tau_{2}=\Theta(m^{3})$ and $\tau_{1}=O(m^{3}\log m)$.

The next example, from Jerrum [198] (xxx cite final version), uses a coupling whose construction is not quite obvious.

###### Example 14.33

Permutations and words.

Fix a finite alphabet $A$ of size $|A|$. Fix $m$, and consider the set $A^{m}$ of “words” ${\bf x}=(x_{1},\ldots,x_{m})$ with each $x_{i}\in A$. Consider the Markov chain on $A^{m}$ in which a step ${\bf x}\rightarrow{\bf y}$ is specified by the following two-stage procedure.

Stage 1. Pick a permutation $\sigma$ of $\{1,2,\ldots,m\}$ uniformly at random from the set of permutations $\sigma$ satisfying $x_{\sigma(i)}=x_{i}\forall i$.

Stage 2. Let $(c_{j}(\sigma);j\geq 1)$ be the cycles of $\sigma$. For each $j$, and independently as $j$ varies, pick uniformly an element $\alpha_{j}$ of $A$, and define $y_{i}=\alpha_{j}$ for every $i\in c_{j}(\sigma)$.

Here is an alternative description. Write $\Pi$ for the set of permutations of $\{1,\ldots,m\}$. Consider the bipartite graph on vertices $A^{m}\cup\Pi$ with edge-set $\{({\bf x},\sigma):x_{\sigma(i)}=x_{i}\forall i\}$. Then the chain is random walk on this bipartite graph, watched every second step when it is in $A^{m}$.

From the second description, it is clear that the stationary probabilities $\pi({\bf x})$ are proportional to the degree of ${\bf x}$ in the bipartite graph, giving

 $\pi({\bf x})\propto\prod_{a}n_{a}({\bf x})!$

where $n_{a}({\bf x})=|\{i:x_{i}=a\}|$. We shall use a coupling argument to establish the following bound on variation distance:

 $\bar{d}(t)\leq m\left(1-\frac{1}{|A|}\right)^{t}$ (14.28)

implying that the variation threshold satisfies

 $\tau_{1}\leq 1+\frac{1+\log m}{-\log(1-\frac{1}{|A|})}\leq 1+(1+\log m)|A|.$

The construction of the coupling depends on the following lemma, whose proof is deferred.

###### Lemma 14.34

Givcen finite sets $F^{1},F^{2}$ we can construct (for $u=1,2$) a uniform random permutation $\sigma^{u}$ of $F^{u}$ with cycles $(C^{u}_{j};j\geq 1)$, where the cycles are labeled such that

 $C^{1}_{j}\cap F^{1}\cap F^{2}=C^{2}_{j}\cap F^{1}\cap F^{2}\mbox{ for all }j.$

We construct a step $({\bf x}^{1},{\bf x}^{2})\rightarrow({\bf Y}^{1},{\bf Y}^{2})$ of the coupled processes as follows. For each $a\in A$, set $F^{1,a}=\{i:x^{1}_{i}=a\},\ F^{2,a}=\{i:x^{2}_{i}=a\}$. Take random permutations $\sigma^{1,a},\ \sigma^{2,a}$ as in the lemma, with cycles $C^{1,a}_{j},C^{2,a}_{j}$. Then $(\sigma^{1,a},a\in A)$ define a uniform random permutation $\sigma^{1}$ of $\{1,\ldots,m\}$, and similarly for $\sigma^{2}$. This completes stage 1. For stage 2, for each pair $(a,j)$ pick a uniform random element $\alpha^{a}_{j}$ of $A$ and set

 $Y^{1}_{i}=\alpha^{a}_{j}\mbox{ for every }i\in C^{1,a}_{j}$
 $Y^{2}_{i}=\alpha^{a}_{j}\mbox{ for every }i\in C^{2,a}_{j}.$

This specifies a Markov coupling. By construction

 $\displaystyle\mbox{if }x^{1}_{i}=x^{2}_{i}$ $\displaystyle\mbox{ then }Y^{1}_{i}=Y^{2}_{i}$ $\displaystyle\mbox{if }x^{1}_{i}\neq x^{2}_{i}$ $\displaystyle\mbox{ then }P(Y^{1}_{i}=Y^{2}_{i})=1/|A|.$

So the coupled processes $({\bf X}^{1}(t),{\bf X}^{2}(t))$ satisfy

 $P(X^{1}_{i}(t)\neq X^{2}_{i}(t))=\left(1-\frac{1}{|A|}\right)^{t}1_{(X^{1}_{i}% (0)\neq X^{2}_{i}(0))}.$

In particular $P({\bf X}^{1}(t)\neq{\bf X}^{2}(t))\leq m(1-1/|A|)^{t}$ and the coupling inequality (14.5) gives (14.28).

xxx proof of Lemma – tie up with earlier discussion.

## 14.7.1 Markov coupling may be inadequate

Recall the discussion of the coupling inequality in section 14.1.1. Given a Markov chain and states $i,j$, theory (e.g. [234] section 3.3) says there exists a maximal coupling $X^{(i)}_{t},X^{(j)}_{t}$ with a coupling time $T$ for which the coupling inequality (14.5) holds with equality. But this need not be a Markov coupling, i.e. of form (14.6), as the next result implies. The point is that there exist fixed-degree expander graphs with $\tau_{2}=O(1)$ and so $\tau_{1}=O(\log n)$, but whose girth (minimal cycle length) is $\Omega(\log n)$. On such a graph, the upper bound on $\tau_{1}$ obtained by a Markov coupling argument would be $\Theta(ET)$, which the Proposition shows is $n^{\Omega(1)}$.

###### Proposition 14.35

Fix vertices $i,j$ in a $r$-regular graph ($r\geq 3$) with girth $g$. Let $(X^{(i)}_{t},X^{(j)}_{t})$ be any Markov coupling of discrete-time random walks started at $i$ and $j$. Then the coupling time $T$ satisfies

 $ET\geq\frac{1-(r-1)^{-d(i,j)/2}}{r-2}\ (r-1)^{\frac{g}{4}-\frac{1}{2}}.$

Proof. We quote a simple lemma, whose proof is left to the reader.

###### Lemma 14.36

Let $\xi_{1},\xi_{2}$ be (dependent) random variables with $P(\xi_{u}=1)=\frac{r-1}{r}$, $P(\xi_{u}=-1)=\frac{1}{r}$. Then

 $E\theta^{\xi_{1}+\xi_{2}}\leq\frac{r-1}{r}\theta^{2}+\frac{1}{r}\theta^{-2},\ % 0<\theta<1.$

In particular, setting $\theta=(r-1)^{-1/2}$, we have

 $E\theta^{\xi_{1}+\xi_{2}}\leq 1.$

Now consider the distance $D_{t}\equiv d(X^{(i)}_{t},X^{(j)}_{t})$ between the two particles. The key idea is

 $\displaystyle E(\theta^{D_{t+1}}-\theta^{D_{t}}|X^{(i)}_{t},X^{(j)}_{t})$ $\displaystyle\leq$ $\displaystyle 0\mbox{ if }D_{t}\leq\lfloor g/2\rfloor-1$ (14.29) $\displaystyle\leq$ $\displaystyle(\theta^{-2}-1)\theta^{\lfloor g/2\rfloor}\mbox{ else. }$

The second inequality follows from the fact $D_{t+1}-D_{t}\geq-2$. For the first inequality, if $D_{t}\leq\lfloor g/2\rfloor-1$ then the incremental distance $D_{t+1}-D_{t}$ is distributed as $\xi_{1}+\xi_{2}$ in the lemma, so the conditional expectation of $\theta^{D_{t+1}-D_{t}}$ is $\leq 1$. Now define a martingale $(M_{t})$ via $M_{0}=0$ and

 $M_{t+1}-M_{t}=\theta^{D_{t+1}}-\theta^{D_{t}}-E(\theta^{D_{t+1}}-\theta^{D_{t}% }|X^{(i)}_{t},X^{(j)}_{t}).$

Rearranging,

 $\displaystyle\theta^{D_{t}}-\theta^{D_{0}}$ $\displaystyle=$ $\displaystyle M_{t}+\sum_{s=0}^{t-1}E(\theta^{D_{s+1}}-\theta^{D_{s}}|X^{(i)}_% {s},X^{(j)}_{s})$ $\displaystyle\leq$ $\displaystyle M_{t}+(\theta^{-2}-1)\theta^{\lfloor g/2\rfloor}t\mbox{ by }(% \ref{keyin}).$

Apply this inequality at the coupling time $T$ and take expectations: we have $EM_{T}=0$ by the optional sampling theorem (Chapter 2 yyy) and $D_{T}=0$, so

 $1-\theta^{d(i,j)}\leq(\theta^{-2}-1)\theta^{\lfloor g/2\rfloor}ET$

and the Proposition follows.