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's open access policies. Let us know how this access is important for you.

Main Content
Current View