Volume 2, Number 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:   (9617 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]   (2424 Downloads)    
Subject: 60: Probability theory and stochastic processes
Received: 2011/08/26 | Accepted: 2015/09/12

Add your comments about this article : Your username or email:
Write the security code in the box

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