UC Berkeley

Binary trees are grown by adding one node at a time, an available node at height i being added with probability proportional to c-i, c>1. We establish both a "strong law of large numbers" and a "central limit theorem" for the vector X(t)=(Xi(t)), where Xi(t) is the proportion of nodes of height i that are available at time t. We show, in fact, that there is a deterministic process xi(t) such that {Mathematical expression} and such that if c2 {Mathematical expression}, {Mathematical expression} and Zn(t)=(Zin(t)), then Zn(t) converges weakly to a Gaussian diffusion Z(t). The results are applied to establish asymptotic normality in the unbiased coin-tossing case for an entropy estimation procedure due to J. Ziv, and to obtain results on the growth of the maximum height of the tree. © 1988 Springer-Verlag.