Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine you have $N$ empty bins. At every timestep $t$ you throw a ball to a randomly chosen bin ($t$ is therefore also the total number of balls in this system). Probability that a ball falls into a bin $i$ is proportional to the number of balls already in the bin $k_i$ , plus some initial conditions. So the bins get "wider" as more balls falls into them. I want to find distribution of the balls $P_t: t \rightarrow \infty$

$P_t \propto k_i + A$ , where $k_i$ is the number of the balls in the bin $i$ and $A$ is some constant (initial conditions)

$P_{0}(k_i) = {1 \over{N}}$

so I think that

$P_t(k_i) = {{k_{i-1}+A}\over{NA+\sum_jk_j}}$

How to find the distribution for $t \rightarrow \infty $ ?


Preferential attachment

Rich get richer

share|improve this question
Crossposted on Math.SE: math.stackexchange.com/questions/102899 –  Rasmus Bentmann Jan 27 '12 at 8:15
add comment

1 Answer 1

Your problem can be studied via urn models. Take the case with N=2, two boxes. The initial number of balls in each box is (R,B) (Red, Blue), both integers larger or equal too one. At each round, you draw randomly a ball from one of the boxes with equal probability for each ball. Then you put the drawn ball back, and add one more copy! of the same color to the same box. So note that the probabilities of (Red, or Blue) is changing at each round.

This is called the Polya-Eggenburger urn scheme, and a book-length treatment of this and other urn models is in "Polya's Urn Models", by Hosam M Mahmoud.

This model is interesting (proposed as a model for eṕidemics!) as the limiting distribution depends crucially on the initial condition (R,B). The limiting distribution of proportion of balls is Beta(R,B), a result which is proved in the above mentioned reference. Googling "Polya urn models" will give you a lot of information.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.