There's a bag containing n distinct objects. Keeping track of the outcomes, one object is drawn from the bag, and put back in. Repeating this operation until each of the $n$ objects has been seen at least $m$ times, what is the expected number of draws ?
The way i found to compute this involves representing it as a Markov Chain:
The current state is a list $l$ of m numbers, $l_i$ being the number of objects drawn exactly $i$ times for $0 ≤ i < m$. As the state doesn't account for object drawn m times or more, drawing an object that belong to this group leads you to the same state.
We can then remove the transitions that keep you in the same state and instead take into account the expected number of draws to leave that state.
The expected number of draws to reach last state can then be defined recursively as:
$$f(\text{last state}) = 0$$
$$f(state) =$$ $$\text{Expected number of draws to leave the state}$$ $$+$$ $$\sum_{\text{next state}}{\text{probability of transition to next state}* \text{f(next state)}}$$
Now comes my problem: doing it this way require to go through every possible state, and the number of states is ${n+m \choose m}$, so it grows exponentially with $m$.
Is there a way to do it more efficiently ? If not, is there a way to get an approximation more efficiently ?