1

Suppose that $n$ balls are randomly put in $k$ boxes, with uniform chance; called the uniform multinomial distribution. I'm interested in the chance that no box is empty. In other words, the chance that the minimum number of balls in any box is greater than zero.

By the definition of multinomial distribution one obtains: $$ P(\mbox{no box empty}) = \frac{n!}{k^n}\sum_{\vec{x}} \frac{1}{x_1! \cdots x_k!}, $$ where the sum is over all $k$-vectors $\vec{x}$ with only positive integer entries that sum up to $n$.

I'm wondering whether this formula can be simplified or approximated.

By the way, this is the "opposite" question of https://mathoverflow.net/questions/104948 where a formula for the maximum number of balls in any box is asked.

Community
  • 1
user44090
  • 45
  • "In other words, the chance that the minimum number of balls in any box is zero." should be "is greater than zero", no? – leonbloy Dec 12 '13 at 17:16
  • I guess this should be closed or migrated to MSE. Anyway: $P = k !S(n,k)/k^n$ where $S(n,k)$ is the Stirling number of second kind. – leonbloy Dec 12 '13 at 17:17
  • leonbloy: (1) Sorry for posting this question on the wrong site. (2) Yes, I meant "greater than zero". Corrected. (3) Thanks for your answer! – user44090 Dec 13 '13 at 10:36

1 Answers1

2

(Moving my comment to an answer after migration)

The probability that no box is empty, when all boxes are equiprobable, is not difficult to compute by a combinatorial argument. Assuming all the balls and boxes are distinguishable, the number of ways to have no empty box is given by $k!\, S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind. Then the desired probability is

$$P=\frac{k!\, S(n,k)}{k^n}$$

An coarse approximation for large values of $n,k$ can be obtained by a "Poissonization" approach: the experiment is asympotically equivalent to throwing $k$ Poisson iid variables with $\lambda = n/k$, and the probability that all greater than zero is

$$P_a = (1-e^{-n/k})^k$$

A few values:

n    k      P              Pa
10   4  0.7806015015    0.7099207499
10   6  0.2718121285    0.2847900333
30  12  0.3591452032    0.3577911635
30   6  0.9748018864    0.9602472297
leonbloy
  • 63,430
  • Thank you very much for the answer. I would like to use it in our manuscript. Do you know if there is a paper we can add to our reference? – Gao Apr 09 '18 at 17:34