<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
Generalizations of Polya's urn Problem
Fan Chung1, Shirin Handjani2, and Doug Jungreis2
1Department of Mathematics, University of California, San Diego, La Jolla, CA 92093, USA
2Center for Communications Research, IDA, 4320 Westerra Court, San Diego, CA 92121, USA
shandjan@math.ucsd.edu, jungreis@ccrwest.org
Annals of Combinatorics 7 (2) p.141-153 June, 2003
AMS Subject Classification: 05D40, 60C05, 60G20, 68R10, 91C99
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 , 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.
Keywords: balls and bins, power law, positive feedback, web models


1. R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002) 47每97.

2. B. Arthur, Increasing Returns and Path Dependence in the Economy, The University of Michigan press, 1994.

3. B. Arthur, Y. Ermoliev, and Y. Kaniovski, On generalized urn schemes of the Polya kind, English Translation in Cybernetics 19 (1963) 61每71.

4. A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509每512.

5. P. Diaconis, Recent progress on de Finetti's notions of exchangeability, Bayesian Statist. 3 (1987) 111每125.

6. E. Drinea, M. Enachescu, and M. Mitzenmacher, Variations on random graph models for the web, Harvard Technical Report, TR-06-01.

7. E. Drinea, A. Frieze, and M. Mitzenmacher, Balls and bins models with feedback, SODA 2002.

8. N. Johnson and S. Kotz, Urn Models and Their Applications: An Approach to Modern Discrete Probability Theory, Wiley, New York, 1977.

9. P.L. Krapivsky and S. Redner, Organization of growing random networks, Physica A 281 (2000) 69每77.

10. R. Pemantle, Vertex-reinforced random walks, Probab. Theory Related Fields 92 (1992) 117每136.

11. R. Pemantle and S. Volkov, Vertex-reinforced random walk on Z has finite range, Ann. Probab. 27 (1999) 1368每1388.

12. C. Shapiro and H. R. Varian, Information Rules, Harvard Business School Press, Boston, MA, 1999.

13. J. Spencer and N. Wormald, Explosive processes, manuscript.