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.

  • 1
    $\begingroup$ 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$. $\endgroup$
    – Pat Devlin
    Oct 2 '12 at 11:05
  • $\begingroup$ This seems helpful (found searching "generalized occupancy problem"): springerlink.com/content/ml32565785l060g6 $\endgroup$
    – Pat Devlin
    Oct 2 '12 at 11:09
  • $\begingroup$ The link is dead and not on wayback machine $\endgroup$ Feb 9 at 17:44

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$.


Your Answer

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

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