Let C(n,k) be the binomial coefficient "n choose k". We want to bound the sum of these, with k ranging from 0 to d. This is equivalent to bounding the volume of the n-dimensional Hamming ball of radius d. Denote this number by B(n,d).
A well-known bound (appearing, for example, in the Sauer-Shelah-VC lemma) is
B(n,d) <= (en/d)^d .
We are pretty sure that it can be sharpened, for example by writing a (1/2) in front of the RHS. (We actually think it can be sharpened by better than a constant.)
Thus has to be known. Anyone have a reference? Thanks in advance!
Subscribe to:
Post Comments (Atom)
3 comments:
I don't have a reference off the top of my head.
But for large n, B(n,d) = C(n,d) (1 + O(1/n)). So it's enough to bound C(n,d).
And C(n, d) = n^d/d! (1 + O(1/n)) for large n.
Finally, d! ~ sqrt(2πd) (d/e)^d (Stirling), giving
C(n,d) ~ (2πd)^(-1/2) (en/d)^d.
I won't bother making this more precise because I'm not sure how n and d are going to infinity in this constant. But this gives an improvement of the well-known bound by a factor of (2πd)^(1/2).
Thanks Michael. I kind of wanted to avoid re-proving this, since it must be well-known!.. I'll keep hoping that some kind soul will throw a reference my way...
It seems like there are a lot of expressions that look kind of like the bound you want in Alon and Spencer, The Probabilistic Method, 2nd edition (2000), especially Chapter 14 on "Codes, Games, and Entropy". That may be a good place to start looking.
Post a Comment