# 14.5 The interchange process

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

Fix a graph on $n$ vertices. Given $n$ distinguishable particles, there are $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 $1$, 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!$ configurations. We want to study the time taken to approach the uniform distribution, as measured by the parameters $\tau_{2}$ and $\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 $1$, 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 $\tilde{X}_{t}$, say, with transition rate $1$ 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 $\tilde{\tau}_{2}$ for the relaxation time of $\tilde{X}$. The contraction principle (Chapter 4 yyy) implies $\tau_{2}\geq\tilde{\tau}_{2}$.

###### Open Problem 14.29

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

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

 $\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

$\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 $\mbox{{\cal N}}_{e}$ and $\mbox{{\cal N}}^{*}_{e}$ for each edge $e$. Say edge $e$ is special at time $t$ if the particles at the end-vertices in process $1$ are the same two particles as in process $2$, but in transposed position. The evolution rule for the coupled processes is

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

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 $(X_{t},Y_{t})$ recording the positions of particle $i$ 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 $U_{i}$, say. Thus $\max_{i}U_{i}$ is a coupling time and the coupling inequality (14.5) implies

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

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

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

and so

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

This leads to $\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 $n$ 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 $G$, 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 $G$) when passing from the interchange process to the card-shuffling model. On the complete graph we have $\max_{v,w}\tilde{E}_{v}\tilde{T}_{w}=\Theta(1)$ and $|\mbox{{\cal E}}|=\Theta(n^{2})$, and so Proposition 14.30 gives the bound $\tau_{1}=O(n^{2}\log n)$ for card shuffling by random transpositions, which is crude in view of the exact result $\tau_{1}=\Theta(n\log n)$. In contrast, consider the $n$-cycle, where $\max_{v,w}\tilde{E}_{v}\tilde{T}_{w}=\Theta(n^{2})$ and $|\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 $\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.