Coalescing Random Walks

In our proof of the basic dichotomy we showed that working backwards in time in the voter model lead to a system of coalescing random walks. In that system each site could be 0 = vacant or 1 = occupied by a particle. Particles perform random walks that are independent until two particles hit at which point they coalesce into one. It is easy to show

Math Exercise. If we start coalescing random walk from all sites occupied and we let p(t) be the probability a given site x is occupied at time t then p(t) converges to 0 as t tends to infinity.

It is much more complicated problem to determine the rate at which p(t) tends to 0. Through the combined efforts of Sudbury (1976), Kelley (1977), Sawyer (1979), and Bramson and Griffeath (1980) it has been shown that

where gamma_d is the probability a d dimensional random walk returns to the origin.

s3 Exercise. It is difficult to imagine someone guessing the last result by watching a simulation of coalescing random walk starting from all sites occupied. However, one should be able to see that the density of particles, p(t), tends to 0. With a little imagination one can also see Arratia's (1981) result that in dimensions d > 1, if one rescales space at time t so that the density of particles is 1, then as t tends to infinity the limit is a spatial Poisson process with intensity 1.

A detailed knowledge of the properties of coalescing random walks is the key to understanding the structure of the voter model. In two dimensions this is a very interesting story with surprising connections to the nonspatial coalescent. See Cox and Griffeath (1986) and (1990).

Sudbury, A. (1976) The size of the region occupied by one type in an invasion process. J. Appl. Prob. 13, 355-356

Kelley, F.P. (1977) The asymptotic behavior of an invasion process. J. Appl. Prob. 14, 584-590

Sawyer, S. (1979) A limit theorem for patch sizes in a selectively-neutral migration model. J. Appl. Prob. 16, 482--495

Bramson, M. and Griffeath, D. (1980) Asymptotics for some interacting particle systems on Z^d. Z. fur Wahr. 53, 183-196

Arratia, R. (1981) Limiting point processes for rescaling of coalescing and annihilating random walks on Z^d. Ann. Prob. 9, 909-936

Cox, J.T. and Griffeath, D. (1986) Diffusive clustering in the two dimensional voter model. Ann. Prob. 14, 347-370

Cox, J.T. and Griffeath, D. (1990) Mean field asymptotics for the planar stepping stone model. Proc. London Math. Soc. 61, 189-208

On to the next page or back to the survey contents page