✦ LIBER ✦

On the profile of random trees

✍ Scribed by Michael Drmota; Bernhard Gittenberger

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 302 KB
Volume: 10
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199707)10:4<421::aid-rsa2>3.0.co;2-w

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processes converge weakly to Brownian excursion local time. This is done via characteristic functions obtained by means of generating functions arising from the combinatorial setup and complex contour integration. Besides, an integral representation for the two-dimensional density of Brownian excursion local time is derived. ᮊ 1997

📜 SIMILAR VOLUMES

On the log-product of the subtree-sizes

On the log-product of the subtree-sizes of random trees

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 2 views

We determine the asymptotic behavior of the expected value and the variance of the log-product of the subtree-sizes of trees T belonging to simply generated families of n

A study of random Weyl trees

✍ Luc Devroye; Amar Goudjil 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

We study binary search trees constructed from Weyl sequences n , n G 1, Ä 4 where is an irrational and и denotes ''mod 1.'' We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of . If H is n w x the height of the tree with n nodes when i

A family of random trees with random edg

A family of random trees with random edge lengths

✍ David Aldous; Jim Pitman 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB 👁 1 views

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas for distributions of quantities such as degree sequence, shape, and total length are derived. An interp

On the complexity of branch-and-bound se

On the complexity of branch-and-bound search for random trees

✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

Addendum to “On the log-product of the s

Addendum to “On the log-product of the subtree-sizes of random trees”

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 1 views

The asymptotic behavior of the mean and the variance of the log-product of the subtree-sizes of trees belonging to simply generated families of rooted trees were determined in this paper. The authors have learned that Professor Boris Pittel, in a manuscript entitled ''Normal Convergence Problem? Two

The distribution of nodes of given degre

The distribution of nodes of given degree in random trees

✍ Drmota, Michael; Gittenberger, Bernhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 391 KB 👁 1 views

Let T n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ µ k n and variance ∼ σ 2 k n with positive constants µ