Expected rolls to get 3 of any number Suppose I am rolling a die repeatedly, and I keep a tally of how many times each number has come up.
As soon as a number has come up 3 times, the game is over.
It does not need to be 3 times in a row - the tally just needs to reach 3.
What is the expected number of rolls in a given game?
From simulation, I get an answer of approximately 7.29, but I'm trying to figure out how to solve it exactly.
I'm having trouble even beginning to frame this, so any help would be appreciated.
 A: For $X = (x_1, x_2, \ldots, x_6) \in \{0,1,2,3\}^6$ let $F(X)$ be the expected number of rolls starting in a state where each number $i$ has appeared $x_i$ times.  You want $F(0,\ldots,0)$.  You have
$F(x_1,\ldots,x_6) = 0$ if $\max(x_1, \ldots, x_6) = 3$, otherwise
$$F(x_1,\ldots, x_6) = 1 + \dfrac{1}{6} \left(F(x_1+1,x_2,\ldots,x_6) + \ldots + F(x_1,\ldots,x_5,x_6+1)\right) $$
Maple gives me $F(0,\ldots,0) = \dfrac{4084571}{559872} \approx 7.295544339$.
A: Let me get you started.
After 0 rolls, you have 0 of any number.
After 1 roll, you have 1 of one number, guaranteed.
After 2 rolls, there's two possibilities: $1/6$ of the time you have 2 of one number, and $5/6$ of the time you have 1 of each of two numbers.
After 3 rolls, you can end the game ($1/6 \cdot 1/6 = 1/36$), you can 2 of one number and 1 of another ($1/6 \cdot 5/6 + 5/6 \cdot 2/6 = 15/36 = 5/12$), or you can have 1 each of three numbers ($5/6 \cdot 4/6 = 20/36 = 5/9$).
Proceed in this fashion and you will find how often it will end after each number of rolls.
A: Alternative Poissonization Solution
Note: I have no clue how @Did solved this problem using another Poissonization strategy, but I am very intrigued by its terseness.
Let $N$ be the number of rolls needed, and $X_i$ is the count of each die. The event $\{N > n\}$ is the same as the event $\{\max(X_i) \le 2\ | \; N=n  \;\text{rolls} \}$, the latter which we denote $A_n$. So if $A_n$ occurs, the game is not yet over.
The equation for the expected value of $N$ is:
$E[N] = \sum^{12}_{n=0} P(N \gt n) = \sum^{12}_{n=0} P(A_n)$
(Why 12? The pigeon-hole principle states that the game can't go past 12 rounds)
Here's the Poissonization step: if we assume $N \sim \text{Poi}(\lambda)$, then $X_i$ are independent $\text{Poi}(\frac{\lambda}{6})$. (See notes in [1] for all this) 
Then 
$P(A_n)$ is $n!$ times the coefficient of $\lambda^n$ in the expansion of $e^{\lambda}\left[e^{-\lambda}\left(1 + \frac{\lambda}{6} + \frac{\lambda^2}{2!6^2} \right)^6\right]$
Using Wolfram Alpha, we can easily get the coefficients of that expansion, copied here into Python:
from fractions import Fraction

coefs = [
    Fraction(1), 
    Fraction(1), 
    Fraction(1,2),
    Fraction(35, 216),
    Fraction(65, 1728),
    Fraction(17, 2592),
    Fraction(41, 46656),
    Fraction(17,186624),
    Fraction(65, 8957952),
    Fraction(35, 80621568),
    Fraction(1, 53747712),
    Fraction(1, 1934917632),
    Fraction(1, 139314069504),
]

Finally we compute the sum above:
from math import factorial
ev = 0
for i, coef in enumerate(coefs):
    ev += factorial(i) * coef

print ev
# 4084571/559872

[1] Probability for Statistics and Machine Learning, by DasGupta
