We study three rules for the development of a sequence of finite subtrees ₙ\ of an infinite m-ary tree t. Independent realizations \ω(n)\ of a stationary ergodic process \ω\ on m letters are used to trace out paths in t. In the first rule, tₙ is formed by adding a node to tn - 1 at the first location where the path defined by ω (n) leaves tn - 1. The second and third rules are similar, but more complicated. For each rule, the height Lₙ 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ₙLₙ/ln n = σ₁, lim ₙ Lₙ/ln n = σ₂ a.s., where the constants σ₁, σ₂, are, in general, different, depend on the rule in use, and σ₁ < 1/h < σ₂. It is proven along the way that the height of tₙ grows as σ₂ln n with probability one.
No takes yet. Share an insight, caveat, or question.
Boris Pittel (1985) studied this question.