Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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 $ ?

Related:

Preferential attachment

Rich get richer

Posted also here:

http://mathoverflow.net/questions/86799/probability-preferential-attachment-rich-get-richer

share|improve this question
2  
Crossposted on MO. Please do not do that. –  Did Jan 27 '12 at 7:44
1  
This looks exactly like the Pólya urn model, whose limit distribution is known to be multivariate Dirichlet. –  Did Jan 27 '12 at 7:45
    
OK, I promise not to do that again. Could you please explain your comment? I am not an expert at this stuff. –  Jakub M. Jan 27 '12 at 7:50
    
Did you read the link? –  Did Jan 27 '12 at 8:15
    
You are right, I was confused. en.wikipedia.org/wiki/Multivariate_Pólya_distribution is then an answer. Thanks a lot! –  Jakub M. Jan 27 '12 at 9:03

1 Answer 1

up vote 4 down vote accepted

This looks exactly like the Pólya urn model, whose limit distribution is known to be multivariate Dirichlet.

share|improve this answer

Your Answer

 
discard

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.