Probability of k collisions

, Friday, 30 January 2015
While I was reading about hash tables I stumbled upon this deceptively simple question. I have rephrased it to make it easier to understand.
Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this (select-put) $n$ times. In the end what is the probability of having at least one bucket with $k$ balls?
My initial attempts to solve it failed, and I posted the question on math.stackexchange. An approximation for large values of $m$ and $n$ was posted as an answer but I was interested in exact results. Once I realized I had no way of finding someone else's solution, I was able to solve it myself.

Simulation

First, to check if my solution is correct, I have written a small program to simulate the select-put procedure million times and report the experimental probability for different values of $m$,$n$ and $k$. If you are interested, you can find the java code at the end of my post.

Solution

First we will start with writing the probability of 1 box having $k$ balls. Then using inclusion-exclusion principle we will generalize. Let's write the probability of putting first $k$ balls into the first box and remaining balls to the other boxes: $$\left(\frac1{m}\right)^k \left(1-\frac1{m}\right)^{n-k}$$ We have $\binom{n}{k}$ ways of putting $k$ balls into a particular box (e.g. first box), and we have $m$ such boxes. So the probability becomes: $$m \binom{n}{k} \left(\frac1{m}\right)^k \left(1-\frac1{m}\right)^{n-k}$$ But the expression above suffers from double counting, i.e. it counts configurations that contains multiple boxes with $k$ balls more than once. So we need to subtract the value for 2 boxes having $k$ balls, add the value for 3 boxes having $k$ balls, etc... Let's write the probability of putting first $k$ balls into the 1st box, next $k$ balls into the 2nd box, and remaining balls to the other boxes. $$\left(\frac1{m}\right)^k \left(\frac1{m}\right)^k \left(1-\frac1{m}\right)^{n-2k}$$ We have $\binom{n}{k}\binom{n-k}{k}$ ways of putting $2k$ balls into two particular boxes (e.g. first and second box), and we have $\binom{m}{2}$ such boxes. So the probability becomes: $$\binom{m}{2}\binom{n}{k}\binom{n-k}{k}\left(\frac1{m}\right)^k \left(\frac1{m}\right)^k \left(1-\frac1{m}\right)^{n-2k}$$ At this point you should be able to see the pattern that is emerging.

Generalization

If we put together and generalize what we have done so far we get the following expression as probability of having a box with $k$ balls: $$\sum^{\lfloor \frac{n}{k} \rfloor}_{i=1} (-1)^{i+1} \binom{m}{i} \left[ \prod^{i-1}_{j=0} \binom{n-jk}{k} \right] \left( \frac1{m} \right)^{ik} \left( \frac{m-i}{m} \right)^{n-ik}$$ The powers of $-1$ at the beginning enables adding values for odd number of balls and subtracting values for even number of balls, i.e. inclusion-exclusion principle.

The code

  private static double calculateKcollisions(int m, int n, int k) {
double probability = 0;

int sign = 1;

for (int i = 1; n - i * k >= 0 && i <= m; i++) {
double p = binomial(m, i) * pow(1.0 / m, i * k);
p *= pow((double) (m - i) / m, n - i * k);

for (int j = 0; j < i; j++) {
p *= binomial(n - j * k, k);
}

probability += sign * p;
sign *= -1;
}

return probability;
}



Simulation code

  private static final Random RNG = new Random();

public static void main(String[] args) {
int sampleCount = 1000000;

for (int experimentNo = 0; experimentNo < 10; experimentNo++) {
int m = RNG.nextInt(7) + 3;
int n = RNG.nextInt(m) + RNG.nextInt(10) + 1;
int k = RNG.nextInt(n + 1);

System.out.println(format("m:%d  n:%d  k:%d", m, n, k));

int successCount = 0;
for (int sampleNo = 0; sampleNo < sampleCount; sampleNo++) {

int[] boxes = new int[m];

for (int i = 0; i < n; i++)
boxes[RNG.nextInt(m)]++;

for (int i = 0; i < m; i++) {
if (boxes[i] == k) {
successCount++;
break;
}
}
}

double experimental = (double) successCount / sampleCount;

double calculated = calculateKcollisions(m, n, k);

System.out.println(format("xperimental: %f  calculated: %f", experimental, calculated));
System.out.println(format("diff: %.2f\n", abs(experimental - calculated)));
System.out.println();
}
}


1. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: Latin Women Dating

2. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: AmoLatina.com

3. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: AmoLatina Dating Review Site

4. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: AmoLatina.com Member Login

5. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: Russianbrides

7. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: Russian Brides Online

9. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: Russian Love Match

11. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: Sexy Russian Ladies

12. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: African Date

13. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: African Date Site

14. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: Date African Women

16. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: ChinaLove

17. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: China Love

18. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: China Love Com

19. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: Chinese Love Links

21. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: Cupid Dating

25. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: CharmingDate

26. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: Zoosk Dating Sites

28. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: Zoosk Free Dating App

29. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: Match Dating Site

30. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: www match com

31. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: amolatinawomen

33. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: chinalove.com

34. I really thank you for that great post and Please add a more new post. Do well...! To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: free dating sites no sign up

35. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: 100 percent free dating sites

37. I really thank you for that great post and Please add a more new post. Do well...!For more information visit this site:
best dating websites

38. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
good dating sites

40. I really thank you for that great post and Please add a more new post. Do well...!
love date

42. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
how to date

43. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: relationships topics

44. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. for more information visit: romantic ideas long distance relationship

45. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
tips for women

46. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. for more information visit: dating profile examples for men

47. I really thank you for that great post and Please add a more new post. Do well...!
rules of dating

find a date

50. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: benefits of being in a relationship

51. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners.
online dating apps

52. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: benefits of dating

53. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: how to date an american girl

54. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: best dating sites

56. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: dating pics

57. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: dating your best friend

58. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: dating an older girl

girl sexy

60. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners.
dating hot women

61. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site: a girl thinking

62. I really thank you for that great post and Please add a more new post. Do well...!
dating a latina

63. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: tall women dating

how to date a latina

65. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: dating experience

66. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: stages of dating

country girl dating

68. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: new relationship

69. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
meet american

70. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: how often do you see your boyfriend

71. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.
foreign girlfriend

72. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: dating a skinny girl

73. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
dating american women

74. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: dating a bodybuilder

75. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
foreign dating

76. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: best bbw dating sites

77. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
best dating sites uk

78. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: speed dating questions

79. I really thank you for that great post and Please add a more new post. Do well...!For more information visit this site:
dating tips

80. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: dating a nurse

82. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
weird sex

83. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: how to flirt with a guy

84. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
dating website

85. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: kiss on first date

86. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
dating websites

87. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: russian brides

dating online

89. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: mature women

90. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
online dating apps

91. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: younger females

92. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
top dating website

93. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again. For more information visit this site: sexy black girls

94. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.For more information visit this site:
couple counsellor

97. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: ebony girls

98. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.For more information visit this site:
world best sex site

99. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
online dating sites

100. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: milf dating

101. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: exclusive relationship

102. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
best dating apps

103. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: best hook up

104. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
black men and white women

106. Nice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
hot chubby teen

108. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.For more information visit this site:
how to approach a girl

109. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners. For more information visit this site: younger teens babes

110. To be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: younger teens babes

dating sites

112. I really thank you for that great post and Please add a more new post. Do well...! When it comes to choosing a sexy girl for dating. Most of the men on this earth planet want to find a Slavic woman. You aren’t supposed to be an exception. For more information visit this site: hot women

113. Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.For more information visit this site:
married dating

114. Wow, amazing blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your website is fantastic, let alone the content! For more information visit this site: how to get a girl to like you

bodybuilder dating

116. Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners.For more information visit this site:
chubby women

117. Hey there. I found your blog by the use of Google while looking for a comparable subject, your site got here up.It appears to be good. Amazing article written. I usually don't read such articles but your article is just too good. For more information visit this site:
blacked sex

118. Excellent blog thanks for sharing the valuable information..it becomes easy to read and easily understand the information.
Useful article which was very helpful. also interesting and contains good information.

Python Training in chennai

Python Course in chennai

119. dccornerstone merupakan Situs Judi Online Terbaru Dan Taruhan Togel Online Pasaran Lengkap dengan berani memberikan keuntungan yang besar.

120. My self Assliming Chel and I am the blogger, Publisher, and writer. I love to write on Digital Marketing related topics. Writing is my hobby, I like to know the latest information about Web Development and which I said before, I searching all those things on the internet, I research all those and basis on those result I love to write. VB Web & Software Solution

121. Blog Informasi Togel Online Terpercaya Tahun 2020 http://alaskaagresources.com/ menginformasikan seputar permainan judi togel Online, Toto Online, Daftar togel online terpercaya Di Indonesia dan trik menang togel terbaru. Jadi kalian akan mendapatkan berbagai trik mudah menang dan menghasilkan uang jutaan perhari.

122. Read reviews of the best USA online *Real Casino* of 2020. Read honest and unbiased online casino reviews before you pick your next site.For more information visit this site: allslotscasino

123. Casino of Dreams may not be as established as some of its competitors, but this doesn’t mean that it doesn’t have plenty to offer! This is a Microgaming casino, meaning that it has a decent game selection of around 350 titles from the industry giant, plus the ever-popular live casino suite from Evolution Gaming. casino of dreams