bin and ball

Lemma

[1] Consider a process that throws balls uniformly at random into b bins and let C be a subset of these bins. If the process throws $q \leq b log|C|$ balls, then the probability that each bin in C has at least one ball is at most $\frac{1}{exp(\gamma \cdot ((1 - \frac{q}{b \cdot log|C|}) \cdot log|C|)^2)}$ if $|C| \geq 2$, where $\gamma$ is some constant strictly less than 1. If $|C| = 1$, then the probability is at most $1 - (1/4)^{q/b}$.

Comment: conpon analysis + chernoff bound

Lemma

[1] Consider a process that throws t balls into b bins uniformly at random. if $t \leq b/e$, then the probability that there are at most $t/2$ occupied bins is at most $2^{-t/2}$.

Lemma

[1] Consider a process that throws balls uniformly at random into b bins and let C be a subset of these bins. If the process throws q balls, then the probability that at least $\theta \cdot |C|$ of the bins in $C$ have at least one ball is at most $\frac{1}{exp(\frac{\theta \cdot |C|}{6})}$ if $q \leq \theta \cdot b /2$; and at most $\frac{1}{exp(\frac{\theta \cdot |C|}{6} \cdot (\frac{\theta \cdot b}{q}-1)^2)}$ if $\theta \cdot b/2 < q < \theta \cdot b$. 

Reference

[1] Co-Location-Resistant Clouds, by Yossi Azar et al. in CCSW 2014