14 Interacting Particles on Finite Graphs (March 10, 1994)

14.7 Other coupling examples

Example 14.32

An mm-particle process on the circle.

Fix m<Km<K. Consider mm indistinguishable balls distributed amongst KK 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 ii. If box ii is occupied, do nothing. Otherwise, pick uniformly at random a direction (clockwise or counterclockwise) search from ii in that direction until encountering a ball, and move that ball to box ii. This specifies a Markov chain on the (Km)\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 τ1\tau_{1} and τ2\tau_{2}? Note that as KK\rightarrow\infty there is a limit process involving mm particles on the continuous circle, so we seek bounds which do not depend on KK.

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 τ1=O(m10)\tau_{1}=O(m^{10}). In the other direction, the bound


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

g(𝐱)=i=1msin(2πxi/m)g({\bf x})=\sum_{i=1}^{m}\sin(2\pi x_{i}/m)

where 𝐱=(x1,,xm){\bf x}=(x_{1},\ldots,x_{m}) denotes the configuration with occupied boxes {x1,,xm}\{x_{1},\ldots,x_{m}\}. It is natural to conjecture τ2=Θ(m3)\tau_{2}=\Theta(m^{3}) and τ1=O(m3logm)\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 AA of size |A||A|. Fix mm, and consider the set AmA^{m} of “words” 𝐱=(x1,,xm){\bf x}=(x_{1},\ldots,x_{m}) with each xiAx_{i}\in A. Consider the Markov chain on AmA^{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,,m}\{1,2,\ldots,m\} uniformly at random from the set of permutations σ\sigma satisfying xσ(i)=xiix_{\sigma(i)}=x_{i}\forall i.

Stage 2. Let (cj(σ);j1)(c_{j}(\sigma);j\geq 1) be the cycles of σ\sigma. For each jj, and independently as jj varies, pick uniformly an element αj\alpha_{j} of AA, and define yi=αjy_{i}=\alpha_{j} for every icj(σ)i\in c_{j}(\sigma).

Here is an alternative description. Write Π\Pi for the set of permutations of {1,,m}\{1,\ldots,m\}. Consider the bipartite graph on vertices AmΠA^{m}\cup\Pi with edge-set {(𝐱,σ):xσ(i)=xii}\{({\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 AmA^{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

π(𝐱)ana(𝐱)!\pi({\bf x})\propto\prod_{a}n_{a}({\bf x})!

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

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

implying that the variation threshold satisfies

τ11+1+logm-log(1-1|A|)1+(1+logm)|A|.\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 F1,F2F^{1},F^{2} we can construct (for u=1,2u=1,2) a uniform random permutation σu\sigma^{u} of FuF^{u} with cycles (Cju;j1)(C^{u}_{j};j\geq 1), where the cycles are labeled such that

Cj1F1F2=Cj2F1F2 for all j.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 (𝐱1,𝐱2)(𝐘1,𝐘2)({\bf x}^{1},{\bf x}^{2})\rightarrow({\bf Y}^{1},{\bf Y}^{2}) of the coupled processes as follows. For each aAa\in A, set F1,a={i:xi1=a},  F2,a={i:xi2=a}F^{1,a}=\{i:x^{1}_{i}=a\},\ F^{2,a}=\{i:x^{2}_{i}=a\}. Take random permutations σ1,a,  σ2,a\sigma^{1,a},\ \sigma^{2,a} as in the lemma, with cycles Cj1,a,Cj2,aC^{1,a}_{j},C^{2,a}_{j}. Then (σ1,a,aA)(\sigma^{1,a},a\in A) define a uniform random permutation σ1\sigma^{1} of {1,,m}\{1,\ldots,m\}, and similarly for σ2\sigma^{2}. This completes stage 1. For stage 2, for each pair (a,j)(a,j) pick a uniform random element αja\alpha^{a}_{j} of AA and set

Yi1=αja for every iCj1,aY^{1}_{i}=\alpha^{a}_{j}\mbox{ for every }i\in C^{1,a}_{j}
Yi2=αja for every iCj2,a.Y^{2}_{i}=\alpha^{a}_{j}\mbox{ for every }i\in C^{2,a}_{j}.

This specifies a Markov coupling. By construction

if xi1=xi2\displaystyle\mbox{if }x^{1}_{i}=x^{2}_{i} then Yi1=Yi2\displaystyle\mbox{ then }Y^{1}_{i}=Y^{2}_{i}
if xi1xi2\displaystyle\mbox{if }x^{1}_{i}\neq x^{2}_{i} then P(Yi1=Yi2)=1/|A|.\displaystyle\mbox{ then }P(Y^{1}_{i}=Y^{2}_{i})=1/|A|.

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

P(Xi1(t)Xi2(t))=(1-1|A|)t1(Xi1(0)Xi2(0)).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(𝐗1(t)𝐗2(t))m(1-1/|A|)tP({\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,ji,j, theory (e.g. [234] section 3.3) says there exists a maximal coupling Xt(i),Xt(j)X^{(i)}_{t},X^{(j)}_{t} with a coupling time TT 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 τ2=O(1)\tau_{2}=O(1) and so τ1=O(logn)\tau_{1}=O(\log n), but whose girth (minimal cycle length) is Ω(logn)\Omega(\log n). On such a graph, the upper bound on τ1\tau_{1} obtained by a Markov coupling argument would be Θ(ET)\Theta(ET), which the Proposition shows is nΩ(1)n^{\Omega(1)}.

Proposition 14.35

Fix vertices i,ji,j in a rr-regular graph (r3r\geq 3) with girth gg. Let (Xt(i),Xt(j))(X^{(i)}_{t},X^{(j)}_{t}) be any Markov coupling of discrete-time random walks started at ii and jj. Then the coupling time TT satisfies

ET1-(r-1)-d(i,j)/2r-2(r-1)g4-12.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 ξ1,ξ2\xi_{1},\xi_{2} be (dependent) random variables with P(ξu=1)=r-1rP(\xi_{u}=1)=\frac{r-1}{r}, P(ξu=-1)=1rP(\xi_{u}=-1)=\frac{1}{r}. Then

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

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

Eθξ1+ξ21.E\theta^{\xi_{1}+\xi_{2}}\leq 1.

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

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

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

Mt+1-Mt=θDt+1-θDt-E(θDt+1-θDt|Xt(i),Xt(j)).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}).


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

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

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

and the Proposition follows.