Author

• Hosam M. Mahmoud

Abstract

This paper reviews P´olya urn models and their connection to random trees. Basic results are presented, together with proofs that underly the historical evolution of the accompanying thought process. Extensions and generalizations are given according to chronology:
• P´olya-Eggenberger’s urn
• Bernard Friedman’s urn
• Generalized P´olya urns
• Extended urn schemes
• Invertible urn schemes
Connections to random trees are surveyed. Numerous applications to trees common in computer science are discussed, including:
• Binary search trees
• Fringe-balanced trees
• m-ary search trees
• 2–3 trees
• Paged binary trees
• Bucket quad trees
• Bucket k–d trees
The applications also include various types of recursive trees:
• Standard recursive trees
• Pyramids
• Plane-oriented recursive trees
• Phylogenetic trees
• Bucket recursive trees
• Sprouts
Limit distributions, and phase changes therein are presented within the unifying theme of P´olya urn models.

Keywords

• P´olya urns
• Poissonization
• random trees
• stochastic process