Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How many balls have to be thrown uniformly at random into $m$ bins, such that with high probability $n_1, n_2, \dots, n_m$ are distinct numbers, where $n_i$ is the number of balls in bin $i$ ?

Is there anything known about this problem? A trivial lower bound is $m(m-1)/2$, as we need $m$ distinct values.

share|improve this question
2  
I guess you want the variance (of the number of balls in the $i$th bin) to be substantially larger than $m^2$ for this to happen. Since the variance scales linearly with the number of balls tossed, you need to toss $\gg m^2$ balls to have a high probability that all the bins have different levels. –  Anthony Quas Dec 12 '12 at 22:12
1  
The answer is easy for $m=2$! Even if we add the condition "no empty bins" it is easy although difference at least $3$ might be more interesting. Try $m=3$ to get a feel. –  Aaron Meyerowitz Dec 12 '12 at 23:06
    
See @Ori's answer below for what I should have said... –  Anthony Quas Dec 13 '12 at 0:49
add comment

2 Answers

up vote 14 down vote accepted

This happens whenever $n\gg m^5$. To see this, notice that the expected number of balls in each bin is $n/m$ and the variance is also on the order of $n/m$. The distribution "tends" to N(n/m,n/m) (in the sense of CLT). We also have a local CLT, meaning that the for values $k\in\{n/m-\sqrt{n/m},\ldots,n/m+\sqrt{n/m}\}$ we have that $\mathbb{P}(n_1=k)\approx \sqrt{m/n}$.

So this means that we have a birthday paradox kind of setting where we have roughly $m$ numbers roughly uniformly distributed among roughly $\sqrt{n/m}$ values. In this scenario with high probability you have no collisions exactly when $m \ll \sqrt{\sqrt{n/m}}$, i.e. when $n \gg m^5$.

There is a technicality here, the values $n_i$ are not independent. But they are almost independent, so one can get the desired result by a second moment argument on the number of collisions.

EDIT: one side of the birthday paradox argument is easier to get since it involves only a union bound. If we look at two specific bins than asymptotically we see two independent Poisson($n/m$) random variables and the probability of collision is $K \sqrt{m/n}$ for some constant $K$ (which can be explicitly computed). We have ${m \choose 2}$ pairs of bins so the probability of collision can be asymptotically bounded by $K \sqrt{m^5/n}$. I expect the lower bound to be of the same order of magnitude.

share|improve this answer
    
Can you give bounds $n=n(m,\epsilon)$ on what $n$ is required to have the probability of a collision be below $\epsilon?$ –  Aaron Meyerowitz Dec 13 '12 at 18:41
    
Yes, see my edit. –  Ori Gurel-Gurevich Dec 13 '12 at 19:58
add comment

I think you have a good answer but I wanted to add a few computational observations. For $m=2$ it is obviously best to have an odd number of balls! But when $n=2k$ the chance of an even split is $$\frac{\binom{2k}{k}}{2^{2k}}\approx\frac{1}{\sqrt{\pi k}}$$ So figure out how high you want the probability of distinct bin numbers to be.

For $m=3$ it seems to actually be an advantage to have the number of balls be a multiple of three. There might be an easy explanation why, but I don't see it. (But see the comments) Here are the chances of distinct bin numbers for $m=3$ and various $n$

$[20, .67531], [21, .75929], [22, .69015], [23, .69685], [24, .77016], [25, .70904], $$[121, .86695], [122, .86750], [123, .88141], [124, .86857], [125, .86909], [126, .88267], $$[1021, .95414], [1022, .95416], [1023, .95580], [1024, .95420], [1025, .95422], [1026, .95586]$$[3000, .97379], [3001, .97324], [3002, .97325]$

The last figures suggest to me that, with $m=3$ bins, IF you plan to throw in around $m_0=3000$ balls and then add $100$ more, one at a time THEN the chance of having a tie right after ball number $m_0$ is about $\frac{1}{40}$ but we would also expect (before throwing in the first ball) to have about 2 ties over the next $100$ balls. That reasoning may be too sloppy. There will be ties all along the way, they become less frequent but when they do occur it is probably a clump of several.

When the number of bins gets bigger the chances of a tie increase.

share|improve this answer
4  
If $n=3$, and $m$ is not a multiple of $3$, then the pairwise equality events, that bin $i$ has the same count as bin $j$, are disjoint. When $m$ is a multiple of $3$ it is possible for all bins to have the same count. That effect looks like it is about the right magnitude to explain why it is easier to have all $3$ counts distinct if $m$ is divisible by $3$ -- the pairwise events are about the same probability but because they can overlap, the probability of the union is smaller. –  Douglas Zare Dec 13 '12 at 7:32
2  
By the way, you switched from $m$ bins to $n$ bins. –  Douglas Zare Dec 13 '12 at 7:35
    
Fixed the $m,n$ switch. I like the explanation. –  Aaron Meyerowitz Dec 13 '12 at 13:03
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.