A diffusion limit for a class of randomly-growing binary trees
type: Item
instance of: scholarly article
title: A diffusion limit for a class of randomly-growing binary trees
zbMATH Open document ID: 0641.60026
DOI: 10.1007/BF00318784
author: David Aldous
author: Paul Shields
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 60J60
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 4044843
zbMATH Keywords: strong law of large numbers
zbMATH Keywords: central limit theorem
zbMATH Keywords: coin-tossing
zbMATH Keywords: entropy estimation
MaRDI profile type: Publication
cites work: Stopping times and tightness. II
cites work: Discounted branching random walks
cites work: Splitting intervals
cites work: Splitting intervals. II: Limit laws for lengths
cites work: Oriented percolation in two dimensions
cites work: Q3969647
cites work: Q4189915
cites work: A limit theorem for measurable random processes and its applications
cites work: Q5585020
cites work: A criterion for tightness for a sequence of martingales
cites work: On growing random binary trees
cites work: Asymptotical growth of a class of random trees
cites work: Paths in a random digital tree: limiting distributions
cites work: Q3218851
cites work: Coding theorems for individual sequences
cites work: A universal algorithm for sequential data compression
full work available at URL: https://doi.org/10.1007/bf00318784
OpenAlex ID: W2052638374
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article; zbMATH DE number 4044843