The multiplicative coalescent is a Markov process taking values in ordered @math . It is a mean-field process in which any pair of blocks coalesces at rate proportional to the product of their masses. In Aldous and Limic (1998) each extreme eternal version @math of the multiplicative coalescent was described in three different ways. One of these specifications matches the (marginal) law of @math to that of the ordered excursion lengths above past minima of @math , where @math is a certain Levy-type process which (modulo shift and scaling) has infinitesimal drift @math at time @math . Using a modification of the breadth-first-walk construction from Aldous (1997) and Aldous and Limic (1998), and some new insight from the thesis by Uribe (2007), this work settles an open problem (3) from Aldous (1997), in the more general context of Aldous and Limic (1998). Informally speaking, @math is entirely encoded by @math , and contrary to Aldous' original intuition, the evolution of time for @math does correspond to the linear increase in the constant part of the drift of @math . In the "standard multiplicative coalescent" context of Aldous (1997), this result was first announced by Armendariz in 2001, and obtained in a recent preprint by Broutin and Marckert, who simultaneously account for the process of excess edge counts (or marks). The novel argument presented here is based on a sequence of relatively elementary observations. Some of its components (for example, the new dynamic random graph construction via "simultaneous" breadth-first walks) are of independent interest, and may be useful for obtaining more sophisticated asymptotic results on near critical random graphs and related processes.
The Kingman coalescent and, more generally, the mass-less (exchangeable) coalescents of @cite_32 @cite_16 @cite_37 mostly appear in connection to the mathematical population genetics, as universal (robust) scaling limits of genealogical trees (see for example @cite_41 @cite_11 @cite_5 @cite_29 , or a survey @cite_58 ). The standard multiplicative coalescent is the universal scaling limit of numerous stochastic (typically combinatorial or graph-theoretic) homogeneous (or symmetric) merging-like models @cite_14 @cite_8 @cite_36 @cite_9 @cite_60 @cite_6 @cite_56 @cite_42 . The non-standard'' eternal extreme laws from @cite_10 are also scaling limits of inhomogeneous random graphs and related processes under appropriate assumptions @cite_10 @cite_43 @cite_52 .
@cite_41 @cite_36 @cite_29 @cite_42 @cite_43 @cite_5 @cite_58 @cite_10 @cite_8 @cite_60 @cite_52 @cite_37 @cite_32 @cite_6 @cite_56 @cite_16 @cite_14 @cite_9 @cite_11
2065794571 2056513564 2109430192 1986567569
k−2 � 1 − xb−k � � dx� . Call this process a � -coalescent. Discrete measure-valued processes derived from the � -coalescent model a system of masses undergoing coalescent collisions. Kingman's coalescent, which has numerous applications in population genetics, is the δ0-coalescent for δ0 a unit mass at 0. The coalescent recently derived by Bolthausen and Sznit- man from Ruelle's probability cascades, in the context of the Sherrington- Kirkpatrick spin glass model in mathematical physics, is the U-coalescent for U uniform on � 0� 1� .F or� = U, and whenever an infinite number of masses are present, each collision in a � -coalescent involves an infinite number of masses almost surely, and the proportion of masses involved exists as a limit almost surely and is distributed proportionally to � . The two-parameter Poisson-Dirichlet family of random discrete distributions derived from a stable subordinator, and corresponding exchangeable ran- dom partitions ofgoverned by a generalization of the Ewens sampling formula, are applied to describe transition mechanisms for processes of coalescence and fragmentation, including the U-coalescent and its time reversal. 1. Introduction. Markovian coalescent models for the evolution of a sys- tem of masses by a random process of binary collisions were introduced by Marcus (29) and Lushnikov (28). See (3) for a recent survey of the scientific lit- erature of these models and their relation to Smoluchowski's mean-field theory of coagulation phenomena. Evans and Pitman (15) gave a general framework for the rigorous construction of partition-valued and discrete measure-valued coalescent Markov processes allowing infinitely many massses and treated the binary coalescent model where each pair of masses x and y is subject to a coa- lescent collision at rate κ� xyfor a suitable rate kernel κ. This paper studies a family of partition-valued Markov processes, with state space the compact set of all partitions of � �= � 1� 2 ���� � , such that the restriction of the partition to each finite subset ofis a Markov chain with transition rates of a simple form determined by the moments of a finite measureon the unit interval. The case � = δ 0 , a unit mass at 0, is Kingman's coalescent in which every Let (B t (s), 0 ≤ s < ∞) be reflecting inhomogeneous Brownian motion with drift t - s at time s, started with B t (0) = 0. Consider the random graph script G sign(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 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 -∞; the existence of such a process is not obvious. The multiplicative coalescent @math is a @math -valued Markov process representing coalescence of clusters of mass, where each pair of clusters merges at rate proportional to product of masses. From random graph asymptotics it is known (Aldous (1997)) that there exists a standard version of this process starting with infinitesimally small clusters at time @math . In this paper, stochastic calculus techniques are used to describe all versions @math of the multiplicative coalescent. Roughly, an extreme version is specified by translation and scale parameters, and a vector @math of relative sizes of large clusters at time @math . Such a version may be characterized in three ways: via its @math behavior, via a representation of the marginal distribution @math in terms of excursion-lengths of a Levy-type process, or via a weak limit of processes derived from the standard version via a "coloring" construction. Regard an element of the set Δ := (x 1 , x 2 , . . .): x 1 ≥ x 2 ≥ ⋯ ≥ 0, ∑ i x i = 1 as a fragmentation of unit mass into clusters of masses x i . The additive coalescent of Evans and Pitman is the Δ-valued Markov process in which pairs of clusters of masses x i , x j merge into a cluster of mass x i + x j at rate x i + x j . They showed that a version (X ∞ (t), -∞ < t < ∞) of this process arises as a n → ∞ weak limit of the process started at time -1 2 log n with n clusters of mass 1 n. We show this standard additive coalescent may be constructed from the continuum random tree of Aldous by Poisson splitting along the skeleton of the tree. We describe the distribution of X∞(t) on Δ at a fixed time t. We show that the size of the cluster containing a given atom, as a process in t, has a simple representation in terms of the stable subordinator of index 1 2. As t → -∞, we establish a Gaussian limit for (centered and normalized) cluster sizes and study the size of the largest cluster.