Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I heard about it sometime somewhere and want to read about it now, but I can't recall what the name is:

Start with $a_1 = \ldots =a_n=1$. Choose a number between 1 and $n$ with probability $a_i/(a_1+ \ldots + a_n)$ to choose $i$. If $i_0$ is the number chosen, increase $a_i$ by 1 and now choose another number and so on indefinitely.

share|cite|improve this question
up vote 7 down vote accepted

For this process and a substantial generalization, see this. The case $p=0$ and $\gamma = 1$ corresponds to the process you described.

share|cite|improve this answer
Just for the record the link says that this is called the Polya urn process. – Aniko Nov 19 '10 at 14:10

Thanks for the pointer, Shai Covo. The name of this specific process is preferential attachment.

share|cite|improve this answer

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.