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.

  • 2
    $\begingroup$ 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. $\endgroup$ Dec 12, 2012 at 22:12
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 12, 2012 at 23:06
  • $\begingroup$ See @Ori's answer below for what I should have said... $\endgroup$ Dec 13, 2012 at 0:49

2 Answers 2


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.

  • $\begingroup$ Can you give bounds $n=n(m,\epsilon)$ on what $n$ is required to have the probability of a collision be below $\epsilon?$ $\endgroup$ Dec 13, 2012 at 18:41
  • $\begingroup$ Yes, see my edit. $\endgroup$ Dec 13, 2012 at 19:58

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.

  • 4
    $\begingroup$ 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. $\endgroup$ Dec 13, 2012 at 7:32
  • 2
    $\begingroup$ By the way, you switched from $m$ bins to $n$ bins. $\endgroup$ Dec 13, 2012 at 7:35
  • $\begingroup$ Fixed the $m,n$ switch. I like the explanation. $\endgroup$ Dec 13, 2012 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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