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

Leave a Reply

Your email address will not be published. Required fields are marked *

*