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
- indicate what's in the survey
- describe my technical work
- update subsequent work.
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.