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

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

  • Author(s): Aldous, D
  • Shields, P
  • et al.
Abstract

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 Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View