A Note on the Probability of Cutting a Galton-Watson Tree

Luc Devroye (McGill University)


The structure of Galton-Watson trees conditioned to be of a given size is well-understood. We provide yet another embedding theorem that permits us to obtain asymptotic probabilities of events that are determined by what happens near the root of these trees. As an example, we derive the probability that a Galton-Watson tree is cut when each node is independently removed with probability p, where by cutting a tree we mean that every path from root to leaf must have at least one removed node.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 2001-2019

Publication Date: October 24, 2011

DOI: 10.1214/EJP.v16-952


  1. Aldous, David. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228--266. MR1102319 (92j:60009)
  2. Aldous, David; Pitman, Jim. Tree-valued Markov chains derived from Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998), no. 5, 637--686. MR1641670 (2000c:60130)
  3. Athreya, Krishna B.; Ney, Peter E. Branching processes.Die Grundlehren der mathematischen Wissenschaften, Band 196.Springer-Verlag, New York-Heidelberg, 1972. xi+287 pp. MR0373040 (51 #9242)
  4. V. Campos. V. Chvatal. L. Devroye. and P. Taslakian. Transversals in trees. Journal of Graph Theory To appear.
  5. L. Devroye. Branching processes in the analysis of the heights of trees. Acta Informatica 24 (1987), 277--298.
  6. Devroye, Luc. Universal limit laws for depths in random trees. SIAM J. Comput. 28 (1999), no. 2, 409--432 (electronic). MR1634354 (2000e:68073)
  7. Duquesne, Thomas. An elementary proof of Hawkes's conjecture on Galton-Watson trees. Electron. Commun. Probab. 14 (2009), 151--164. MR2497323 (2010e:60184)
  8. Dwass, Meyer. The total progeny in a branching process and a related random walk. J. Appl. Probability 6 1969 682--686. MR0253433 (40 #6648)
  9. J. D. Farley. Breaking al Qaeda cells: a mathematical analysis of counterterrorism operations. Studies in Conflict and Terrorism 26 (2003), 399--411.
  10. J. D. Farley. Toward a Mathematical Theory of Counterterrorism How to Build the Perfect Terrorist Cell, I (2007) Technical Report, Center fo International Security and Cooperation, Stanford University.
  11. Flajolet, Philippe; Odlyzko, Andrew. The average height of binary trees and other simple trees. J. Comput. System Sci. 25 (1982), no. 2, 171--213. MR0680517 (84a:68056)
  12. Flajolet, Philippe; Sedgewick, Robert. Analytic combinatorics.Cambridge University Press, Cambridge, 2009. xiv+810 pp. ISBN: 978-0-521-89806-5 MR2483235 (2010h:05005)
  13. Geiger, Jochen; Kauffmann, Lars. The shape of large Galton-Watson trees with possibly infinite variance. Random Structures Algorithms 25 (2004), no. 3, 311--335. MR2086163 (2005i:60166)
  14. C. Holmgren. Split Trees, Cuttings and Explosions (2010) Ph.D. dissertation, Uppsala University.
  15. Ibragimov, I. A. On the accuracy of approximation by the normal distribution of distribution functions of sums of independent random variables.(Russian) Teor. Verojatnost. i Primenen 11 1966 632--655. MR0212853 (35 #3718)
  16. Janson, Svante. Random records and cuttings in complete binary trees. Mathematics and computer science. III, 241--253, Trends Math., Birkhäuser, Basel, 2004. MR2090513 (2005i:05034)
  17. Janson, Svante. Random cutting and records in deterministic and random trees. Random Structures Algorithms 29 (2006), no. 2, 139--179. MR2245498 (2007k:05200)
  18. Janson, Svante. Conditioned Galton-Watson trees do not grow. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 331--334, Discrete Math. Theor. Comput. Sci. Proc., AG, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006. MR2509643 (2010h:05275)
  19. Kennedy, Douglas P. The Galton-Watson process conditioned on the total progeny. J. Appl. Probability 12 (1975), no. 4, 800--806. MR0386042 (52 #6901)
  20. V. F. Kolchin. Branching Processes and random trees. Problems in Cybernetics, Combinatorial Analysis and Graph Theory (in Russian) (1980), 85--97. Nauka. Moscow.
  21. Kolchin, Valentin F. Random mappings.Translated from the Russian.With a foreword by S. R. S. Varadhan.Translation Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York, 1986. xiv + 207 pp. ISBN: 0-911575-16-2 MR0865130 (88a:60022)
  22. Le Gall, Jean-François. Marches aléatoires, mouvement brownien et processus de branchement.(French) [Random walks, Brownian motion and branching processes] Séminaire de Probabilités, XXIII, 258--274, Lecture Notes in Math., 1372, Springer, Berlin, 1989. MR1022916 (91e:60241)
  23. Lyons, Russell; Pemantle, Robin; Peres, Yuval. Conceptual proofs of $L\log L$ criteria for mean behavior of branching processes. Ann. Probab. 23 (1995), no. 3, 1125--1138. MR1349164 (96m:60194)
  24. Meir, A.; Moon, J. W. On the altitude of nodes in random trees. Canad. J. Math. 30 (1978), no. 5, 997--1015. MR0506256 (80k:05043)
  25. Moon, J. W. Counting labelled trees.From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, 1969). Canadian Mathematical Monographs, No. 1 Canadian Mathematical Congress, Montreal, Que. 1970 x+113 pp. MR0274333 (43 #98)
  26. Neveu, J.; Pitman, J. W. The branching process in a Brownian excursion. Séminaire de Probabilités, XXIII, 248--257, Lecture Notes in Math., 1372, Springer, Berlin, 1989. MR1022915 (91e:60240)
  27. V. V. Petrov. Sums of Independent Random Variables (1975) Springer-Verlag. Berlin.
  28. Rouault, Alain. Lois empiriques dans les processus de branchement spatiaux homogènes supercritiques.(French) C. R. Acad. Sci. Paris Sér. I Math. 292 (1981), no. 20, 933--936. MR0625371 (82f:60188)
  29. Spitzer, Frank. Principles of random walks.Second edition.Graduate Texts in Mathematics, Vol. 34.Springer-Verlag, New York-Heidelberg, 1976. xiii+408 pp. MR0388547 (52 #9383)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.