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
Solution for n=2 and 3, and some observations
