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

14.5 The interchange process

xxx notation: X~\tilde{X} for process or underlying RW?

Fix a graph on nn vertices. Given nn distinguishable particles, there are n!n! “configurations” with one particle at each vertex. The interchange process is the following continuous-time reversible Markov chain on configurations.

On each edge there is a Poisson, rate 11, process of “switch times”, at which times the particles at the two ends of the edge are interchanged.

The stationary distribution is uniform on the n!n! configurations. We want to study the time taken to approach the uniform distribution, as measured by the parameters τ2\tau_{2} and τ1\tau_{1}.

As with the voter model, there is an induced process obtained by declaring some subset of particles to be “visible”, regarding the visible particles as indistinguishable, and ignoring the invisible particles. Interchanging two visible particles has no effect, so the dynamics of the induced process are as follows.

On each edge there is a Poisson, rate 11, process of “switch times”. At a switch time, if one endpoint is unoccupied and the other endpoint is occupied by a (visible) particle, then the particle moves to the other endpoint.

This is the finite analog of the exclusion process studied in the interacting particle systems literature. But in the finite setting, the interchange process seems more fundamental.

If we follow an individual particle, we see a certain continuous-time Markov chain X~t\tilde{X}_{t}, say, with transition rate 11 along each edge. In the terminology of Chapter 3 yyy this is the fluid model random walk, rather than the usual continuized random walk. Write τ~2\tilde{\tau}_{2} for the relaxation time of X~\tilde{X}. The contraction principle (Chapter 4 yyy) implies τ2τ~2\tau_{2}\geq\tilde{\tau}_{2}.

Open Problem 14.29

Does τ2=τ~2\tau_{2}=\tilde{\tau}_{2} in general?

If the answer is “yes”, then the general bound of Chapter 4 yyy will give

τ1τ~2(1+12logn!)=O(τ~2nlogn)\tau_{1}\leq\tilde{\tau}_{2}(1+\frac{1}{2}\log n!)=O(\tilde{\tau}_{2}n\log n)

but the following bound is typically better.

Proposition 14.30

τ1(2+logn)emaxv,wE~vT~w\tau_{1}\leq(2+\log n)e\ \max_{v,w}\tilde{E}_{v}\tilde{T}_{w}.

Proof. We use a coupling argument. Start two versions of the interchange process in arbitrary initial configurations. Set up independent Poisson processes 𝒩e\mbox{${\cal N}$}_{e} and 𝒩e*\mbox{${\cal N}$}^{*}_{e} for each edge ee. Say edge ee is special at time tt if the particles at the end-vertices in process 11 are the same two particles as in process 22, but in transposed position. The evolution rule for the coupled processes is

Use the same Poisson process 𝒩e\mbox{${\cal N}$}_{e} to define simultaneous switch times for both interchange processes, except for special edges where we use 𝒩e\mbox{${\cal N}$}_{e} for process 11 and 𝒩e*\mbox{${\cal N}$}^{*}_{e} for process 22.

Clearly, once an individual particle is matched (i.e. at the same vertex in both processes), it remains matched thereafter. And if we watch the process (Xt,Yt)(X_{t},Y_{t}) recording the positions of particle ii in each process, it is easy to check this process is the same as watching two independent copies of the continuous-time random walk, run until they meet, at time UiU_{i}, say. Thus maxiUi\max_{i}U_{i} is a coupling time and the coupling inequality (14.5) implies

d¯(t)P(maxiUi>t).\bar{d}(t)\leq P(\max_{i}U_{i}>t).

Now UiU_{i} is distributed as Mv(i),w(i)M_{v(i),w(i)}, where v(i)v(i) and w(i)w(i) are the initial positions of particle ii in the two versions and where Mv,wM_{v,w} denotes meeting time for independent copies of the underlying random walk X~t\tilde{X}_{t}. Writing m*=maxv,wEMv,wm^{*}=\max_{v,w}EM_{v,w}, we have by subexponentiality (as at (14.16))

P(Mv,w>t)exp(1-tem*)P(M_{v,w}>t)\leq\exp\left(1-\frac{t}{em^{*}}\right)

and so

d¯(t)nexp(1-tem*).\bar{d}(t)\leq n\exp\left(1-\frac{t}{em^{*}}\right).

This leads to τ1(2+logn)em*\tau_{1}\leq(2+\log n)em^{*} and the result follows from Proposition 14.5.

14.5.1 Card-shuffling interpretation

Taking the underlying graph to be the complete graph on nn vertices, the discrete-time jump chain of the interchange process is just the “card shuffling by random transpositions” model from Chapter 7 yyy. On any graph GG, the jump chain can be viewed as a card-shuffling model, but note that parameters τ\tau are multiplied by |||\mbox{${\cal E}$}| (the number of edges in GG) when passing from the interchange process to the card-shuffling model. On the complete graph we have maxv,wE~vT~w=Θ(1)\max_{v,w}\tilde{E}_{v}\tilde{T}_{w}=\Theta(1) and ||=Θ(n2)|\mbox{${\cal E}$}|=\Theta(n^{2}), and so Proposition 14.30 gives the bound τ1=O(n2logn)\tau_{1}=O(n^{2}\log n) for card shuffling by random transpositions, which is crude in view of the exact result τ1=Θ(nlogn)\tau_{1}=\Theta(n\log n). In contrast, consider the nn-cycle, where maxv,wE~vT~w=Θ(n2)\max_{v,w}\tilde{E}_{v}\tilde{T}_{w}=\Theta(n^{2}) and ||=n|\mbox{${\cal E}$}|=n. Here the jump process is the “card shuffling by random adjacent transpositions” model from Chapter 7 yyy. In this model, Proposition 14.30 gives the bound τ1=O(n3logn)\tau_{1}=O(n^{3}\log n) which as mentioned in Chapter 7 yyy is the correct order of magnitude.

Diaconis and Saloff-Coste [115] studied the card-shuffling model as an application of more sophisticated techniques of comparison of Dirichlet forms.

xxx talk about their results.