𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A family of random trees with random edge lengths

✍ Scribed by David Aldous; Jim Pitman

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
212 KB
Volume
15
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

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 interpretation is given in terms of sampling from the inhomogeneous continuum random tree of Aldous and Pitman (1998).

πŸ“œ SIMILAR VOLUMES

A study of random Weyl trees
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

On finding a minimum spanning tree in a
On finding a minimum spanning tree in a network with random weights
✍ Colin McDiarmid; Theodore Johnson; Harold S. Stone πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 221 KB πŸ‘ 1 views

We investigate Prim's standard ''tree-growing'' method for finding a minimum spanning tree, when applied to a network in which all degrees are about d and the edges e Ε½ . have independent identically distributed random weights w e . We find that when the kth ' Ε½ . edge e is added to the current tree

Tiny families of functions with random p
Tiny families of functions with random properties: A quality-size trade-off for hashing
✍ Oded Goldreich; Avi Wigderson πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 298 KB πŸ‘ 1 views

We present three explicit constructions of hash functions, which exhibit a Ε½ trade-off between the size of the family and hence the number of random bits needed to . Ε½ . generate a member of the family , and the quality or error parameter of the pseudorandom property it achieves. Unlike previous con

On a random graph with immigrating verti
On a random graph with immigrating vertices: Emergence of the giant component
✍ David J. Aldous; Boris Pittel πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 186 KB πŸ‘ 1 views

A randomly evolving graph, with vertices immigrating at rate n and each possible edge appearing at rate 1/n, is studied. The detailed picture of emergence of giant components with O n 2/3 vertices is shown to be the same as in the ErdΕ‘s-RΓ©nyi graph process with the number of vertices fixed at n at t