Polya Urn Models and Connections to Ran- dom Trees: A Review
Hosam M. Mahmoud · 2003
Abstract. This paper reviews Pólya urn models and their connec-tion 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 accord-ing to chronology: • Pólya-Eggenberger’s urn • Bernard Friedman’s urn • Generalized Pólya urns • Extended urn schemes • Invertible urn schemes Connections to random trees are surveyed. Numerous applications to trees common in computer science are discussed, including: