Brownian excursions, critical random graphs and the multiplicative coalescent

Aldous, David

Ann. Probab., Tome 25 (1997) no. 4, p. 812-854 / Harvested from Project Euclid

Résumé

Let $(B^t (s), 0 \leq s < \infty)$ be reflecting inhomogeneous Brownian motion with drift $t - s$ at time $s$, started with $B^t (0) = 0$. Consider the random graph $\mathscr{G}(n, n^{-1} + tn^{-4/3})$, whose largest components have size of order $n^{2/3}$. Normalizing by $n^{-2/3}$, the asymptotic joint distribution of component sizes is the same as the joint distribution of excursion lengths of $B^t$ (Corollary 2). The dynamics of merging of components as $t$ increases are abstracted to define the multiplicative coalescent process. The states of this process are vectors $\mathsf{x}$ of nonnegative real cluster sizes $(x_i)$, and clusters with sizes $x_i$ and $x_j$ merge at rate $x_i x_j$. The multiplicative coalescent is shown to be a Feller process on l_2$. The random graph limit specifies the standard multiplicative coalescent, which starts from infinitesimally small clusters at time $-\infty$; the existence of such a process is not obvious.

Détail

Publié le : 1997-04-14
Classification:  Brownian motion,  Brownian excursion,  Markov process,  random graph,  critical point,  stochastic coalescent,  stochastic coagulation,  weak convergence,  60C05,  60J50