A standard sixsided die is to be rolled repeatedly until a side appears a number of times equal to its number. In other words until the nth n appears.
Let P(n)=the probability the game terminates with the nth n.
Find the distribution of n.
Feel free to generalize for m sides.
Warning: I have not managed this past m=4.
(In reply to
re(4): computer aided solution by Charlie)
I figured out a computational shortcut to calculating the probabilities.
Now assume that the game ends where value 1 occurs s1 times, 2 s2 times and so on to n occuring s_n times. Now if the game ended with value k being rolled then that means s_k=k and s_t<t for all other t.
The odds of this happening can be calculated as
(s1+s2+...+s_n)!/(s1*s2*...*s_n!)*(1/n)^(s1+s2+...+s_n)
Now to get the complete probability for a given k we simply sum this individual probability over all possible combinations of values of the other s_t. As it turns out this number of combinations does not explode nearly as quickly.
Taking this approach, I made this function in Mathematica whicle builds the nested summation expression for a given n,s and then uses that to calculate the probabilities. I also calculate the ratio of consecutive probabilities.
p[n_, s_] := Module[{ex, i, a},
ex = "Sum[(s1";
For[i = 2, i <= n, ++i,
ex = ex <> "+s" <> ToString[i];
];
ex = ex <> ")!/(s1!";
For[i = 2, i <= n, ++i,
ex = ex <> "*s" <> ToString[i] <> "!";
];
ex = ex <> ")*(1/" <> ToString[n] <> ")^(s1";
For[i = 2, i <= n, ++i,
ex = ex <> "+s" <> ToString[i];
];
ex = ex <> "+1)";
For[i = 1, i <= n, ++i,
If[i == s, a = i  1, a = 0;];
ex = ex <> ",{s" <> ToString[i] <> "," <> ToString[a] <> "," <>
ToString[i  1] <> "}";
];
ex = ex <> "]";
Return[ToExpression[ex]];
];
My next post I will give the results so far (I'm having it run up to 20sided die and so far it has completed for 10sides)

Posted by Daniel
on 20150703 21:00:09 