xxx notation: for process or underlying RW?
Fix a graph on vertices. Given distinguishable particles, there are “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 , 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 configurations. We want to study the time taken to approach the uniform distribution, as measured by the parameters and .
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 , 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 , say, with transition rate 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 for the relaxation time of . The contraction principle (Chapter 4 yyy) implies .
Does in general?
If the answer is “yes”, then the general bound of Chapter 4 yyy will give
but the following bound is typically better.
.
Proof. We use a coupling argument. Start two versions of the interchange process in arbitrary initial configurations. Set up independent Poisson processes and for each edge . Say edge is special at time if the particles at the end-vertices in process are the same two particles as in process , but in transposed position. The evolution rule for the coupled processes is
Use the same Poisson process to define simultaneous switch times for both interchange processes, except for special edges where we use for process and for process .
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 recording the positions of particle 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 , say. Thus is a coupling time and the coupling inequality (14.5) implies
Now is distributed as , where and are the initial positions of particle in the two versions and where denotes meeting time for independent copies of the underlying random walk . Writing , we have by subexponentiality (as at (14.16))
and so
This leads to and the result follows from Proposition 14.5.
Taking the underlying graph to be the complete graph on 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 , the jump chain can be viewed as a card-shuffling model, but note that parameters are multiplied by (the number of edges in ) when passing from the interchange process to the card-shuffling model. On the complete graph we have and , and so Proposition 14.30 gives the bound for card shuffling by random transpositions, which is crude in view of the exact result . In contrast, consider the -cycle, where and . 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 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.