# Expected number of multinomial samples to cover a multiset

Consider a multinomial distribution $$[p_1, \ldots, p_n]$$ and a collection of counts $$[a_1, \ldots, a_n]$$. I would like to know the expected number of multinomial samples needed until every element $$i$$ has been sampled at least $$a_i$$ times.

More formally let $$X_1, X_2, \ldots \sim \operatorname{Multinomial}([p_1, ..., p_n]) \\ C_i^j = \sum_{i' \le i} \boldsymbol{1}_{X_{i'} = j} \\ M = \min \{i: \forall j \le n, C_i^j \ge a_j\}$$ and I would like to know $$\mathbb E [M]$$.

This isn't quite the negative multinomial since I want all values to reach a threshold rather than just the first. It feels like it should have closed form expectation but I haven't found it yet.

• For the case where $p_1=p_2=...=p_n$, this is the double dixie cup problem. Commented Jun 13, 2023 at 14:33
• Thank you, that is exactly the name I needed! It appears to have been generalized to my case with arxiv.org/abs/1412.3626 Commented Jun 14, 2023 at 15:24
• Ah, not quite exactly my case in the arxiv paper. Specifically they allow unequal probabilities but assume $a_1 = a_2 = \ldots = a_n = N$ Commented Jun 14, 2023 at 15:32