# lower bound for probability of no 2 balls per bin.

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?

-
You could look at the generalized birthday problem section of en.wikipedia.org/wiki/Birthday_paradox – Ross Millikan Jun 6 '12 at 4:29
I am possibly confused, but don't you want $n =c\sqrt{m}$? – André Nicolas Jun 6 '12 at 5:34

@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.