19
$\begingroup$

Motivated by the central limit theorem, one expects that $$\binom{n}{k} \approx \frac{2^n}{\sqrt{\pi n/2}} \exp\left(-\frac{(k-n/2)^2}{n/2}\right).$$ Computations suggest that the ratio of the two sides approaches 1 only for $|k-n/2| < 2\sqrt{n}$, and presumably this will follow from some version of the CLT.

In the literature or standard usage, are there any explicit upper (and lower?) bounds for binomial coefficients with a similar form that are sharp (in the ratio sense) for a wider range of $k$?

$\endgroup$
  • 1
    $\begingroup$ How about using Stirling's approximation to factorial when k is a significant fraction of n? Gerhard "How Good Is Good Really?" Paseman, 2016.04.17. $\endgroup$ – Gerhard Paseman Apr 18 '16 at 4:26
  • 1
    $\begingroup$ So using Stirling's formula, you get an approximation to within a (small) constant simultaneously valid for all $n$ and $k$. $\endgroup$ – Anthony Quas Apr 18 '16 at 4:41
  • $\begingroup$ Stirling's formula is indeed awesome, but it leaves one with $k^k$ and $(n-k)^{n-k}$ factors which are too cumbersome to work with in my application. $\endgroup$ – Kevin O'Bryant Apr 19 '16 at 1:15
  • $\begingroup$ Can you say more about your application? It seems like the kind of bound you want depends a lot on how you're using it. (And for instance if you care about sums of binomial coefficients, this may not be the best approach.) $\endgroup$ – usul Apr 19 '16 at 1:48
  • $\begingroup$ @KevinO'Bryant, does my answer address your specific question? $\endgroup$ – kodlu Apr 29 '16 at 23:46
22
$\begingroup$

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have $$ \sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\} $$ where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.

This result is most certainly not mine, I learned it from Bob Gallager's Information Theory and Reliable Communications.

$\endgroup$
  • $\begingroup$ Do you have a source for this? If this is an original result, do you have a blog post or similar that shows the other manipulations? $\endgroup$ – ShadSterling Apr 18 '16 at 16:00
  • 2
    $\begingroup$ See this: eudml.org/doc/121842. Stanica's paper even improves the lower bound to $1-1/(32n)$ times the upper bound given by kodlu. $\endgroup$ – Mert Sağlam Apr 18 '16 at 18:42
  • 1
    $\begingroup$ Shouldn't the minus signs in the exponents be removed? As it is, it looks like for say $k=\frac{n}{2}$ both upper and lower bound go to $0$. $\endgroup$ – Clement C. Apr 18 '16 at 19:34
  • 1
    $\begingroup$ @MertSaglam, thanks for pointing out Stanica's nice result, I wasn't aware of it. $\endgroup$ – kodlu Apr 19 '16 at 0:39
  • 1
    $\begingroup$ The bounds given in this answer are also stated in "The Theory of Error-Correcting Codes" by MacWilliams and Sloane (Chapter 10, Lemma 7, p309). $\endgroup$ – Ashley Montanaro Oct 12 '17 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.