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
![Rendered by QuickLaTeX.com q leq b log|C|](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-bc27e5994940e6c26e0975d31ea4ef25_l3.png)
balls, then the probability that each bin in C has at least one ball is at most
![Rendered by QuickLaTeX.com frac{1}{exp(gamma cdot ((1 - frac{q}{b cdot log|C|}) cdot log|C|)^2)}](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-fc52ffd9bf763f5c801ed7f1eab37cb7_l3.png)
if
![Rendered by QuickLaTeX.com |C| geq 2](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-2e4c09efb51e4e7e5625a28d5d391b98_l3.png)
, where
![Rendered by QuickLaTeX.com gamma](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-11f70f0c218d320fd93d30bba4c86300_l3.png)
is some constant strictly less than 1. If
![Rendered by QuickLaTeX.com |C| = 1](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-646ce65b82dbbe62e5eb204f5d62cf97_l3.png)
, then the probability is at most
![Rendered by QuickLaTeX.com 1 - (1/4)^{q/b}](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-9845cfff4ad3f3b721a912f137f37e5b_l3.png)
.
Comment: conpon analysis + chernoff bound
Lemma
[1] Consider a process that throws t balls into b bins uniformly at random. if
![Rendered by QuickLaTeX.com t leq b/e](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-61ab2f8dffb4d113b26168b96e9dacfc_l3.png)
, then the probability that there are at most
![Rendered by QuickLaTeX.com t/2](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-a51aabd35a2569fafdde79555305587c_l3.png)
occupied bins is at most
![Rendered by QuickLaTeX.com 2^{-t/2}](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-f0274c89703371423bdc84151a83bc34_l3.png)
.
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
![Rendered by QuickLaTeX.com theta cdot |C|](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-77114c135f7ed629cec08b42b756b76a_l3.png)
of the bins in
![Rendered by QuickLaTeX.com C](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-eda88fce4ab12a676aa4baf036291115_l3.png)
have at least one ball is at most
![Rendered by QuickLaTeX.com frac{1}{exp(frac{theta cdot |C|}{6})}](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-bb7318ecdd7b3447cb6cbabd82fb921f_l3.png)
if
![Rendered by QuickLaTeX.com q leq theta cdot b /2](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-aedffc7044935123b8300a80f6ec3524_l3.png)
; and at most
![Rendered by QuickLaTeX.com frac{1}{exp(frac{theta cdot |C|}{6} cdot (frac{theta cdot b}{q}-1)^2)}](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-515953d04c710d2ab7bae8581daa4ea7_l3.png)
if
![Rendered by QuickLaTeX.com theta cdot b/2 < q < theta cdot b](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-a1be6b64412bfff59fee9f1ac4d83a21_l3.png)
.
Reference
[1] Co-Location-Resistant Clouds, by Yossi Azar et al. in CCSW 2014