A note on the probability of cutting a Galton-Watson tree. (English) Zbl 1244.60087

Devroye, Luc

Electron. J. Probab. 16, Paper No. 72, 2001-2019 (2011).

Summary: 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.

MSC:

60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
60J85	Applications of branching processes
60G99	Stochastic processes

Keywords:

random Galton-Watson tree; probabilistic analysis of algorithms; branching process