### 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

balls, then the probability that each bin in C has at least one ball is at most

if

, where

is some constant strictly less than 1. If

, then the probability is at most

.

Comment: conpon analysis + chernoff bound

### Lemma

[1] Consider a process that throws t balls into b bins uniformly at random. if

, then the probability that there are at most

occupied bins is at most

.

[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

of the bins in

have at least one ball is at most

if

; and at most

if

.

## Reference

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