A diffusion limit for a class of randomly-growing binary trees (Q1100799)

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)=(X_ i(t))\), where \(X_ i(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 \(x_ i(t)\) such that \[ \sum | X_ i(t)-x_ i(t)| \quad converges\quad to\quad 0\quad a.s., \] and such that if \(c>2^{1/2}\), \[ Z\quad n_ i(t)=2^{n/2}\{X_{n+i}(tc\quad n)-x_{n+i}(tc\quad n)),\quad and\quad Z\quad n(t)=(Z\quad n_ i(t)), \] then Z n(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.