A strong law for the height of random binary pyramids (Q1336596)

A random binary pyramid is a tree which grows according to the following rule: each new birth is equally likely to be to any one of the nodes which have not already produced two daughters. If \(h_ n\) denotes the height (maximum generation number) of the tree after \(n\) births, then this paper proves that \(h_ n/ \log_ en\) converges almost surely to a constant which is evaluated explicitly. The technique involves embedding the process in continuous time using suitable exponential random variables, yielding a general (Crump-Mode-Jagers) branching process, invoking Kingman's theorem on the first birth time in the \(k\)th generation of such a process, and then estimating the time of the \(n\)th birth using an ``ad hoc'' method. (These ideas are not new; see for instance \textit{B. Pittel} [J. Math. Anal. Appl. 103, 461-480 (1984; Zbl 0593.60014)] or \textit{L. Devroye} [Acta Inf. 24, 277-298 (1987; Zbl 0643.60065)]. It has emerged from discussions with J. D. Biggins that the asymptotics of the time of the \(n\)th birth follow easily from Nerman's theorem on the almost sure convergence of the normed supercritical general branching process, enabling a similar result to be obtained for a much more general model with fairly arbitrary rules for growing the tree, including the special cases which have been considered before).