Suppose you are given a random number, $N$, of balls together with the same random number $N$ of urns, where $N$ has a Poisson distribution with parameter 10. Assume each ball is equally likely to go into any of the urns, $1, 2, ..., N$. It is further assumed that the balls are put into the urns independently. Find the expected number of urns that are empty after all balls have been put into the urns.


Define random variables $I_k$ for $k = 1, 2, ... N$, such that

$$ I_k = \begin{cases} 1, & \text{if the k-th urn is empty} \\ 0, & \text{otherwise} \end{cases} $$

Now, consider for $k=1, ... , N$, we have

\begin{align*} E[I_k | N = n] &= P(\{\text{no balls go into k-th urn}\}) \\ &= \left(\frac {n-1} {n}\right)^n \end{align*}


\begin{align*} E\left[\sum_{k=1}^n I_k | N = n\right] &= \sum_{k=1}^nE[I_k | N = n] \\ &= n\left(\frac {n-1} {n}\right)^n \end{align*}

Define the random variable $E\left[\sum_{k=1}^n I_k | N\right] = E\left[\sum_{k=1}^n I_k | N = n\right]$, $N = n$ for some $n \in \mathbf{R}$. Then apply the law of iterated expectations and we get

\begin{align*} E\left[\sum_{k=1}^N I_k \right] &= E\left[E\left[\sum_{k=1}^n I_k | N\right]\right] \\ &= E\left[N\left(\frac {N-1} {N}\right)^N\right] \\ &= \sum_{k=0}^{\infty} k\left(\frac {k-1} {k}\right)^k e^{-10} \frac {10^k} {k!} \end{align*}

From here, I face some difficulty evaluating the final expression. Also, I am not entirely sure if my approach is correct in general.

Any advice would be greatly appreciated!

  • 1
    $\begingroup$ It's important to note that your sum isn't defined when $N=0$ which occurs with non zero probability. How should we interpret this event? Wolfram doesn't produce a closed form of this sum, FYI, but your approach seems legit $\endgroup$ – Matthew Pilling Apr 18 at 2:34
  • $\begingroup$ Yup, that makes sense! Must have overlooked it, thanks for the feedback! Should have defined the bounds for $N \ge 1$, as it naturally should be. $\endgroup$ – iobtl Apr 18 at 6:40

Your approach is fine, though the sum should begin at $k=1$ (or $k=2$).

I don't think the expression has a nice closed form.

Noticing that the mean of the variable is $\lambda = 10$, and that the approximation $(1-1/n)^n \approx e^{-1}$ should work reasonably around $n\approx 10$, then the function $g(n)= n \, (1-1/n)^n$ is approximately linear around the mean.

Then we can approximate $$E[g(n)] \approx g(E[n]) = g(\lambda) = 10 \, (1-1/10)^{10} = 3.48678\dots \tag 1$$

If we really wish, we could refine this by computing the second derivate of $g()$, see eg. This gives $3.48589\dots$ , which already suggests that the approximation $(1)$ is good.

Further, one can check that $g(n)$ is concave, hence (by Jensen) $(1)$ is also an upper bound.


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.