Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
You could look at the generalized birthday problem section of – 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
up vote 1 down vote accepted

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

share|cite|improve this answer
Thanks! :) (I would vote up if I could) – somebody Jun 6 '12 at 8:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.