Abstract.
We consider generalizations of the classical Polya urn problem: Given finitely many bins each containing one ball, suppose that additional balls arrive one at a time. For each new ball, with probability p, create a new bin and place the ball in that bin; with probability 1−p, place the ball in an existing bin, such that the probability that the ball is placed in a bin is proportional to $ m^\gamma $, where m is the number of balls in that bin. For p=0, the number of bins is fixed and finite, and the behavior of the process depends on whether γ is greater than, equal to, or less than 1. We survey the known results and give new proofs for all three cases. We then consider the case p>0. When γ=1, this is equivalent to the so-called preferential attachment scheme which leads to power law distribution for bin sizes. When γ>1, we prove that a single bin dominates, i.e., as the number of balls goes to infinity, the probability that any new ball either goes into that bin or creates a new bin converges to 1. When p > 0 and γ < 1, we show that under the assumption that certain limits exist, the fraction of bins having m balls shrinks exponentially as a function of m. We then discuss further generalizations and pose several open problems.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS Subject Classification: 05D40, 60C05, 60G20, 68R10, 91C99.
Rights and permissions
About this article
Cite this article
Chung, F., Handjani, S. & Jungreis, D. Generalizations of Polya's urn Problem. Ann. Combin. 7, 141–153 (2003). https://doi.org/10.1007/s00026-003-0178-y
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00026-003-0178-y