A standard six-sided die is to be rolled repeatedly until a side appears a number of times equal to its number. In other words until the n-th n appears.

Let P(n)=the probability the game terminates with the n-th n.

Find the distribution of n.

Feel free to generalize for m sides.

Warning: I have not managed this past m=4.

To make it easier, imagine the same game with a coin. Heads equals 1, tails equals 2. The only possible outcomes are

heads (game over)

tails, heads (game over)

tails, tails (game over)

Let P(n)=the probability the game terminates with the n-th n.

P(1) is the sum of the first two P's=3/4

P(2) is 1/4

Now imagine a 3-sided "die". The possible outcomes are:

1

21

22

231

232

2331

2332

2333

31

321

322

3231

3232

3233

331

3321

3322

3323

333

There are 19 possible outcomes. The probability of each outcome is 1/3^n, where n is the number of rolls.

P(1)=1/3+1/9+1/27+1/81+1/9+1/27+1/81+1/27+1/81=57/81

P(2)=1/9+1/27+1/81+1/27+1/81=17/81

P(3)=2/27=6/81

Note how much more complicated n=3 is than n=2. If you think that is a lot, try n=4. It gets a lot harder to ennumerate all the possibilities.

For n=6, the maximum number of rolls without the game ending is 15. This corresponds to having rolled 5 6's, 4 5's, 3 4's, 2 3's and 1 2. Given this, the game has to end on the 16th roll.

Generalizing, for n sides, the game has to end after 1 + (sum 1 to n-1) rolls = 1 + n(n-1)/2

*Edited on ***July 29, 2015, 6:06 pm**