anlak.com

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();
    }
  }

123 comments:

  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  6. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Russianbrides.com

    ReplyDelete
  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

    ReplyDelete
  8. 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: Russianbrides.com Login

    ReplyDelete
  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

    ReplyDelete
  10. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Hot Russian Brides

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  15. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: African Dating Sites

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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  20. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: arabiandate com

    ReplyDelete
  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

    ReplyDelete
  22. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Asian Dating

    ReplyDelete
  23. I really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: CharmDate Com Login

    ReplyDelete
  24. 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: CharmDate Login

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  27. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Zoosk Dating Service

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

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

    ReplyDelete
  32. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Amolatina News

    ReplyDelete
  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


    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  36. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: Interracial dating sites

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  39. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: online dating

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

    ReplyDelete
  41. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: how to find a girlfriend

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

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

    ReplyDelete
  48. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: tinder vs match

    ReplyDelete
  49. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
    For more information visit this site:
    find a date

    ReplyDelete
  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

    ReplyDelete
  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.
    For more information visit this site:
    online dating apps

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  55. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: best hookup sites

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  59. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
    For more information visit this site:
    girl sexy

    ReplyDelete
  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.
    For more information visit this site:
    dating hot women

    ReplyDelete
  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

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

    ReplyDelete
  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

    ReplyDelete
  64. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
    For more information visit this site:
    how to date a latina

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  67. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.For more information visit this site:
    country girl dating

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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.
    For more information visit this site:
    foreign girlfriend

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  81. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: dating a widower

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  88. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.For more information visit this site:
    dating online

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  95. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: interracial dating

    ReplyDelete
  96. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.For more information visit this site:
    love advice chat

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  105. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: how to ask someone out

    ReplyDelete

  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

    ReplyDelete
  107. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update. For more information visit this site: interracial dating

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  111. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.For more information visit this site:
    dating sites

    ReplyDelete
  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

    ReplyDelete

  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

    ReplyDelete
  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

    ReplyDelete
  115. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.For more information visit this site:
    bodybuilder dating

    ReplyDelete


  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

    ReplyDelete
  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

    ReplyDelete
  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.
    to know about python training course , use the below link.

    Python Training in chennai

    Python Course in chennai

    ReplyDelete
  119. 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

    ReplyDelete
  120. 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.

    ReplyDelete
  121. 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

    ReplyDelete
  122. 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

    ReplyDelete