The Stochastic Coalescence page

Note: Written in 2000, last edited around 2005.

This is a chatty discussion, intended to be understandable to a Ph. D. student in theoretical or applied probability. Numbers like [55] refer to the bibliography and are accompanied by Math Reviews links, and paper gives you the paper in compressed Postscript.

My survey paper Deterministic and Stochastic Models for Coalescence ...., written July 1997 (appeared early 1999) gave my view of the subject then. On this page I

Transparencies from four lectures given in 2000 can be found from here.

The 1997 survey

We seek to model the following physical phenomenon. Clusters of different masses move in space. When two clusters, of masses $x$ and $y$ say, come close, they may coalesce into one cluster of mass $x+y$. Models involve a rate kernel $K(x,y)$ which specifies the propensity for mass-$x$ and mass-$y$ clusters to merge. The physics of the specific physical phenomenon being modeled are used to derive the rate kernel $K(x,y)$. Otherwise our models are mean-field, ignoring the geometry of cluster positions.

To make a deterministic model, write $n(x,t)$ for the average number of mass-$x$ clusters per unit volume at time $t$. The idea above is then formalized by a set of differential equations for the $n(x,t)$ called the Smoluchowski coagulation equation. These were the subject of much study in the scientific literature, peaking during the 1960s.

Around 1980 there was a wave of statistical physics interest in an explicitly stochastic model, the Marcus-Lushnikov process. Start with $N$ separate atoms. As time increases, atoms merge into clusters according to the rule: each pair of clusters (sizes $x$ and $y$, say) merge at rate $K(x,y)/N$. Although it wasn't realized at the time, two special cases had been studied in the probability literature: the case $K(x,y) = 1$ is Kingman's coalescent and the case $K(x,y) = xy$ is the process of component sizes in the Erdos-Renyi random graph process.

Evans and Pitman MR 1625867 introduced the general stochastic coalescent. Here we scale total mass to be $1$, and allow countably many clusters. So the state-space is $\{(x_i): x_i > 0, \sum_i x_i = 1\}$ for continuous cluster-masses $x_i$. The evolution rule is: each pair of clusters (masses $x$ and $y$, say) merge at rate $K(x,y)$. If the kernel has a scaling property then the Marcus-Lushnikov process is a special case of the stochastic coalescent, by scaling mass and time.

My general theme has been to show that in special cases the stochastic coalescent can be described in terms of known stochastic processes, as described below. There are many other types of open problem in this area, described in the survey paper.

My own research

Consider the random graph process: $n$ vertices, with each possible edge being present with probability $1/n + t/n^{4/3}$. This is the right scaling around the critical probability $1/n$; note $t$ can be positive or negative. The largest components are all of order $n^{2/3}$; if we scale size by $n^{-2/3}$ and take $n \to \infty$ limits of the vector of component sizes, we get a limit process $Z(t) = (Z_1(t),Z_2(t),......)$ parametrized by "time" $- \infty < t < \infty$. This is the subject of paper [72] MR 98d:60019 We call $Z$ the standard multiplicative coalescent. It is the special case $K(x,y) = xy$ of the general stochastic coalescent mentioned above. Surprisingly, the marginal distributions $Z(t)$ can be described in terms of excursion lengths of a certain inhomogeneous reflecting Brownian motion. This process is standard by virtue of starting from time $-\infty$ in a particular way. There are other versions of the multiplicative coalescent and a complete description of all versions (the entrance boundary) is given in paper [76] MR 99d:60086 (with Vlada Limic).

As another special model, consider the continuum random tree and for $0< \lambda < \infty$ split the tree into components at the points of a Poisson process of rate $\lambda$ along the skeleton of the tree. This gives a vector $Y(\lambda) = (Y_1(\lambda),Y_2(\lambda),......)$ of masses of the components, which as $\lambda$ increases specifies a fragmentation process. In paper [82] (with Jim Pitman) it is shown that reversing the direction of time by setting $\lambda = e^{-t}$ gives the standard additive coalescent, that is the case $K(x,y) = x+y$ of the general stochastic coalescent. The same construction applied to a more general family of inhomogeneous continuum random trees yields the general version of the additive coalescent, i.e. we can identify the entrance boundary: see paper [87] (with Jim Pitman).

In a different direction, there is some non-rigorous statistical physics literature (van Dongen MR 90f:82016) concerning cluster sizes in the gelation phase transition for rate kernels $K(x,y)$ more general than $K(x,y) = xy$. Almost nothing is known rigorously, but paper [77] MR 99g:60128 makes a start by studying a special one-parameter family of kernels. Jeon MR 99g:82056 also has results of this type.

Updates and complements

Smoluchowski Coagulation Equations

Variation continue to attract interest. Of potential relevance to the stochastic setting is work on self-similarity by Davies et al MR 2000d:82024 .

WLLNs and Coagulation-Fragmentation

Norris MR 1682596 gives a detailed account of the WLLN is the pure coalescent case. The analog of the weak law of large numbers relating stochastic and deterministic models when fragmentation is present has been studied by Jeon MR 99g:82056 and Guias MR 98j:60115 and Eibeck - Wagner preprint .

Other appearances of the Standard Additive Coalescent

Bertoin A fragmentation process related to Brownian motion gives an alternative construction of the standard additive coalescent in terms of excursions of Brownian motion with drift (the drift being a constant depending on $t$). This construction is more direct, but also perhaps more mysterious, than our construction via the CRT. Chassaing and Louchard preprint give a parallel connection with hashing with linear probing. Bertoin Clustering statistics for sticky particles with Brownian initial velocity makes a connection with a process of sticky particles which move deterministically on the line, sticking when they meet while conserving mass and momentum, in the case where the initial positions and velocities are random.

Another special model

Bolthausen and Sznitman MR 1652734 study a special model of multiple (rather than binary) coalescence, motivated by Ruelle's probability cascades. Pitman preprint studies a more general family of coalescents with multiple collisions, and Bertoin and Le Gall The Bolthausen-Sznitman coalescent and the genealogy of continuous-state branching processes relates it to Neveu's continuous-state branching process.