Probability, preferential attachment, "rich get richer" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T13:51:56Z http://mathoverflow.net/feeds/question/86799 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86799/probability-preferential-attachment-rich-get-richer Probability, preferential attachment, "rich get richer" unknown (google) 2012-01-27T06:56:59Z 2012-02-02T20:07:38Z <p>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> <p>$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> <p>$P_{0}(k_i) = {1 \over{N}}$</p> <p>so I think that</p> <p>$P_t(k_i) = {{k_{i-1}+A}\over{NA+\sum_jk_j}}$</p> <p>How to find the distribution for $t \rightarrow \infty$ ? </p> <p>Related:</p> <p><a href="http://en.wikipedia.org/wiki/Preferential_attachment" rel="nofollow">Preferential attachment</a></p> <p><a href="http://en.wikipedia.org/wiki/Rich_get_richer" rel="nofollow">Rich get richer</a></p> http://mathoverflow.net/questions/86799/probability-preferential-attachment-rich-get-richer/87366#87366 Answer by Kjetil B Halvorsen for Probability, preferential attachment, "rich get richer" Kjetil B Halvorsen 2012-02-02T20:07:38Z 2012-02-02T20:07:38Z <p>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.</p> <p>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. </p> <p>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.</p>