23
$\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$?

Improve this question
$\endgroup$
6
  • 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
    Commented Apr 18, 2016 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
    Commented Apr 18, 2016 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
    Commented Apr 19, 2016 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
    Commented Apr 19, 2016 at 1:48
  • $\begingroup$ @KevinO'Bryant, does my answer address your specific question? $\endgroup$
    – kodlu
    Commented Apr 29, 2016 at 23:46

1 Answer 1

Reset to default
29
$\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.

Improve this answer
$\endgroup$
6
  • 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$
    – MERTON
    Commented Apr 18, 2016 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.
    Commented Apr 18, 2016 at 19:34
  • 1
    $\begingroup$ @MertSaglam, thanks for pointing out Stanica's nice result, I wasn't aware of it. $\endgroup$
    – kodlu
    Commented Apr 19, 2016 at 0:39
  • 2
    $\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
    Commented Oct 12, 2017 at 12:56
  • 3
    $\begingroup$ This inequality can be written in a simpler way without using the entropy function: since $n h (k/n) = k \ln(n/k) + (n-k)\ln(n/(n-k))$, $\exp(\cdot) = (n/k)^k\cdot (n/(n-k))^{n-k} = {n^n \over k^k (n-k)^{n-k}}$, so both the upper and the lower bounds are constant multiples of ${n^{n+1/2} \over k^{k+1/2} (n-k)^{n-k+1/2}}$. $\endgroup$
    – Erel Segal-Halevi
    Commented Sep 19, 2018 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .