A new encoding of coalescent processes: applications to the additive and multiplicative cases

DOI10.1007/S00440-015-0665-1MaRDI QIDQ328790zbMATH OpenOpenAlexFDO

Authors Nicolas Broutin, Jean-François Marckert

Publication date 21 October 2016

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.4266

zbMATH Keywords

random graphPrim's algorithmCayley treeadditive coalescentinvasion percolationmultiplicative coalescent

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorics in computer science (68R05) Continuous-time Markov processes on general state spaces (60J25) Combinatorial probability (60C05)

Abstract: We revisit the discrete additive and multiplicative coalescents, starting with $n$ particles with unit mass. These cases are known to be related to some "combinatorial coalescent processes": a time reversal of a fragmentation of Cayley trees or a parking scheme in the additive case, and the random graph process $(G(n,p){)}_p$ in the multiplicative case. Time being fixed, encoding these combinatorial objects in real-valued processes indexed by the line is the key to describing the asymptotic behaviour of the masses as $no+infty$. We propose to use the Prim order on the vertices instead of the classical breadth-first (or depth-first) traversal to encode the combinatorial coalescent processes. In the additive case, this yields interesting connections between the different representations of the process. In the multiplicative case, it allows one to answer to a stronger version of an open question of Aldous [Ann. Probab., vol. 25, pp. 812--854, 1997]: we prove that not only the sequence of (rescaled) masses, seen as a process indexed by the time $lambda$, converges in distribution to the reordered sequence of lengths of the excursions above the current minimum of a Brownian motion with parabolic drift $(B_t+lambdat-t^2/2,tgeq0)$, but we also construct a version of the standard augmented multiplicative coalescent of Bhamidi, Budhiraja and Wang [Probab. Theory Rel., to appear] using an additional Poisson point process.

Recommendations

• The eternal multiplicative coalescent encoding via excursions of Lévy-type processes
• A new combinatorial representation of the additive coalescent
• The entrance boundary of the multiplicative coalescent
• On a ternary coalescent process
• The standard additive coalescent

Cites work

• {{#invoke:WikidataIB|getLink|Q2774021}} scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4519896}} scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q1579440}} A fragmentation process connected to Brownian motion
• {{#invoke:WikidataIB|getLink|Q5175231}} Aggregation models with limited choice and the multiplicative coalescent
• {{#invoke:WikidataIB|getLink|Q1228139}} An invariance principle for random walk conditioned by a late return to zero
• {{#invoke:WikidataIB|getLink|Q1356369}} Brownian excursions, critical random graphs and the multiplicative coalescent
• {{#invoke:WikidataIB|getLink|Q3953457}} Capillary displacement and percolation in porous media
• {{#invoke:WikidataIB|getLink|Q1284161}} Coalescent random forests
• {{#invoke:WikidataIB|getLink|Q2492015}} Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• {{#invoke:WikidataIB|getLink|Q1389184}} Construction of Markovian coalescents
• {{#invoke:WikidataIB|getLink|Q1283382}} Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• {{#invoke:WikidataIB|getLink|Q1039145}} Erdős-Renyi random graphs \(+\) forest fires \(=\) self-organized criticality
• {{#invoke:WikidataIB|getLink|Q1840520}} Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent
• {{#invoke:WikidataIB|getLink|Q5811564}} Justification and Extension of Doob's Heuristic Approach to the Kolmogorov- Smirnov Theorems
• {{#invoke:WikidataIB|getLink|Q5475389}} On a conditionally Poissonian graph process
• {{#invoke:WikidataIB|getLink|Q2426828}} One more approach to the convergence of the empirical process to the Brownian bridge
• {{#invoke:WikidataIB|getLink|Q3150200}} Phase transition for Parking blocks, Brownian excursion and coalescence
• {{#invoke:WikidataIB|getLink|Q5484520}} Random Fragmentation and Coagulation Processes
• {{#invoke:WikidataIB|getLink|Q2743189}} Random graphs.
• {{#invoke:WikidataIB|getLink|Q980742}} Random trees and applications
• {{#invoke:WikidataIB|getLink|Q1001839}} Stochastic coalescence with homogeneous-like interaction rates
• {{#invoke:WikidataIB|getLink|Q483318}} The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• {{#invoke:WikidataIB|getLink|Q2428503}} The continuum limit of critical random graphs
• {{#invoke:WikidataIB|getLink|Q756237}} The continuum random tree. I
• {{#invoke:WikidataIB|getLink|Q1307461}} The standard additive coalescent
• {{#invoke:WikidataIB|getLink|Q2491622}} Well-posedness of Smoluchowski's coagulation equation for a class of homogeneous kernels

Cited in

(18)

• Stochastic block model in a new critical regime and the interacting multiplicative coalescent
• Parking on Cayley trees and frozen Erdős-Rényi
• Cross-Multiplicative Coalescent Processes and Applications
• Rigid representations of the multiplicative coalescent with linear deletion
• Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes
• On moments of multiplicative coalescents
• The standard additive coalescent
• Models of random subtrees of a graph
• Critical random forests
• Invariance principle for fragmentation processes derived from conditioned stable Galton-Watson trees
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• A new combinatorial representation of the additive coalescent
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• Heavy-tailed configuration models at criticality
• Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent
• scientific article; zbMATH DE number 1789869 (Why is no real title available?)
• The eternal multiplicative coalescent encoding via excursions of Lévy-type processes
• Asymptotic behaviour of the first positions of uniform parking functions

This page was built for publication: A new encoding of coalescent processes: applications to the additive and multiplicative cases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q328790)