# Balls and bins variation

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.

• 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
• 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

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.

• 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

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.

• 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
• 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