Reversible Markov Chains and Random Walks on Graphs

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

There is a well-established topic “interacting particle systems”, treated in the books by Griffeath [173], Liggett [232], and Durrett [132], which studies different models for particles on the infinite lattice ZdZ^{d}. All these models make sense, but mostly have not been systematically studied, in the context of finite graphs. Some of these models – the voter model, the antivoter model, and the exclusion process – are related (either directly or “via duality”) to interacting random walks, and setting down some basic results for these models on finite graphs (sections 14.3 - 14.5) is the main purpose of this chapter. Our focus is on applying results developed earlier in the book. With the important exception of duality, we do not use the deeper theory developed in the infinite setting. As usual, whether the deeper theory is applicable to the type of questions we ask in the finite setting is an interesting open question. These models are most naturally presented in continuous time, so our default convention is to work with continuous-time random walk.

We have already encountered results whose natural proofs were “by coupling”, and this is a convenient place to discuss couplings in general.