What is the expected number of bins with at least one ball? Consider an random variable $X$, that follows a binomial distribution with parameters:


*

*$n=B$ (i.e. the number of attempts is $B$)

*$p=P$ (i.e. the probability of having a success is $P$)


So, $X \sim Bin(B,P)$.
Then, we read $X$.
After that, we create exactly $X$ bins and $X$ balls.
Finally, we toss the uniformly at random to the bins.
All the tosses are independent from each other.
How can I obtain lower bounds on the expected number of bins with at least one ball?
Thanks in advance.
 A: Suppose $X = m$. Let $Y_{i}$ denote a random variable, such that:
$$ Y_{i} = \left\{\begin{matrix}
1 & \text{if the }i\text{-th bin has at least one ball} \\ 
0 & \text{otherwise}
\end{matrix}\right.$$
Then, we have
$$
\Pr[Y_i = 0 \mid X = m] = \left(\frac{m-1}{m}\right)^m
$$
because all $m$ balls are tossed into other $m-1$ bins.
Therefore,
$$
\Pr[Y_i = 1 \mid X = m] = 1 - \left(\frac{m-1}{m}\right)^m
$$
and
$$
\mathbb{E}[Y_i \mid X = m] = 1 - \left(\frac{m-1}{m}\right)^m \geq 1 - \frac{1}{e}
$$
Let $Z$ denote the number of bins with at least $1$ ball.
Then, by the linearity of the expectation:
$$
\mathbb{E}[Z \mid X = m] = \mathbb{E}[Y_1 + Y_2 + \cdots + Y_m \mid X = m] \geq m\left(1 - \frac{1}{e}\right)
$$
Thus, by the law of total expectation:
\begin{align}
\mathbb{E}[Z] =& \sum_{m=0}^B \mathbb{E}[Z \mid X = m]\cdot\Pr[X=m]  \\
\geq &\sum_{m=0}^B m\left(1 - \frac{1}{e}\right)\cdot\Pr[X=m] \\
=& \left(1-\frac{1}{e}\right) \sum_{m=0}^Bm\cdot\Pr[X=m] \\
=& \left(1 - \frac{1}{e}\right) \cdot\mathbb{E}[X] = \left(1-\frac{1}{e}\right)BP
\end{align}
