1
$\begingroup$

There are $n$ balls and $m$ bins and every ball is placed independently and uniformly at random into a bin. I'm trying to show that there exists a constant $c$ such that, if $m=c\sqrt{n}$ then with probability $\geqslant 1/2$, no two balls will collide into the same bin, for sufficiently large $n$. (In textbooks I found the solution for upper bounding this probability.)

Let $A_i$ be the event that the $i$-th ball does not collide with balls $1,\dots,i-1$.

So essentially I want to lower bound the probability $ p = P\left[\ \bigcap_{i=2}^m A_i\ \right] = \prod_{i=2}^m\left( 1 - \frac{i-1}{n}\right). $ Assuming that $n \geqslant 2m$, we can use the bound $1-x\geqslant e^{-x-x^2}$ (for $x\leqslant \frac{1}{2}$). This gives $ p\geqslant \exp\left(\sum_{i=2}^m\left(-\frac{(i-1)^2}{n^2}-\frac{i-1}{n}\right)\right) = \exp\left( \frac{-(m-1) m (2 m+3 n-1)}{6 n^2} \right). $ But now I'm stuck, because setting $m=\Theta(\sqrt{n})$, doesn't seem to yield constant probability. What am I missing?

  • 0
    I am possibly confused, but don't you want $n =c\sqrt{m}$?2012-06-06

1 Answers 1

1

@André Nicolas: $m$ and $n$ are transposed in the first sentence (notice that the product of $A_i$ over all balls goes up to $m$).

@somebody: Your strategy of using the lower bound $e^{-x-x^2}$ is fatally flawed, since the $x^2$ term gives rise to the undesirable cubic polynomial in $m$ that is causing a problem later. What you want is to find a lower bound for $1-x$ which looks more like $e^{-cx}$. For instance, it is easy to check that $1-x \ge e^{-2x},$ for $0\le x\le \tfrac12$. Now you should have no difficulty following through the argument to find a value of $m = c\sqrt{n}$ which does the job.

  • 0
    Thanks! :) (I would vote up if I could)2012-06-06