Asymptotical growth of a class of random trees
type: Item
instance of: scholarly article
title: Asymptotical growth of a class of random trees
zbMATH Open document ID: 0563.60010
published in: The Annals of Probability
publication date: 1985-01-01T00:00:00Z
review text: We study three rules for the development of a sequence of finite subtrees \(\{t_ n\}\) of an infinite m-ary tree t. Independent realizations \(\{\) w(n)\(\}\) of a stationary ergodic process \(\{\) \(w\}\) on m letters are used to trace out paths in t. In the first rule, \(t_ n\) is formed by adding a node to \(t_{n-1}\) at the first location where the path defined by \(\omega\) (n) leaves \(t_{n-1}\). The second and third rules are similar, but more complicated. For each rule, the height \(L_ n\) of the added node is shown to grow, in probability, as ln n divided by h the entropy per symbol of the generic process. A typical retrieval time has the same behavior. On the other hand, lim inf\({}_ nL_ n/\ln n=\sigma_ 1\), lim sup\({}_ nL_ n/\ln n=\sigma_ 2\) a.s., where the constants \(\sigma_ 1\), \(\sigma_ 2\), are, in general, different, depend on the rule in use, and \(\sigma_ 1<1/h<\sigma_ 2\). It is proved along the way that the height of \(t_ n\) grows as \(\sigma_ 2\ln n\) with probability one.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60F15
Mathematics Subject Classification ID: 28D20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3897906
zbMATH Keywords: random trees
zbMATH Keywords: lengths of the paths
zbMATH Keywords: ergodic process
zbMATH Keywords: asymptotic growth
zbMATH Keywords: strong, weak convergence
author: Boris Pittel
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1176993000
OpenAlex ID: W2091851562
Wikidata QID: Q56688556
DOI: 10.1214/AOP/1176993000
description: scientific article; zbMATH DE number 3897906