3
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ But I need a lower bound on the number of occupied bins. Your analysis will not give a lower bound on probability that a bin is occupied... $\endgroup$
    – Michael
    Feb 18, 2013 at 11:57
  • $\begingroup$ @Michael There are Chernoff bounds of the form $P(X < \alpha) < f(\alpha)$ or $P(|X-\mu| > \alpha) < f(\alpha)$, both should work. $\endgroup$
    – dtldarek
    Feb 18, 2013 at 12:16
  • $\begingroup$ Sure, but I need a lower bound on probability that a bin is occupied, or an upper bound on probability that a bin is empty. Your analysis gives an opposite... If I skip balls, how it can help me to ensure high occupancy? Or I'm missing something? $\endgroup$
    – Michael
    Feb 18, 2013 at 12:35
  • 1
    $\begingroup$ @Michael The idea is to count taken bins the first moment they turn from empty to non-empty. If you hit an empty bin, then it is non-empty then, right? So the high number of empty-hits (this is not the same as empty bins) will mean high number of taken bins. $\endgroup$
    – dtldarek
    Feb 18, 2013 at 12:53
  • $\begingroup$ I got the point! So, the expected number of occupied bins is $k/2$, and using Chernoff, with probability of at lest $1-e^{-k/16}$, the number of occupied bins is at least $k/4$. Very elegant approach. Thank you! $\endgroup$
    – Michael
    Feb 18, 2013 at 13:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .