$k$ balls into $n$ bins -- Number of occupied bins

Question

Suppose we throw $k$ balls into $n$ bins. Assume that $\log^2n\le k\le n$.

Is there a high probability bound (preferably exponential) on the number of occupied (i.e., non-empty) bins?

Something like: $\Pr(\text{Num of Occupied Bins} < \alpha k) < e^{-O(k)}$.

Thanks!

Answer 1

If $2k \leq n$ then probability of finding an empty bin is $\geq \frac{1}{2}$ and then you can use Chernoff bound.

If $2k > n$ then you could always skip some balls ;-)

Cheers!