Löhr, Wolfgang; Voisin, Guillaume; Winter, Anita
Convergence of bi-measure -trees and the pruning process
Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 4 , p. 1342-1368
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consulter l'article sur le site de la revue
MR 3414450
doi : 10.1214/14-AIHP628
URL stable : http://www.numdam.org/item?id=AIHPB_2015__51_4_1342_0

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.

Bibliographie

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

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

[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 3083925 | Zbl 1277.60136

[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). Numdam | MR 2976559 | Zbl 1256.60028

[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 3035742 | Zbl 1285.60004

[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 3201925 | Zbl 1302.60077

[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 2727317 | Zbl 1231.60073

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

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

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

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

[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 1641670 | Zbl 0917.60082

[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.

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

[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 3098439 | Zbl 1279.60035

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

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

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

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

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

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

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

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

[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. MR 2504401 | Zbl 1187.05068

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

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

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

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

[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 2351587 | Zbl 1139.60006

[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 2243874 | Zbl 1101.60054

[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 2221786 | Zbl 1086.60050

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

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

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

[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 461610 | Zbl 0385.60006

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

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

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

[39] W. Löhr. Equivalence of Gromov–Prohorov- and Gromov’s ̲ λ -metric on the space of metric measure spaces. Electron. Commun. Probab. 18 (2013) no. 17, 10. MR 3037215 | Zbl 06346866

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

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

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

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

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

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

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

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