On trees invariant under edge contraction

Hénard, Olivier; Maillard, Pascal

Journal de l’École polytechnique — Mathématiques, Volume 3 (2016), pp. 365-400.

We study random trees which are invariant in law under the operation of contracting each edge independently with probability $p\in (0,1)$. We show that all such trees can be constructed through Poisson sampling from a certain class of random measured $ℝ$-trees satisfying a natural scale invariance property. This has connections to exchangeable partially ordered sets, real-valued self-similar increasing processes and quasi-stationary distributions of Galton–Watson processes.

Nous étudions les arbres aléatoires dont la loi est invariante par la contraction indépendante de leurs arêtes avec probabilité $p\in (0,1)$. Nous montrons que ces arbres peuvent être construits par échantillonnage poissonnien à partir d’une classe de $ℝ$-arbres aléatoires mesurés qui satisfont à une propriété d’invariance naturelle. Cette étude est liée aux ordres partiels échangeables, aux processus autosimilaires croissants à valeurs réelles et aux distributions quasi-stationnaires de processus de Galton-Watson.

Classification: 60J80, 60G18, 60B10
Keywords: Random tree, self-similar processes, Gromov-Hausdorff-Prokhorov topology
Mot clés : Arbres aléatoires, processus autosimilaires, topologie de Gromov-Hausdorff-Prokhorov

[ADH13] Abraham, R.; Delmas, J.-F.; Hoscheit, P. A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces, Electron. Comm. Probab., Volume 18 (2013) no. 14, pp. 1-21 | MR | Zbl

[Ald93] Aldous, D. The continuum random tree III, Ann. Probability, Volume 21 (1993) no. 1, pp. 248-289 | MR | Zbl

[ALW16] Athreya, S.; Löhr, W.; Winter, A. The gap between Gromov-vague and Gromov–Hausdorff-vague topology, Stochastic Processes Appl., Volume 126 (2016) no. 9, pp. 2527-2553 | DOI | MR | Zbl

[AP98] Aldous, D.; Pitman, J. Tree-valued Markov chains derived from Galton-Watson processes, Ann. Inst. H. Poincaré Probab. Statist., Volume 34 (1998) no. 5, pp. 637-686 | DOI | Numdam | MR | Zbl

[Dre84] Dress, A. W. M. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Advances in Math., Volume 53 (1984) no. 3, pp. 321-402 | MR | Zbl

[Drm09] Drmota, M. Random trees, SpringerWienNewYork, Vienna, 2009 | DOI

[Dug66] Dugundji, J. Topology, Allyn and Bacon, Inc., Boston, 1966 | Zbl

[EPW06] Evans, S. N; Pitman, J.; Winter, A. Rayleigh processes, real trees, and root growth with re-grafting, Probab. Theory Related Fields, Volume 134 (2006) no. 1, pp. 81-126 | DOI | MR | Zbl

[Eva08] Evans, S. N. Probability and real trees, Lect. Notes in Math., 1920, Springer, Berlin, 2008 | MR

[FHP11] Forman, N.; Haulk, C.; Pitman, J. A representation of exchangeable hierarchies by sampling from real trees (2011) (arXiv:1101.5619)

[FS09] Flajolet, Ph.; Sedgewick, R. Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | DOI | Zbl

[GPW09] Greven, A.; Pfaffelhuber, P.; Winter, A. Convergence in distribution of random metric measure spaces ($\Lambda$-coalescent measure trees), Probab. Theory Related Fields, Volume 145 (2009) no. 1-2, pp. 285-322 | DOI | MR | Zbl

[Gro07] Gromov, M. Metric structures for Riemannian and non-Riemannian spaces, Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA, 2007

[HBS65] Hurst, H. E.; Black, R. P.; Simaika, Y. M. Long-term storage: an experimental study, Constable, London, 1965

[Jan11] Janson, S. Poset limits and exchangeable random posets, Combinatorica, Volume 31 (2011) no. 5, pp. 529-563 | DOI | MR | Zbl

[LS06] Lovász, L.; Szegedy, B. Limits of dense graph sequences, J. Combinatorial Theory Ser. B, Volume 96 (2006) no. 6, pp. 933-957 | DOI | MR | Zbl

[Maiar] Maillard, P. The $\lambda$-invariant measures of subcritical Bienaymé–Galton–Watson processes, Bernoulli (to appear) (arXiv:1508.00845) | MR | Zbl

[MVN68] Mandelbrot, B. B.; Van Ness, J. W. Fractional Brownian motions, fractional noises and applications, SIAM Rev., Volume 10 (1968) no. 4, pp. 422-437 | DOI | MR | Zbl

[OV85] O’Brien, G. L.; Vervaat, W. Self-Similar Processes with Stationary Increments Generated by Point Processes, Ann. Probability, Volume 13 (1985) no. 1, pp. 28-52 | MR | Zbl

[Rém85] Rémy, J.-L. Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., Volume 19 (1985) no. 2, pp. 179-195 | Zbl

[Sta97] Stanley, R. P. Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 1997 | MR | Zbl

[Ver85] Vervaat, W. Sample Path Properties of Self-Similar Processes with Stationary Increments, Ann. Probability, Volume 13 (1985) no. 1, pp. 1-27 | MR | Zbl