There are $n$ balls. We put them into $2n$ bins uniformly and pairwise-independently, meaning $P(\text{ball }a \text{ in bin }B_i)=\frac{1}{2n}$ and $P(\text{ball }a \text{ in bin }B_i\text{ and }\text{ball }b \text{ in bin }B_j)=\frac{1}{4n^2}$. Show that the probability that bin $B_1$ is not empty is at least $\frac{3}{8}$.
If the balls are independent, then $P(B_1\text{ is empty})=(1-\frac{1}{2n})^{n}\leq e^{-0.5}<\frac{5}{8}$, and we are done. However, I am not sure how to do it if we only have pairwise independence. Thanks!
Best Answer
We expect half a ball per bin, and we expect $\left(\frac1{2n}\right)^2\binom n2=\frac18\left(1-\frac1n\right)\lt\frac18$ pairs per bin. Denote the probability that there are $k$ balls in the bin by $p_k$. We have
$$\sum_{k=1}^nkp_k=\frac12$$
and
$$ \sum_{k=1}^n(k-1)p_k\le\sum_{k=1}^n\binom k2p_k\lt\frac18\;. $$
Subtracting the two yields
$$ \sum_{k=1}^np_k\gt\frac38\;, $$
as required.