1
$\begingroup$

How many balls do you need to throw randomly into n bins so that the probability that none of the bins is empty is at least 1/100?

I am trying to solve this question by first finding the expected no of balls to be thrown so that every bin has at least one ball which comes out to be the following (similar to coupon-collector problem)

$$ n*\sum_{i = 1}^{n} \frac{1}{n} = n * H_{n} $$

Now, I am trying to use Markov's inequality :

$$ Pr[X\geqslant a] \leqslant \frac{E[X]}{a} $$

But, I am stuck here as I am unable to connect it with the question. Please help.

$\endgroup$
1
$\begingroup$

Lemma:
Let $X$ be the number of empty bins when $m$ balls are thrown uniformly and independently at random in $n$ bins. Then $$\mathbb{E}[X] = n\left( 1 - \frac{1}{n}\right)^m \leq n e^{-m/n}.$$

Proof:
Let $X_i$ be the random variable denoting whether bin $i$ is empty or not (i.e., $X_i = 1$ if bin $i$ is empty and $X_i = 0$ if bin $i$ contains at least one ball).
Observe that $X = \sum_{i=1}^n X_i$, and that all $X_i$'s are independent. The probability that bin $i$ receives a ball is $\frac{1}{n}$, hence the probability that it remains empty after tossing one ball is $Pr(X_i = 1) = 1 - \frac{1}{n}$. Since the throws are supposed independent, after $m$ throws, we have $$Pr(X_i = 1) = \left( 1 - \frac{1}{n}\right)^m.$$ Since $X$ is a sum of independent Bernouilli random variables, we directly obtain $$\mathbb{E}[X] = n \left( 1 - \frac{1}{n}\right)^m \leq n e^{-m/n}.$$


Now, letting $m \geq n \ln(n \cdot 100)$, we have $$\mathbb{E}[X] \leq n e^{-n \ln(100n)/n} = \frac{n}{100n} = \frac{1}{100}.$$ Concluding with Markov's inequality that tells us $Pr(X \geq 1) \leq \mathbb{E}[X]$, we obtain $$Pr(X = 0) \geq 1 - \frac{1}{100}.$$ In plain text, this means that the probability to have no empty bin is greater that $1 - \frac{1}{100}$, or that the probability to have at least an empty bin is smaller that $\frac{1}{100}$.

$\endgroup$

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.