Probabilistic Combinatorics, Weak Convergence, and Probability Models
for Random Coalescing
David Aldous (UC Berkeley, Department of Statistics)
The first "interesting" result in the theory of weak convergence of
probability measures is that simple symmetric random walk can be rescaled
to converge to Brownian motion. The underlying random walk may be viewed
as the uniform distribution on a combinatorial set (binary n-tuples). It
turns out that uniform distributions on other combinatorial sets
(triangulations, mappings, graphs) have analogous limits constru(triangulations, mappings, graphs) have analogous limits constructible
from Brownian-type continuous processes. The limit process describing
merging of random graph components in the critical region has a different
interpretation as a natural Markov model of coalescence of mass into
clusters. Studing how this process starts from the infinite past is a
surprisingly subtle problem.