The multinomial count distribution for a set of $M$ categories is

$P((n_1, \dots,n_M)|N)=\left(\frac{N!}{n_1!\dots n_m!}\prod_{i=1}^Mp_i^{n_i}\right)\delta\left( \sum_{i=1}^M n_i-N\right)\;,$
where category $i=1, \dots, m$ appears $n_i$ times, and the Dirac $\delta$-function appears to enforce the sum constraint that $\sum_{i=1}^M n_i=N$.

What is the distribution, $P(m)$ of the number of non-zero counts, $m=\sum_{i=1}^M\mathrm{sgn}[n_i]$, where $\mathrm{sgn}(x)=1$ for $x>0$ and $0$ for $x=0$.

I couldn't find anything in a quick internet search, but I am still hoping there may be a closed form solution, even for the case where the $p_i$ are all distinct.

One approach is to focus instead on the distribution, $P_0(m_0)$, of zero counts, $m_0$, from which I think $P(m)=1-P_0(M-m)$.

A specific subset of $m_0$ categories is denoted $\alpha=\{\alpha_1, \dots, \alpha_{m_0}\}$, where $\alpha_i\in\{1, \dots, M\}$. There are $\binom{M}{m_0}$ distinct $\alpha$ subsets. For a given $\alpha$, the probability to obtain one of the $\alpha$ categories in a single count sample is $p_\alpha=\sum_{i=1}^{m_0}p_{\alpha_i}$. Thus, the probability to obtain something other than the $\alpha$ categories across $N$ samples is $(1-p_\alpha)^N$. This representation ignores permutations of the $\alpha$ subset. There are $m_0!$ such permutations.

If someone knows a solution, please share. In lieu of a solution, I could use help in the combinatorics in the sum of $(1-p_\alpha)^N$ over subsets $\alpha$ and their orderings.

  • $\begingroup$ Since I tend to need a mental picture of a problem to make it more paletable, may I just check that you are asking for the probability distribution $P(m)$ that when $N$ distinct balls are placed into $M$ distinct boxes, exactly $m$ boxes contain at least 1 ball (leaving exactly $M-m$ empty boxes)? $\endgroup$ – N. Shales Mar 30 '17 at 15:19
  • $\begingroup$ Yes. Another mental picture for the multinomial is provided on its wiki page: "...the probability of counts for rolling a k-sided die n times. For n independent trials each of which leads to a success for exactly one of k categories, with each category having a given fixed success probability, the multinomial distribution gives the probability of any particular combination of numbers of successes for the various categories." $\endgroup$ – puelmato Mar 30 '17 at 15:25
  • $\begingroup$ In addition, the balls are not placed into the $M$ boxes with equal probability but with the given probabilities $p_1, \dots, p_M$. $\endgroup$ – puelmato Mar 30 '17 at 15:33
  • $\begingroup$ I think a nice closed form solution for arbitrary $p_i$s is going to be a bit ambitious. Each different distribution of balls to boxes will have potentially different probabilities, I believe that the only way to find the total probability that exactly $m$ boxes are filled with at least 1 ball would be to sum over all such cases. For the scenario that $p_i=p=\text{const.}$ it is possible to give a simpler alternating sum for $P(m)$. $\endgroup$ – N. Shales Mar 30 '17 at 16:01
  • $\begingroup$ Hmmm, ok. Might some parametrized balls-to-boxes distribution make the existence of a closed form solution more likely? Say power-law distributed,$p_i\propto i^\beta$? $\endgroup$ – puelmato Mar 30 '17 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.