Cutting down trees with a Markov chainsaw. (English) Zbl 1352.60009
Start with a rooted tree and at each step randomly remove an edge and keep only the part of the tree containing the root. Repeat until only the root is left. What is the random number of steps performed?
In this paper, the authors give new simpler proofs for the asymptotic distribution of the number of steps required for trees generated by various Galton-Watson-type processes. They also give a more precise non-asymptotic results for a particular type of such trees.
Finally, they also study a continuous version of this edge removal on the Brownian continuum random tree.
In this paper, the authors give new simpler proofs for the asymptotic distribution of the number of steps required for trees generated by various Galton-Watson-type processes. They also give a more precise non-asymptotic results for a particular type of such trees.
Finally, they also study a continuous version of this edge removal on the Brownian continuum random tree.
Reviewer: Demetres Christofides (Pyla)
MSC:
| 60C05 | Combinatorial probability |
| 05C05 | Trees |
| 60F17 | Functional limit theorems; invariance principles |
| 60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |
Keywords:
Galton-Watson tree; real tree; Brownian continuum random tree; Gromov-Hausdorff convergenceReferences:
| [1] | Abraham, R. and Delmas, J.-F. (2013). The forest associated with the record process on a Lévy tree. Stochastic Process. Appl. 123 3497-3517. · Zbl 1291.60172 · doi:10.1016/j.spa.2013.04.017 |
| [2] | Abraham, R. and Delmas, J.-F. (2013). Record process on the continuum random tree. ALEA Lat. Am. J. Probab. Math. Stat. 10 225-251. · Zbl 1277.60136 |
| [3] | Addario-Berry, L., Broutin, N. and Holmgren, C. (2010). Cutting down trees with a Markov chainsaw (with online slides). YEP VII Seminar (March 2010). . · Zbl 1352.60009 |
| [4] | Aldous, D. (1991). The continuum random tree. II. An overview. In Stochastic ( Durham , 1990) (M. T. Barlow and N. H. Bingham, eds.) 23-70. Cambridge Univ. Press, Cambridge. · Zbl 0791.60008 · doi:10.1017/CBO9780511662980.003 |
| [5] | Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228-266. · Zbl 0733.60016 · doi:10.1214/aoap/1177005936 |
| [6] | Aldous, D. (1991). The continuum random tree. I. Ann. Probab. 19 1-28. · Zbl 0791.60008 · doi:10.1214/aop/1176990534 |
| [7] | Aldous, D. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404 |
| [8] | Aldous, D. and Pitman, J. (1998). The standard additive coalescent. Ann. Probab. 26 1703-1726. · Zbl 0936.60064 · doi:10.1214/aop/1022855879 |
| [9] | Aldous, D. and Steele, J. M. (2003). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Discrete and Combinatorial Probability (H. Kesten, ed.) 1-72. Springer, Berlin. · Zbl 1037.60008 · doi:10.1007/978-3-662-09444-0_1 |
| [10] | Aldous, D. J. (1990). The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3 450-465. · Zbl 0717.05028 · doi:10.1137/0403039 |
| [11] | Aldous, D. J. and Pitman, J. (1994). Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 487-512. · Zbl 0811.60057 · doi:10.1002/rsa.3240050402 |
| [12] | Bertoin, J. (2006). Random Fragmentation and Coagulation Processes . Cambridge Univ. Press, Cambridge. · Zbl 1107.60002 · doi:10.1017/CBO9780511617768 |
| [13] | Bertoin, J. (2012). Fires on trees. In Annales de l’Institut Henri Poincaré , Probabilités et Statistiques 48 909-921. · Zbl 1263.60083 · doi:10.1214/11-AIHP435 |
| [14] | Bertoin, J. and Miermont, G. (2013). The cut-tree of large Galton-Watson trees and the Brownian CRT. Ann. Appl. Probab. 23 1469-1493. · Zbl 1279.60035 · doi:10.1214/12-AAP877 |
| [15] | Bertoin, J. and Pitman, J. (1994). Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 147-166. · Zbl 0805.60076 |
| [16] | Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201 |
| [17] | Broder, A. (1989). Generating random spanning trees. In 30 th Annual Symposium on Foundations of Computer Science 442-447. IEEE, New York. |
| [18] | Burago, D., Burago, Y. and Ivanov, S. (2001). A Course in Metric Geometry. Graduate Studies in Mathematics 33 . Amer. Math. Soc., Providence, RI. · Zbl 0981.51016 |
| [19] | Chassaing, P. and Marchand, R. (2009). Personal communication. |
| [20] | Daley, D. J. and Vere-Jones, D. (2007). An Introduction to the Theory of Point Processes. Vol. II : General Theory and Structure . Springer, New York. · Zbl 0657.60069 |
| [21] | Devroye, L. and Janson, S. (2011). Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees. Random Structures Algorithms 38 381-395. · Zbl 1223.05049 · doi:10.1002/rsa.20319 |
| [22] | Drmota, M., Iksanov, A., Moehle, M. and Roesler, U. (2009). A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms 34 319-336. · Zbl 1187.05068 · doi:10.1002/rsa.20233 |
| [23] | Fill, J. A., Kapur, N. and Panholzer, A. (2006). Destruction of very simple trees. Algorithmica 46 345-366. · Zbl 1106.68081 · doi:10.1007/s00453-006-0100-1 |
| [24] | Haas, B. and Miermont, G. (2012). Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab. 40 2589-2666. · Zbl 1259.60033 · doi:10.1214/11-AOP686 |
| [25] | Holmgren, C. (2008). Random records and cuttings in split trees: Extended abstract. In Fifth Colloquium on Mathematics and Computer Science . 269-281. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1355.68064 |
| [26] | Iksanov, A. and Möhle, M. (2007). A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Probab. 12 28-35. · Zbl 1133.60012 |
| [27] | Janson, S. (2004). Random records and cuttings in complete binary trees. In Mathematics and Computer Science. III : Algorithms , Trees , Combinatorics and Probability ( Vienna ) (M. Drmota, P. Flajolet, D. Gardy and B. Gittenberger, eds.) 241-253. Birkhäuser, Basel. · Zbl 1063.60018 · doi:10.1007/978-3-0348-7915-6_24 |
| [28] | Janson, S. (2006). Random cutting and records in deterministic and random trees. Random Structures Algorithms 29 139-179. · Zbl 1120.05083 · doi:10.1002/rsa.20086 |
| [29] | Kennedy, D. P. (1976). The distribution of the maximum Brownian excursion. J. Appl. Probab. 13 371-376. · Zbl 0338.60048 · doi:10.2307/3212843 |
| [30] | Kesten, H. (1986). Subdiffusive behavior of random walk on a random cluster. Ann. Inst. Henri Poincaré Probab. Stat. 22 425-487. · Zbl 0632.60106 |
| [31] | Kolchin, V. F. (1986). Random Mappings . Optimization Software Inc. Publications Division, New York. · Zbl 0605.60010 |
| [32] | Kuba, M. and Panholzer, A. (2008). Isolating a leaf in rooted trees via random cuttings. Ann. Comb. 12 81-99. · Zbl 1154.05019 · doi:10.1007/s00026-008-0338-1 |
| [33] | Kuba, M. and Panholzer, A. (2008). Isolating nodes in recursive trees. Aequationes Math. 76 258-280. · Zbl 1180.05031 · doi:10.1007/s00010-008-2929-7 |
| [34] | Le Gall, J.-F. (2005). Random trees and applications. Probab. Surv. 2 245-311. · Zbl 1189.60161 · doi:10.1214/154957805100000140 |
| [35] | Le Gall, J.-F. (2006). Random real trees. Ann. Fac. Sci. Toulouse Math. (6) 15 35-62. · Zbl 1129.60047 · doi:10.5802/afst.1112 |
| [36] | Lyons, R. and Peres, Y. (2012). Probability on trees and networks. Unpublished manuscript. · Zbl 1376.05002 |
| [37] | McDiarmid, C. (1998). Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed, eds.) 195-248. Springer, Berlin. · Zbl 0927.60027 · doi:10.1007/978-3-662-12788-9_6 |
| [38] | Meir, A. and Moon, J. W. (1970). The distance between points in random trees. J. Combin. Theory 8 99-103. · Zbl 0185.47001 · doi:10.1016/S0021-9800(70)80012-6 |
| [39] | Meir, A. and Moon, J. W. (1970). Cutting down random trees. J. Aust. Math. Soc. 11 313-324. · Zbl 0196.27602 · doi:10.1017/S1446788700006698 |
| [40] | Meir, A. and Moon, J. W. (1974). Cutting down recursive trees. Math. Biosci. 21 173-181. · Zbl 0288.05102 · doi:10.1016/0025-5564(74)90013-3 |
| [41] | Meir, A. and Moon, J. W. (1978). On the altitude of nodes in random trees. Canad. J. Math. 30 997-1015. · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0 |
| [42] | Miermont, G. (2009). Tessellations of random maps of arbitrary genus. Ann. Sci. Éc. Norm. Supér. (4) 42 725-781. · Zbl 1228.05118 |
| [43] | Panholzer, A. (2003). Noncrossing trees revisited: Cutting down and spanning subtrees. In Discrete Random Walks ( Paris , 2003) 265-276 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1073.60503 |
| [44] | Panholzer, A. (2006). Cutting down very simple trees. Quaest. Math. 29 211-227. · Zbl 1120.05020 · doi:10.2989/16073600609486160 |
| [45] | Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. · Zbl 1103.60004 · doi:10.1007/b11601500 |
| [46] | Riordan, J. (1968). Forests of labeled trees. J. Combin. Theory 5 90-103. · Zbl 0157.55001 · doi:10.1016/S0021-9800(68)80033-X |
| [47] | Stroock, D. W. (2011). Probability Theory. An Analytic View , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 1223.60001 · doi:10.1017/CBO9780511974243 |
| [48] | Villani, C. (2009). Optimal Transport : Old and New . Springer, Berlin. · Zbl 1156.53003 · doi:10.1007/978-3-540-71050-9 |
| [49] | Williams, D. (1991). Probability with Martingales . Cambridge Univ. Press, Cambridge. · Zbl 0722.60001 · doi:10.1017/CBO9780511813658 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
