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

14.8 Notes on Chapter 14

Section 14.1. Coupling has become a standard tool in probability theory. Lindvall [234] contains an extensive treatment, emphasizing its use to prove limit theorems. Stoyan [315] emphasizes comparison results in the context of queueing systems.

Birth-and-death chains have more monotonicity properties than stated in Proposition 14.1 – see van Doorn [329] for an extensive treatment. The coupling (14.2) of a birth-and-death process is better viewed as a specialization of couplings of stochastically monotone processes, c.f. [234] Chapter 4.3.

Section 14.1.1. Using the coupling inequality to prove convergence to stationarity (i.e. the convergence theorem, Chapter 2 yyy) and the analogs for continuous-space processes is called the coupling method. See [234] p. 233 for some history. Systematic use to bound variation distance in finite-state chains goes back to Aldous [15]. repeated here. The coupling inequality is often presented as involving the chain started from an arbitrary point and the stationary chain, leading to a bound on d(t)d(t) instead of d¯(t)\bar{d}(t).

Section 14.3. The voter model on ZdZ^{d}, and its duality with coalescing random walk, has been extensively studied – see [132, 232] for textbook treatments. The general notion of duality is discussed in [232] section 2.3. The voter model on general finite graphs has apparently been studied only once, by Donnelly and Welsh [128]. They studied the two-party model, and obtained the analog of Proposition 14.9(a) and some variations.

In the context of Open Problem 14.13 one can seek to use the randomization idea in Matthews’ method, and the problem reduces to proving that, in the coalescing of kk randomly-started particles, the chance that the final join is between a (k-1)(k-1)-cluster and a 11-cluster is small.

Section 14.3.5. On the infinite two-dimensional lattice, the meeting time MM of independent random walks is such that logM\log M has approximately an exponential distribution. Rather surprisingly, with a logarthmic time transformation one can get a analog of Proposition 14.17 on the infinite lattice – see Cox and Griffeath [103].

Section 14.4. Donnelly and Welsh [129] obtained Proposition 14.19 and a few other results, e.g. that, over edge-transitive graphs, cedgec_{\mbox{edge}} is uniquely maximized on the complete graph.

In the context of Open Problem 14.25, there are many known Normal limits in the context of interacting particle systems on the infinite lattice, but it is not clear how well those techniques extend to general finite graphs. It would be interesting to know whether Stein’s method could be used here (see Baldi and Rinott [38] for different uses of Stein’s method on graphs).

Section 14.5. The name “interchange process” is my coinage: the process, in the card-shuffling interpretation, was introduced by Diaconis and Saloff-Coste [115].

The interchange process can of course be constructed from a Poisson process of directed edges, as was the voter model in section 14.3. On the nn-path, this “graphical representation” has an interpretation as a method to create a pseudo-random permutation with paper and pencil – see Lange and Miller [221] for an entertaining elementary exposition.

Miscellaneous. One can define a wide variety of “growth and coverage” models on a finite graph, where there is some prescribed rule for growing a random subset 𝒮t{\cal S}_{t} of vertices, starting with a single vertex, and the quantity of interest is the time TT until the subset has grown to be the complete graph. Such processes have been studied as models for rumors, broadcast information and percolation – see e.g. Weber [335] and Fill and Pemantle [148].