In a blog post, rjlipton proves that 14nkk!≤(nk)≤nkk! when k≤√n. I posted a comment trying to strengthen the first inequality to 12nkk!<(nk) That comment is almost unreadable because (1) I don't know how to use LaTeX on wordpress, (2) especially if I get only one try (can't edit). Here, I don't have such problems.
Proof. Consider a hashtable with n buckets and k items. There are nk ways to distribute the items, out of which (nk)k! have no collision. The probability of having some collision is 1−(nk)k!/nk. Now suppose Y is a random variable whose value says how many collisions there are. So, P(Y>0)=1−(nk)nk/k!≤EY The inequality comes from the first moment principle. The expected number of collisions increases with k, so we just look at the case k=√n. There are √n(√n−1)/2 possible collisions, each happening with probability 1/n. Thus, EY=√n(√n−1)21n=12−12√n Putting the previous two displayed inequalities together, we get 1−(nk)nk/k!≤12−12√n and finally (nk)nk/k!≥12+12√n>12
Update: Stefan Kiefer pointed out that the tight bounds are 1√enkk!<(nk)≤nkk!if k≤√n
No comments:
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.