7
$\begingroup$

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.

2 Answers 2

7

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

  • 6
    Just for the record the link says that this is called the Polya urn process.2010-11-19
2

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