Volume 2, Issue 1 (March 2003)                   JIRSS 2003, 2(1): 53-114 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Mahmoud H M. P´olya Urn Models and Connections to Random Trees: A Review. JIRSS. 2003; 2 (1) :53-114
URL: http://jirss.irstat.ir/article-1-94-en.html
Abstract:   (13731 Views)
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.
Full-Text [PDF 370 kb]   (4732 Downloads)    

Received: 2011/08/26 | Accepted: 2015/09/12 | Published: 2003/03/15

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Journal of The Iranian Statistical Society