Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-18T02:21:08.824Z Has data issue: false hasContentIssue false
  • English
  • Français

Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains

Published online by Cambridge University Press:  27 July 2009

David Aldous ,
Barry Flannery  and
José Luis Palacios
David Aldous
Affiliation:
Department of StatisticsUniversity of California Berkeley, California 94720
Barry Flannery
Affiliation:
Department of Mathematics and Computer Science Valdosta State College Valdosta, Georgia 31698
José Luis Palacios
Affiliation:
Universidad Simón Bolívar, Departamento de Matemáticas y C. C. Apartado 89.000 Caracas, Venezuela
Get access Rights & Permissions [Opens in a new window]

Abstract

From an urn containing colored balls, one ball is drawn and replaced by a random number of differently colored balls, with the distribution of the added balls depending only on the color of the ball drawn. Under mild regularity conditions, the proportions of different colors will converge to deterministic limits. Two applications of this standard result are described.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 2 , Issue 3 , July 1988 , pp. 293 - 307
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Athreya, K. & Ney, P. (1972). Branching processes. New York: Springer-Verlag.CrossRefGoogle Scholar
Bagchi, A. & Pal, A.K. (1985). Asymptotic normality in the generalized Polya-Eggenberger-Urn model, with an application to computer data structures. SIAM Journal of Algebraic and Discrete Methods 6:394–405.CrossRefGoogle Scholar
Cunto, W. & Gascón, J.L. (1987). Improving time and space efficiency in generalized binary search trees. Acta Informatica 24: 583–594.CrossRefGoogle Scholar
Darroch, J. & Seneta, E. (1965). On quasi-stationary distributions in absorbing discrete-time finite Markov chains. Journal of Applied Probability 2: 88–100.CrossRefGoogle Scholar
Devroye, L. (1987). Branching processes in the analysis of the heights of trees. Acta Informatica 24: 277–298.CrossRefGoogle Scholar
Eisenbarth, B., Ziviani, N., Gonnet, O., Mehlhorn, K., & Wood, D. (1982). The theory of fringe analysis and its application to 2–3 trees and B-trees. Information and Control 55: 125–174.CrossRefGoogle Scholar
Flannery, B. (1986). On quasi-stationary distributions of Markov chains. Ph.D. dissertation, Department of Statistics, University of California, Berkeley.Google Scholar
Knuth, D. (1973). The art of computer programming, Vol. 3. Reading: Addison-Wesley.Google Scholar
Poblete, P. & Munro, J. (1985). The analysis of a fringe heuristic for binary search trees. Journal of Algorithms 6: 336–350.CrossRefGoogle Scholar
Yao, A. (1978). On random 2–3 trees. Acta Informatica 9: 159–170.CrossRefGoogle Scholar