An -particle process on the circle.
Fix . Consider indistinguishable balls distributed amongst 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 . If box is occupied, do nothing. Otherwise, pick uniformly at random a direction (clockwise or counterclockwise) search from in that direction until encountering a ball, and move that ball to box . This specifies a Markov chain on the possible configurations of balls. The chain is reversible and the stationary distribution is uniform. Can we estimate the “mixing time” parameters and ? Note that as there is a limit process involving particles on the continuous circle, so we seek bounds which do not depend on .
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 . In the other direction, the bound
is easily established, by applying the extremal characterization (Chapter 3 yyy) to the function
where denotes the configuration with occupied boxes . It is natural to conjecture and .
The next example, from Jerrum [198] (xxx cite final version), uses a coupling whose construction is not quite obvious.
Permutations and words.
Fix a finite alphabet of size . Fix , and consider the set of “words” with each . Consider the Markov chain on in which a step is specified by the following two-stage procedure.
Stage 1. Pick a permutation of uniformly at random from the set of permutations satisfying .
Stage 2. Let be the cycles of . For each , and independently as varies, pick uniformly an element of , and define for every .
Here is an alternative description. Write for the set of permutations of . Consider the bipartite graph on vertices with edge-set . Then the chain is random walk on this bipartite graph, watched every second step when it is in .
From the second description, it is clear that the stationary probabilities are proportional to the degree of in the bipartite graph, giving
where . We shall use a coupling argument to establish the following bound on variation distance:
(14.28) |
implying that the variation threshold satisfies
The construction of the coupling depends on the following lemma, whose proof is deferred.
Givcen finite sets we can construct (for ) a uniform random permutation of with cycles , where the cycles are labeled such that
We construct a step of the coupled processes as follows. For each , set . Take random permutations as in the lemma, with cycles . Then define a uniform random permutation of , and similarly for . This completes stage 1. For stage 2, for each pair pick a uniform random element of and set
This specifies a Markov coupling. By construction
So the coupled processes satisfy
In particular and the coupling inequality (14.5) gives (14.28).
xxx proof of Lemma – tie up with earlier discussion.
Recall the discussion of the coupling inequality in section 14.1.1. Given a Markov chain and states , theory (e.g. [234] section 3.3) says there exists a maximal coupling with a coupling time 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 and so , but whose girth (minimal cycle length) is . On such a graph, the upper bound on obtained by a Markov coupling argument would be , which the Proposition shows is .
Fix vertices in a -regular graph () with girth . Let be any Markov coupling of discrete-time random walks started at and . Then the coupling time satisfies
Proof. We quote a simple lemma, whose proof is left to the reader.
Let be (dependent) random variables with , . Then
In particular, setting , we have
Now consider the distance between the two particles. The key idea is
(14.29) | |||||
The second inequality follows from the fact . For the first inequality, if then the incremental distance is distributed as in the lemma, so the conditional expectation of is . Now define a martingale via and
Rearranging,
Apply this inequality at the coupling time and take expectations: we have by the optional sampling theorem (Chapter 2 yyy) and , so
and the Proposition follows.