Convergence of bi-measure $ℝ$-trees and the pruning process

Löhr, Wolfgang; Voisin, Guillaume; Winter, Anita

Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4, pp. 1342-1368.

Dans (Ann. Inst. Henri Poincaré Probab. Stat. 34 (1998) 637–686), les auteurs obtiennent une chaîne de Markov à valeurs arbres en élaguant de plus en plus de sous-arbres le long des nœuds d’un arbre de Galton–Watson. Plus récemment dans (Ann. Probab. 40 (2012) 1167–1211), un analogue continu de la dynamique d’élagage à valeurs arbres est construit sur des arbres de Lévy. Dans cet article, nous présentons une nouvelle topologie qui permet de relier les dynamiques discrètes et continues en les considérant comme des exemples du même processus de Markov fort avec des conditions initiales différentes. Nous construisons ce processus d’élagage sur l’espace des arbres appelés bi-mesurés, qui sont des espaces métriques mesurés avec une mesure d’élagage additionnelle. La mesure d’élagage est supposée finie sur les arbres finis, mais pas nécessairement localement finie. De plus, nous caractérisons analytiquement le processus d’élagage par son générateur infinitésimal et montrons qu’il est continu en son arbre bi-mesuré initial. Plusieurs exemples sont donnés, notamment le cas d’une loi de reproduction à variance finie où la mesure d’élagage est la mesure des longueurs sur l’arbre sous-jacent.

In (Ann. Inst. Henri Poincaré Probab. Stat. 34 (1998) 637–686) a tree-valued Markov chain is derived by pruning off more and more subtrees along the edges of a Galton–Watson tree. More recently, in (Ann. Probab. 40 (2012) 1167–1211), a continuous analogue of the tree-valued pruning dynamics is constructed along Lévy trees. In the present paper, we provide a new topology which allows to link the discrete and the continuous dynamics by considering them as instances of the same strong Markov process with different initial conditions. We construct this pruning process on the space of so-called bi-measure trees, which are metric measure spaces with an additional pruning measure. The pruning measure is assumed to be finite on finite trees, but not necessarily locally finite. We also characterize the pruning process analytically via its Markovian generator and show that it is continuous in the initial bi-measure tree. A series of examples is given, which include the finite variance offspring case where the pruning measure is the length measure on the underlying tree.

Mots clés : tree-valued Markov process, CRT, real trees, pruning procedure, pointed Gromov-weak topology, prohorov metric, non-locally finite measures

[1] R. Abraham and J.-F. Delmas. Fragmentation associated with Lévy processes using snake. Probab. Theory Related Fields 141 (2008) 113–154. | DOI | MR | Zbl

[2] R. Abraham and J.-F. Delmas. A continuum-tree-valued Markov process. Ann. Probab. 40 (3) (2012) 1167–1211. | MR | Zbl

[3] R. Abraham and J.-F. Delmas. Record process on the continuum random tree. ALEA Lat. Am. J. Probab. Math. Stat. 10 (1) (2013) 225–251. | MR | Zbl

[4] R. Abraham, J.-F. Delmas and H. He. Pruning Galton–Watson trees and tree-valued Markov process. Ann. Inst. Henri Poincaré Probab. Stat. 48 (3) (2012). | EuDML | Numdam | MR | Zbl

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

[6] R. Abraham, J.-F. Delmas and P. Hoscheit. Exit times for an increasing Lévy tree-valued process. Probab. Theory Related Fields 159 (1–2) (2014) 357–403. | MR | Zbl

[7] R. Abraham, J.-F. Delmas and G. Voisin. Pruning a Lévy continuum random tree. Electron. J. Probab. 15 (46) (2010) 1429–1473. | MR | Zbl

[8] R. Abraham and L. Serlet. Poisson snake and fragmentation. Electron. J. Probab. 7 (2002) 1–15. | DOI | EuDML | MR | Zbl

[9] D. Aldous. The continuum random tree I. Ann. Probab. 19 (1991) 1–28. | DOI | MR | Zbl

[10] D. Aldous. The continuum random tree III. Ann. Probab. 21 (1993) 248–289. | DOI | MR | Zbl

[11] D. Aldous and J. Pitman. The standard additive coalescent. Ann. Probab. 26 (4) (1998) 1703–1726. | MR | Zbl

[12] D. Aldous and J. Pitman. Tree-valued Markov chains derived from Galton–Watson processes. Ann. Inst. Henri. Poincaré Probab. Stat. 34 (5) (1998) 637–686. | Numdam | MR | Zbl

[13] S. Athreya, W. Löhr and A. Winter. The gap between Gromov-vague and Gromov–Hausdorff-vague topology. Preprint, 2014. Available at arXiv:1407.6309. | MR | Zbl

[14] J. Bertoin. Fires on trees. Ann. Inst. Henri Poincaré Probab. Stat. 48 (4) (2012) 909–921. | Numdam | MR | Zbl

[15] J. Bertoin and G. Miermont. The cut-tree of large Galton–Watson trees and the Brownian CRT. Ann. Appl. Probab. 23 (4) (2013) 1469–1493. | MR | Zbl

[16] P. Billingsley. Convergence of Probability Measures. Wiley, New York, 1999. | DOI | MR | Zbl

[17] D. Blount and M. A. Kouritzin. On convergence determining and separating classes of functions. Stochastic Process. Appl. 120 (10) (2010) 1898–1907. | MR | Zbl

[18] V. I. Bogachev. Measure Theory, Vol. I. Springer, Berlin, 2007. | DOI | MR | Zbl

[19] D. Burago, Y. Burago and S. Ivanov. A Course in Metric Geometry. Graduate Studies in Mathematics 33. Amer. Math. Soc., Providence, RI, 2001. | DOI | MR | Zbl

[20] N. Curien and B. Haas. The stable trees are nested. Probab. Theory Related Fields 157 (2012) 847–883. | DOI | MR | Zbl

[21] A. Depperschmidt, A. Greven and P. Pfaffelhuber. Marked metric measure spaces. Electron. Commun. Probab. 16 (2011) 174–188. | DOI | MR | Zbl

[22] A. W. M. Dress and W. F. Terhalle. The real tree. Adv. Math. 120 (1996) 283–301. | DOI | MR | Zbl

[23] A. W. M. Dress, V. Moulton and W. F. Terhalle. T-theory: An overview. European J. Combin. 17 (2–3) (1996). | MR | Zbl

[24] M. Dromota, A. Iksanov, M. Mohle and U. Rosler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms 34 (2009) 319–336. | DOI | MR | Zbl

[25] R. M. Dudley. Real Analysis and Probability. Cambridge Univ. Press, Cambridge, 2002. | MR | Zbl

[26] T. Duquesne. A limit theorem for the contour process of conditioned Galton–Watson trees. Ann. Probab. 31 (2) (2003) 996–1027. | MR | Zbl

[27] T. Duquesne and J.-F. Le Gall. Random trees, Lévy processes and spatial branching processes. Astérisque 281 (2002) vi+147. | Numdam | MR | Zbl

[28] S. N. Ethier and T. Kurtz. Markov Processes. Characterization and Convergence. Wiley, New York, 1986. | MR | Zbl

[29] S. N. Evans. Probability and real trees. In École d’Été de Probabilités de Saint Flour XXXV-2005. Lecture Notes in Mathematics 1920. Springer, Berlin. 2007. | MR | Zbl

[30] S. N. Evans and A. Winter. Subtree prune and re-graft: A reversible real-tree valued Markov chain. Ann. Probab. 34 (3) (2006) 918–961. | MR | Zbl

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

[32] K. Fukaya. Collapsing of Riemannian manifolds and eigenvalues of Laplace operator. Invent. Math. 87 (3) (1987) 517–547. | MR | Zbl

[33] A. Greven, P. Pfaffelhuber and A. Winter. Convergence in distribution of random metric measure spaces1–2) (2009) 285–322. | MR | Zbl

[34] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics 152. Birkhäuser, Boston, MA, 1999. | MR | Zbl

[35] J. Hoffmann-Jørgensen. Probability in Banach spaces. In École d’Été de Probabilités de Saint Flour VI-1976. Lecture Notes in Mathematics 598. Springer, Berlin, 1977. | MR | Zbl

[36] C. Holmgren. Random records and cuttings in binary search trees. Combin. Probab. Comput. 19 (2010) 391–424. | DOI | MR | Zbl

[37] S. Janson. Random cuttings and records in deterministic and random trees. Random Structures Algorithms 29 (2006) 139–179. | DOI | MR | Zbl

[38] L. Le Cam. Convergence in distribution of stochastic processes. Univ. Calif. Publ. Statist. 2 (1957) 207–236. | MR | Zbl

[39] W. Löhr. Equivalence of Gromov–Prohorov- and Gromov’s ${\underline{\square }}_{\lambda }$-metric on the space of metric measure spaces. Electron. Commun. Probab. 18 (2013) no. 17, 10. | MR | Zbl

[40] R. Lyons. Random walks, capacities, and percolation on trees. Ann. Probab. 20 (1992) 2043–2088. | MR | Zbl

[41] A. Meir and J. W. Moon. Cutting down random trees. J. Aust. Math. Soc. 11 (1970). | MR | Zbl

[42] G. Miermont. Self-similar fragmentations derived from the stable tree I: Splitting at heights. Probab. Theory Related Fields 127 (2003) 423–454. | DOI | MR | Zbl

[43] G. Miermont. Self-similar fragmentations derived from the stable tree II: Splitting at nodes. Probab. Theory Related Fields 131 (2005) 341–375. | DOI | MR | Zbl

[44] G. Miermont. Tessellations of random maps of arbitrary genus. Ann. Sci. Ec. Norm. Super. (4) 42 (2009) 725–781. | Numdam | MR | Zbl

[45] A. Panholzer. Cutting down very simple trees. Quaest. Math. 29 (2006) 211–227. | DOI | MR | Zbl

[46] C. Villani. Optimal Transport. Grundlehren der Mathematischen Wissenschaften 338. Springer, Berlin, 2009. | DOI | MR | Zbl

[47] G. Voisin. Dislocation measure of the fragmentation of a general Lévy tree. ESAIM Probab. Stat. 15 (2011) 372–389. | DOI | Numdam | MR | Zbl