Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.