Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

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


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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View