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();
}
}
Nice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: Latin Women Dating
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
ReplyDeleteThanks 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
ReplyDeleteThank 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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...! For more information visit this site: Russianbrides
ReplyDeleteI 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
ReplyDeleteThanks 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
ReplyDeleteThank 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
ReplyDeleteI 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
ReplyDeleteI 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: Sexy Russian Ladies
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
ReplyDeleteThank 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
ReplyDeleteThank 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
ReplyDeleteI 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: ChinaLove
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
ReplyDeleteThanks 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
ReplyDeleteThank 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
ReplyDeleteI 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: Cupid Dating
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
ReplyDeleteI 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
ReplyDeleteThank 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
ReplyDeleteThanks 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: Zoosk Dating Sites
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
ReplyDeleteI 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
ReplyDeleteThank 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
ReplyDeleteThanks 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: amolatinawomen
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
ReplyDeleteThank 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
ReplyDeleteI 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: 100 percent free dating sites
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...!For more information visit this site:
ReplyDeletebest dating websites
Nice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
good dating sites
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...!
ReplyDeleteFor more information visit this site:
love date
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
how to date
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
ReplyDeleteThank 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
tips for women
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...!
ReplyDeleteFor more information visit this site:
rules of dating
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
ReplyDeleteI have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
ReplyDeleteFor more information visit this site:
find a date
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
ReplyDeleteThank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners.
ReplyDeleteFor more information visit this site:
online dating apps
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
ReplyDeleteNice Content!
ReplyDeleteI 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
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
ReplyDeleteI 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
ReplyDeleteTo be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: dating pics
ReplyDeleteThank 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
ReplyDeleteWow, 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
ReplyDeleteI have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
ReplyDeleteFor more information visit this site:
girl sexy
Thank you very much for the information which you provide in your post. I have read your post. you provide great information for beginners.
ReplyDeleteFor more information visit this site:
dating hot women
Nice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site: a girl thinking
I really thank you for that great post and Please add a more new post. Do well...!
ReplyDeleteFor more information visit this site:
dating a latina
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
ReplyDeleteI have read your blog and I gathered some needful information from your blog. Keep update your blog. Waiting for your next update.
ReplyDeleteFor more information visit this site:
how to date a latina
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
ReplyDeleteThanks 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
ReplyDeleteI 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:
ReplyDeletecountry girl dating
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
ReplyDeletemeet american
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
ReplyDeleteThanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.
ReplyDeleteFor more information visit this site:
foreign girlfriend
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
dating american women
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
ReplyDeleteforeign dating
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
best dating sites uk
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
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...!For more information visit this site:
ReplyDeletedating tips
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
ReplyDeleteI 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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
weird sex
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
dating website
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
dating websites
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
ReplyDeleteI 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:
ReplyDeletedating online
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
online dating apps
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
top dating website
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
ReplyDeleteThanks 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:
ReplyDeletecouple counsellor
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
ReplyDeleteI 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:
ReplyDeletelove advice chat
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
ReplyDeleteThanks 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:
ReplyDeleteworld best sex site
Nice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
online dating sites
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
ReplyDeleteTo be honest I found very helpful information on your blog, Thanks for providing us such Information. For more information visit this site: exclusive relationship
ReplyDeleteI really thank you for that great post and Please add a more new post. Do well...! For more information visit this site:
ReplyDeletebest dating apps
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
ReplyDeleteNice Content!
ReplyDeleteI like this content very much. I need like this content for Dating niche. For more information visit this site:
black men and white women
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
ReplyDeleteNice Content!
I like this content very much. I need like this content for Dating niche. For more information visit this site:
hot chubby teen
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
ReplyDeleteThanks 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:
ReplyDeletehow to approach a girl
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
ReplyDeleteTo 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
ReplyDeleteI 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:
ReplyDeletedating sites
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
ReplyDeleteThanks 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
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
ReplyDeleteI 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:
ReplyDeletebodybuilder dating
ReplyDeleteThank 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
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:
ReplyDeleteblacked sex
Excellent blog thanks for sharing the valuable information..it becomes easy to read and easily understand the information.
ReplyDeleteUseful 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
dccornerstone merupakan Situs Judi Online Terbaru Dan Taruhan Togel Online Pasaran Lengkap dengan berani memberikan keuntungan yang besar.
ReplyDeleteMy 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
ReplyDeleteBlog 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.
ReplyDeleteRead 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
ReplyDeleteCasino 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