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.
Best Answer
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}