# distribution of the number of empty bins in a multinomial setting

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.

• 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"): springerlink.com/content/ml32565785l060g6 – Pat Devlin Oct 2 '12 at 11:09

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