Probability, preferential attachment, "rich get richer"

2012-01-27T06:56:59Z

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

Answer by Kjetil B Halvorsen for Probability, preferential attachment, "rich get richer"

2012-02-02T20:07:38Z

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.

Probability, preferential attachment, "rich get richer" - MathOverflow

Probability, preferential attachment, "rich get richer"

Answer by Kjetil B Halvorsen for Probability, preferential attachment, "rich get richer"