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.

  • $\begingroup$ For the case where $p_1=p_2=...=p_n$, this is the double dixie cup problem. $\endgroup$
    – jblood94
    Commented Jun 13, 2023 at 14:33
  • $\begingroup$ Thank you, that is exactly the name I needed! It appears to have been generalized to my case with arxiv.org/abs/1412.3626 $\endgroup$ Commented Jun 14, 2023 at 15:24
  • $\begingroup$ 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$ $\endgroup$ Commented Jun 14, 2023 at 15:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.