Skip to main content
2 of 4
added 575 characters in body
Iosif Pinelis
  • 142.6k
  • 9
  • 121
  • 260

This follows immediately from a theorem due by Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)).$$ So, we get \eqref{10}.

Iosif Pinelis
  • 142.6k
  • 9
  • 121
  • 260