What is the expected number of times to roll an ordinary $6$-sided die until each face comes up the same number of times?
This question is suggested by this one. JMoravitz suggested the reformulation given here, and Erick Wong commented that, since there is a positive probability that the event never occurs, the expected waiting time is infinite.
I have a calculation that purports to show the expected waiting time is finite, though I don't believe that. My reaction when I read the linked question was "forever". I need help finding the error, because I haven't been able to locate it.
In order for each face to come up an equal number of times, we have to make $6n$ rolls. The probability that every face has come up $n$ times is$$
{{6n\choose n,n,n,n,n,n}\over6^{6n}}= {(6n)!\over(n!)^66^{6n}}
$$ so the expected number of rolls is bounded above by $$
\sum_{n=1}^\infty 6n{(6n)!\over(n!)^66^{6n}}\tag{1}
$$
I say "bounded above" because the summand in $(1)$ only take account of the probability that the event occurs after $6n$ rolls, and it should use the probability that the event first occurs after $6n$ rolls, which cannot be more. Then by Stirling's approximation, $$
6n{(6n)!\over(n!)^66^{6n}}\sim
6n{{(6n)^{6n}e^{-6n}\sqrt{12n\pi}}\over
{(n^ne^{-n}\sqrt{2n\pi}})^6 6^{6n}}=6n{\sqrt{12n\pi}\over{(2n\pi)^3}}=O(n^{-3/2}),
$$
so that the sum in $(1)$ converges.
I must be doing something stupid (not for the first or last time) but I can't figure out what. Please point out my mistake.
Best Answer
Let me suggest why your computation must be wrong (and then point of that what Mark Bennet says is also correct):
Suppose that you found out that for each $6n$, the probability of equal-distribution was even smaller --- let's say it's zero. (Alternatively, you might ask for the probability that after $6n$ rolls, each number had come up $-3$ times; that probability would definitely be zero.
In that case, your sum would look like $$ \sum_n 6n \cdot 0 $$ which is certainly bounded...but that doesn't mean that the expected number of rolls until we find each face has shown up $-3$ times must be zero, right?
The problem here is that you're computing $$ \sum n \cdot p(n) $$ with the assumption that $\sum p(n) = 1$, i.e., that the even must occur on some $n$. But what you're missing is a term that looks like $\infty \cdot p(\infty)$ [informally, of course]: the expected number of rolls before something that never occurs ... actually occurs. :(
Let's look at something very concrete: what's the expected number of rolls you have to make until the total of your rolls is $1$?
Well, $1/6$ of the time, it happens in $1$ roll. What about in 2 rolls, or 3 rolls, or ... ? It never happens. But your sum would be $$ 1/6 \cdot 1 + 0 \cdot 2 + 0 \cdot 3 + \ldots $$ which is nice and finite.