Ten distinguishable balls are thrown into 100 distinguishable bins independently and uniformly at random. Let X be the number of bins with at least two balls.
- Compute E(X) and use Markov’s inequality to estimate an upper bound on P [X ≥ 2]
- Compute Var(X) and use Chebyshev’s inequality to estimate an upper bound on P [X ≥ 2]
I'm having trouble with establishing the expected number of bins with at least 2 balls.
Here's what I've done so far:
-
Let X be a random variable such that X_i = 1 if bin i has ≥ 2 balls and 0 otherwise. Then we can calculate that for a given bin, P(≥ 2 balls) = 1 – P(1 ball) – P(0 balls).
-
The probability that the first ball falls into a given bin is clearly 1/100, so P(1 ball) = $(1/100)^{10}$ since we have 10 balls.
-
P(0 balls) = $(99/100)^{10}$ since on each toss 99 of the bins don't get the ball. Then we have $1 – (1/100)^{10} – (99/100)^{10} = 0.095$.
This is where my understanding is failing. I believe the above means that for a given bin i, the probability that it contains 2 or more balls is 0.095. By linearity of expectations, we should do $0.095*100$ to get the probability that any bin of the 100 has 2 or more balls. Clearly though this is nonsensical as it gives a probability over 1. Where am I going wrong here?
Best Answer
Credit to @lulu for his help here.
I was calculating P(1) incorrectly. $𝑃(1)=10×(1/100)^1×(99/100)^9 = 0.09135172474$. With that I calculate P(2) = =1 - 0.09135172474 - 0.904382075 = 0.0042. Then we can do P(2) * 100 since we have 100 bins to get E(2) = 0.47 which makes sense.