3

What is a published reference for the asymptotic equivalent of $ n \choose k$ with $k$ linear in $n$? I want both the entropy function and the denominator in $\sqrt{n}.$

Patrick Sole
  • 396
  • [tag:reference-request]? – Peter Taylor Feb 06 '19 at 13:49
  • I suspect that the asymptotics of ${n \choose \alpha n}$ are in "The Probabilistic Method" by Alon and Spencer, but I don't have a copy at hand right now. – Michael Lugo Feb 06 '19 at 15:30
  • Also, this is possibly a repeat of https://math.stackexchange.com/questions/1004005/asymptotic-behavior-of-n-choose-lfloor-alpha-n-rfloor or https://math.stackexchange.com/questions/1109921/limit-of-frac1n-logn-choose-np-without-using-stirlings-formula?rq=1 – Michael Lugo Feb 06 '19 at 15:31
  • The asymptotics in "The Probabilistic Method" by Alon and Spencer p.232 are incorrect. The term in $\sqrt{n}$ is missing. – Patrick Sole Feb 06 '19 at 15:55
  • See also https://math.stackexchange.com/questions/235962/asymptotics-of-binomial-coefficients-and-the-entropy-function – leonbloy Feb 10 '19 at 21:46
  • See also https://mathoverflow.net/questions/236508/are-there-good-bounds-on-binomial-coefficients/236511#236511 – kodlu Apr 28 '19 at 23:17

2 Answers2

3

The following appears (with proof) in Ash, Information Theory, 1965 as Lemma 4.7.1:

$$ \frac{2^{nH(p,1-p)}}{\sqrt{8np(1-p)}} \le {n \choose np} \le \frac{2^{nH(p,1-p)}}{\sqrt{2 \pi np(1-p)}} \,, $$ Here $H(p,1-p):=-p \log_2 p - (1-p) \log_2 (1-p)$ is the binary entropy function.

Artemy
  • 1,254
1

These lecture notes by David Galvin state the asymptotic expression (see the beginning of Section 3.1): \begin{align*} \binom{n}{\alpha n} &= \frac{2^{H(\alpha)n}}{\sqrt{2\pi\, n\, \alpha(1-\alpha)}} [1+o(1)] \qquad\text{as $n\to\infty$} \end{align*} for $0<\alpha<1$. He does not provide a proof, only that it follows from Stirling's approximation, so I assume the proof must be straightforward.

Blackbird
  • 1,985
  • This solves my question completely. But what about a sum of binomial coefficients like the volume of a hamming ball of radius $\alpha n$ – Patrick Sole Apr 30 '19 at 18:29