Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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
add comment

1 Answer 1

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|improve this answer
    
Thanks! :) (I would vote up if I could) –  somebody Jun 6 '12 at 8:33
add comment

Your Answer

 
discard

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.