4
$\begingroup$

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.

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .