MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(X_1,X_2,\ldots,X_k)$ be a multinomial random vector with parameters $n, p_1, p_2, \ldots, p_k$ (i.e., we throw randomly $n$ balls into $k$ bins, so that for each ball, the probability of landing in bin $i$ is $p_i$, independent of other balls).

Let $Y = \sum_{i=1}^k I_{\lbrace X_i = 0\rbrace }$ be the number of empty bins.

How is $Y$ distributed? Will be grateful to learn about any exact/approximate/asymptotic result.

I am familiar with the "occupancy problem" of Feller (the special case in which $p_i = 1/k$ for all $i$), and also with the Bahadur representation for dependent binary variates.

share|cite|improve this question
Well by linearity of expectation, the expected value of $Y$ is given by $\mathbb{E}(Y) = \sum_{i=1} ^{k} \mathbb{E}(I_{X_i =0}) = \sum_{i=1} ^{k} \mathbb{P}(X_i =0) = \sum_{i=1} ^{k} (1-p_i)^n$. – Pat Devlin Oct 2 '12 at 11:05
This seems helpful (found searching "generalized occupancy problem"): – Pat Devlin Oct 2 '12 at 11:09

As Pat Devlin commented, you can compute the expected value. A similar calculation gives you the higher moments.

$$E(Y^2) = \sum_{i,j} I_{X_i = 0} I_{X_j = 0} \\\ = \sum_i I_{X_i = 0} + 2 \sum_{i\lt j} I_{X_i = 0} I_{X_j = 0} \\\ = \sum_i (1-p_i)^n + 2\sum_{i \lt j} (1-p_i-p_j)^n$$

$$E(Y^m) = \sum_{S \subset \lbrace 1, 2, ... n \rbrace} \# \operatorname{surj}(m,|S|) (1-P(S))^n$$

where $\#\operatorname{surj}(a,b)$ is the number of surjections from a set of size $a$ to a set of size $b$, $\sum_i (-1)^i {b \choose i }(b-i)^a$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.