Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-16T17:26:09.906Z Has data issue: false hasContentIssue false
  • English
  • Français

On the number of vertices with a given degree in a Galton-Watson tree

Part of: Markov processes Limit theorems Combinatorics Combinatorial probability

Published online by Cambridge University Press:  01 July 2016

Nariyuki Minami
Nariyuki Minami*
Affiliation:
University of Tsukuba
*
∗ Postal address: Institute of Mathematics, University of Tsukuba, Tsukuba 305-8571, Japan. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let Yk(ω) (k ≥ 0) be the number of vertices of a Galton-Watson tree ω that have k children, so that Z(ω) := ∑k≥0Yk(ω) is the total progeny of ω. In this paper, we will prove various statistical properties of Z and Yk. We first show, under a mild condition, an asymptotic expansion of P(Z = n) as n → ∞, improving the theorem of Otter (1949). Next, we show that Yk(ω) := ∑j=0kYj(ω) is the total progeny of a new Galton-Watson tree that is hidden in the original tree ω. We then proceed to study the joint probability distribution of Z and Ykk, and show that, as n → ∞, Yk/nk is asymptotically Gaussian under the conditional distribution P(· | Z = n).

Keywords

Galton-Watson treetotal progenyLagrange inversioncentral limit theorem

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.)
Secondary: 60C05: Combinatorial probability 05A15: Exact enumeration problems, generating functions 60F05: Central limit and other weak theorems
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 37 , Issue 1 , March 2005 , pp. 229 - 264
Copyright
Copyright © Applied Probability Trust 2005 

References

Aldous, D. (1991). The continuum random tree. II. An overview. In Stochastic Analysis (London Math. Soc. Lecture Notes Ser. 167), eds Barlow, M. T. and Bingham, N. H., Cambridge University Press, pp. 23–70.Google Scholar
Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Springer, New York.Google Scholar
Boyd, A. V. (1971). Formal power series and the total progeny in a branching process. J. Math. Anal. Appl. 34, 565–566.Google Scholar
Consul, P. C. and Shenton, L. R. (1972). Use of Lagrange expansion for generating discrete generalized probability distributions. SIAM J. Appl. Math. 23, 239–248.Google Scholar
Copson, E. T. (1965). Asymptotic Expansions. Cambridge University Press.Google Scholar
De Bruijn, N. G. (1981). Asymptotic Methods in Analysis. Dover, New York.Google Scholar
Dembo, A., Mörters, P. and Sheffield, S. (2003). A large-deviation theorem for tree-indexed Markov chains. Preprint ArXiv:math.PR/0306045, University of California, Davis.Google Scholar
Drmota, M. (2004). Combinatorics and asymptotics on trees. Cubo Mat. Educ. 6, 105–136.Google Scholar
Dwass, M. (1969). The total progeny in a branching process and a related random walk. J. Appl. Prob. 6, 682–686.Google Scholar
Good, I. J. (1949). The number of individuals in a cascade process. Proc. Camb. Phil. Soc. 45, 360–363.CrossRefGoogle Scholar
Good, I. J. (1960). Generalizations to several variables of Lagrange's expansion, with applications to stochastic processes. Proc. Camb. Phil. Soc. 56, 367–380.CrossRefGoogle Scholar
Good, I. J. (1975). The Lagrange distributions and branching processes. SIAM J. Appl. Math. 28, 270–275.CrossRefGoogle Scholar
Han, G. N. (1996). Démonstration combinatoire des formules de Prodinger concernant les arbres binaires. Séminaire Lotharingien de Combinatoire 38. Available at http://www.mat.univie.ac.at/∼slc/.Google Scholar
Harris, T. (1989). The Theory of Branching Processes. Dover, New York.Google Scholar
Hirsch, F. and Lacombe, G. (1999). Elements of Functional Analysis (Graduate Texts Math. 192). Springer, New York.Google Scholar
Hofbauer, J. (1982). Lagrange inversion. Séminaire Lotharingien de Combinatoire 6. Available at http://www.mat.univie.ac.at/∼slc/.Google Scholar
Jagers, P. (1975). Branching Processes with Biological Applications. John Wiley, London.Google Scholar
Kennedy, D. P. (1975). The Galton–Watson process conditioned on the total progeny. J. Appl. Prob. 12, 800–806.Google Scholar
Kesten, H. and Pittel, B. (1996). A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree. Random Structures Algorithms 8, 243–299.Google Scholar
Krattenthaler, C. (1996). Comment on ‘A note on the distribution of the three types of nodes in uniform binary trees’ by Helmut Prodinger. Séminaire Lotharingien de Combinatoire 38. Available at http://www.mat.univie.ac.at/∼slc/.Google Scholar
Kurata, K. and Minami, N. (2004). The equivalence of two constructions of Galton–Watson processes. Preprint mp_arc 04-295, Department of Mathematics, University of Texas at Austin. Available at http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=04-295.Google Scholar
Mahmoud, H. M. (1995). The Joint distribution of the three types of nodes in uniform binary trees. Algorithmica 13, 313–323.CrossRefGoogle Scholar
Neveu, J. (1986). Arbres et processus de Galton–Watson. Ann. Inst. H. Poincaré Prob. Statist. 22, 199–207.Google Scholar
Otter, R. (1949). The multiplicative processes. Ann. Math. Statist. 20, 206–224.Google Scholar
Prodinger, H. (1996). A note on the distribution of the three types of nodes in uniform binary trees. Séminaires Lotharingien de Combinatoire 38. Available at http://www.mat.univie.ac.at/∼slc/.Google Scholar
Rote, G. (1996). Binary trees having a given number of nodes with 0, 1, and 2 children. Séminaire Lotharingien de Combinatoire 38. Available at http://www.mat.univie.ac.at/∼slc/.Google Scholar
Sevast'yanov, B. A. (1971). Branching Processes. Nauka, Moscow (in Russian).Google Scholar
Tutte, W. T. (1964). The number of planted plane trees with a given partition. Amer. Math. Monthly 71, 272–277.Google Scholar