You throw a fair $k$-sided dice repeatedly and keep track of all the results. You stop if you have seen every face exactly the same number of times. What is the expected number of times you have to throw the dice? Is that number even finite?
Start with the simplest example of a $2$-sided dice, ie a fair coin. There is a 50% chance that after 2 flips you will have one head and one tail so you stop. There is a 12.5% chance that after 2 flips you will be at 2:0 and continue but after 4 flips you will be at 2:2, so you stop. One can compute a few more terms but I don't see enough of a pattern to get a summable series.
It is not too hard to compute the probability that after $k\cdot m$ throws of a $k$-sided dice you get every face exactly $m$ times but these probabilities are not independent for different $m$ so I'm not sure whether that is helpful.
The relation to random walks looks useful. One can map the results of throwing a coin repeatedly to a random work on the integers. Seeing the same number of heads and tails is equivalent to coming back to the starting point (at zero). This is a well studied problem and it is known that you come back to zero with probability one in a finite time. The number I'm looking for would be the expected time when you get back to zero for the first time but I haven't found any results on that.
For $k$ bigger than $2$ (and even) the mapping to random walks is not bijective anymore. If you map the outcome of a $6$-sided dice throw to a random walk on the $3$-dimensional integer lattice with each face corresponding to a step in one of the 6 directions that a return to the origin is necessary but not sufficient for having seen each face the same number of times. However, it is known that for a random walk on the integer lattice in dimension of at least $3$, the chance to return to the origin in finite time is strictly smaller than $1$. So this should prove that for a dice with at least $6$ faces, the expected number of throws is not finite.
Is this a finite number for $k=2$ and $k$ between $3$ and $5$? Are there estimates for it?
Best Answer
Answer concerning $k=2$. For $k\geq2$ see edit.
If $X_2$ denotes the number throws needed then $X_2$ only takes positive multiples of $2$ as value, and this with: $$P(X_2=2n)=2^{1-2n}C_{n-1}=2^{1-2n}\frac{(2n-2)!}{n!(n-1)!}$$for $n=1,2,\dots$, leading to:$$\mathbb EX_2=\sum_{n=1}^{\infty}2^{2-2n}\binom{2n-2}{n-1}=\sum_{n=0}^{\infty}2^{-2n}\binom{2n}{n}$$
Here $C_n$ stands for the $n$-th Catalan number.
In this case ($k=2$) we can do it with a fair coin.
Let $H_k$ stand for the number of throws with outcome heads and let $T_k$ for the number of throws with outcome tails by $k$ throws.
Then have a look at the path determined by $(k,H_k-T_k)$ for $k=0,1,\dots,2n$ under condition that $X_2=2n$.
Starting at $(0,0)$ and ending at $(2n,0)$ first WLOG we go to $(1,1)$.
Then with probability $2^{2-2n}C_{n-1}$ from there we go to $(2n-1,1)$ keeping a positive second coordinate.
And then with probability $2^{-1}$ we go to $(2n,0)$.
We have the asymptotic equality: $$2^{-2n}\binom{2n}{n}\sim\frac{1}{n^{\frac12}\sqrt\pi}$$and conclude that: $$\mathbb EX_2=+\infty$$
edit (to make the answer complete):
If $k>2$ let $U$ denote the outcome at first throw and let $V$ be (e.g.) the smallest element of $\left\{ 1,\dots,k\right\} $with $U\neq V$.
Now define $Y$ as the number of throws needed (inclusive the first) to come back again in the situation that outcome $U$ and outcome $V$ have appeared the same number of times.
Comparing $Y$ and $X_{2}$ we find easily that $P\left(Y>n\right)\geq P\left(X_{2}>n\right)$ for every nonnegative integer $n$ and consequently: $$\mathbb{E}Y=\sum_{n=0}^{\infty}P\left(Y>n\right)\geq\sum_{n=0}^{\infty}P\left(X_2>n\right)=\mathbb{E}X_{2}$$
Next to that it is evident that $X_{k}\geq Y$ so that $\mathbb{E}X_{k}\geq\mathbb{E}Y$.
Combining this with $\mathbb{E}X_{2}=+\infty$ we conclude that $\mathbb{E}X_{k}=+\infty$ for $k=2,3,\dots$