Loading [MathJax]/jax/output/CommonHTML/fonts/TeX/fontdata.js

13 February 2014

Approximation of Binomial Coefficients

A proof that 12nkk!<(nk).

In a blog post, rjlipton proves that 14nkk!(nk)nkk! when kn. 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(n1)/2 possible collisions, each happening with probability 1/n. Thus, EY=n(n1)21n=1212n Putting the previous two displayed inequalities together, we get 1(nk)nk/k!1212n and finally (nk)nk/k!12+12n>12

Update: Stefan Kiefer pointed out that the tight bounds are 1enkk!<(nk)nkk!if kn

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.