Number of complete N-ary subtrees on Galton-Watson family trees

DOI10.1007/S11009-006-8549-6MaRDI QIDQ2433261zbMATH OpenOpenAlexFDO

Authors George P. Yanev, Ljuben Mutafchiev

Publication date 27 October 2006

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0601585

zbMATH Keywords

\(N\)-ary treebinary treebranching process

Mathematics Subject Classification ID

Trees (05C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: We associate with a Bienayme-Galton-Watson branching process a family tree rooted at the ancestor. For a positive integer N, define a complete N-ary tree to be the family tree of a deterministic branching process with offspring generating function s^N. We study the random variables V(N,n) and V(N) counting the number of disjoint complete N-ary subtrees, rooted at the ancestor, and having height n and infinity, respectively. Dekking (1991) and Pakes and Dekking (1991) find recursive relations for Pr(V(N,n)>0) and Pr(V(N)>0) involving the offspring probability generation function (pgf) and its derivatives. We extend their results determining the probability distributions of V(N,n) and V(N). It turns out that they can be expressed in terms of the offspring pgf, its derivatives, and the above probabilities. We show how the general results simplify in case of fractional linear, geometric, Poisson, and one-or-many offspring laws.

Recommendations

• Survival probabilities for N-ary subtrees on a Galton-Watson family tree
• On family trees and subtrees of simple branching processes
• A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees
• On the number of vertices with a given degree in a Galton-Watson tree
• Non-fringe subtrees in conditioned Galton-Watson trees

Cites work

• Branching Processes That Grow Faster Than Binary Splitting
• Connectivity properties of Mandelbrot's percolation process
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• On family trees and subtrees of simple branching processes
• Percolation of arbitrary words in \(\{0, 1\}^ \mathbb{N}\)
• Phase transition in reinforced random walk and RWRE on trees

Cited in

(3)

• Note on the number of rooted complete N-ary trees.
• Survival probabilities for N-ary subtrees on a Galton-Watson family tree
• On family trees and subtrees of simple branching processes

This page was built for publication: Number of complete \(N\)-ary subtrees on Galton-Watson family trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433261)