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.
For almost two decades the only stochastic merging process widely studied by probabilists was the (Kingman) coalescent @cite_24 @cite_39 . Starting with Aldous @cite_38 @cite_14 , and Pitman @cite_32 , Sagitov @cite_16 , and Donnelly and Kurtz @cite_37 , the main-stream probability research on coalescents was much diversified.
@cite_38 @cite_37 @cite_14 @cite_32 @cite_39 @cite_24 @cite_16
1573705578 2065794571 2067409890 1970474336
Aldous and Pitman have studied the asymptotic behavior of the additive coalescent processes using a nested family random forests derived by logging certain inhomogeneous continuum random trees. Here we propose a different approach based on partitions of the unit interval induced by certain bridges with exchangeable increments. The analysis is made simple by an interpretation in terms of an aggregating server system. 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 We study a class of stochastic flows connected to the coalescent processes that have been studied recently by Mohle, Pitman, Sagitov and Schweinsberg in connection with asymptotic models for the genealogy of populations with a large fixed size. We define a bridge to be a right-continuous process (B(r),r[0,1]) with nondecreasing paths and exchangeable increments, such that B(0)=0 and B(1)=1. We show that flows of bridges are in one-to-one correspondence with the so-called exchangeable coalescents. This yields an infinite-dimensional version of the classical Kingman representation for exchangeable partitions of ℕ. We then propose a Poissonian construction of a general class of flows of bridges and identify the associated coalescents. We also discuss an important auxiliary measure-valued process, which is closely related to the genealogical structure coded by the coalescent and can be viewed as a generalized Fleming-Viot process. Author(s): Aldous, DJ; Pittel, B | Abstract: A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1 n, is studied. The detailed picture of emergence of giant components with O(n2 3) vertices is shown to be the same as in the Erdos-Renyi graph process with the number of vertices fixed at n at the start. A major difference is that now the transition occurs about a time t = π 2, rather than t = 1. The proof has three ingredients. The size of the largest component in the subcritical phase is bounded by comparison with a certain multitype branching process. With this bound at hand, the growth of the sum-of-squares and sum-of-cubes of component sizes is shown, via martingale methods, to follow closely a solution of the Smoluchowsky-type equations. The approximation allows us to apply results of Aldous [Brownian excursions, critical random graphs and the multiplicative coalescent, Ann Probab 25 (1997), 812-854] on emergence of giant components in the multiplicative coalescent, i.e., a nonuniform random graph process. © 2000 John Wiley a Sons, Inc. Random Struct. Alg., 17, 79-102, 2000.