Skip to main content
MathOverflow

Return to Answer

added 23 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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 $n=3$$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 $n=3$$m=3$ and various $m$$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 $n=3$$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.

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 $n=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. Here are the chances of distinct bin numbers for $n=3$ and various $m$

$[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 $n=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.

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.

Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

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 $n=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. Here are the chances of distinct bin numbers for $n=3$ and various $m$

$[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 $n=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.