4
$\begingroup$

I'm reading that recent paper on a new bound for diagonal Ramsey and am stuck at the attached "Fact 12.1", which is "standard".fact 12.1

Could anyone please point me to a source for this fact, including a proof?

$\endgroup$
2
  • 11
    $\begingroup$ $1=(p+(1-p))^a\geqslant {a\choose b}p^b(1-p)^{a-b}$, where $p=b/a$. Take $\log_2$ and get this bound $\endgroup$ Commented Jun 23 at 16:05
  • 2
    $\begingroup$ Many thanks! I'm formalising the paper, and the argument above went in smooth as butter $\endgroup$ Commented Jun 24 at 9:23

4 Answers 4

8
$\begingroup$

Fedor Petrov's comment is the key but is perhaps a little terse for someone unfamiliar with this style of argument. Here is a more leisurely explanation. The tools required here are very elementary, nothing complicated is needed.

First, a warmup: observe that the Taylor series identity $e^x = \sum_{n \ge 0} \frac{x^n}{n!}$ implies, for $x \ge 0$, the inequality $e^x \ge \frac{x^n}{n!}$ (just by deleting all the other terms in the Taylor series), and hence gives a lower bound

$$n! \ge \frac{x^n}{e^x}$$

on the factorial, which depends on a real parameter $x \ge 0$. Now we can attempt to optimize this bound as a function of $x$, and an easy computation of the logarithmic derivative implies that we should take $x = n$, which gives

$$\boxed{ n! \ge \frac{n^n}{e^n} }.$$

This is a simple form of Stirling's approximation; I learned this argument from Terence Tao's notes here. It has the following probabilistic interpretation (which can be safely ignored if you're happy with the above argument but which I think is enlightening as to the meaning of this inequality):

$e^{-\lambda} \frac{\lambda^n}{n!}$ is the probability that a Poisson random variable with mean $\lambda$ takes the value $n$. For large values of $\lambda$ the Poisson distribution is asymptotically Gaussian (this can be verified by a direct calculation but is also a special case of the central limit theorem) and in particular its mean is asymptotically its mode, so if we want to maximize this probably we should take $\lambda = n$, which is in fact its maximum value, and the CLT moreover tells us that this maximum probability is approximately $\frac{1}{\sqrt{2\pi n}}$. The bound above comes from observing that probabilities are bounded by $1$, while the more precise Stirling's approximation incorporates this factor of $\frac{1}{\sqrt{2\pi n}}$, which here has the conceptual interpretation as being inversely proportional to the standard deviation of the limiting Gaussian distribution.

Now suppose we want to use the same idea to bound the binomial coefficients. A natural idea is to use the binomial theorem

$$(x + y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}$$

which for $x, y \ge 0$ gives the inequality $(x + y)^n \ge {n \choose k} x^k y^{n-k}$ and hence, setting $p = \frac{x}{x + y}$, the upper bound

$${n \choose k} \le \frac{1}{p^k (1 - p)^{n-k}}.$$

Now we would again like to optimize this bound as a function of $p$, and again an easy computation of the logarithmic derivative implies that we should take $p = \frac{k}{n}$, which gives

$$\boxed{ {n \choose k} \le \frac{n^n}{k^k (n - k)^{n-k}} }.$$

Taking logarithms gives the entropy bound. This argument also has a probabilistic interpretation, which is probably more obvious:

${n \choose k} p^k (1 - p)^{n-k}$ is the probability that a binomial random variable $\text{Bin}(n, p)$ takes the value $k$. For large values of $n$ this distribution is again asymptotically Gaussian, which can again be verified either by a direct computation or by appealing to the central limit theorem, which again means that its mean is asymptotically its mode. We can also appeal to the law of large numbers: as $n \to \infty$ the most likely value of $k$ is the most likely number of coin flips if we flip $n$ coins with a bias of $p$, which should be (and is) $k = np$ (assuming this is an integer). So $p = \frac{k}{n}$ optimizes the above inequality. The inequality itself again comes from the observation that probabilities are bounded by $1$, and a more refined square-root factor can be obtained conceptually from the CLT again or directly from Stirling's approximation.

$\endgroup$
3
$\begingroup$

This follows immediately from a theorem due to 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)). \tag{20}\label{20}$$ So, we get \eqref{10}.


In fact, as seen from \eqref{20}, much stronger inequalities than \eqref{10} hold: $$\sum_{j=k}^n\binom nj\le\exp(-nH(k/n))\quad\text{if }k\ge n/2$$ and, equivalently, $$\sum_{j=0}^k\binom nj\le\exp(-nH(k/n))\quad\text{if }k\le n/2.$$

$\endgroup$
3
  • 1
    $\begingroup$ why is the equation labeled (10)? $\endgroup$ Commented Jun 23 at 18:00
  • $\begingroup$ @ZachHunter : With MathJax, this kind of enumeration seems convenient -- then it is easy to add intermediate equation numbers, such as (15). $\endgroup$ Commented Jun 23 at 18:04
  • 1
    $\begingroup$ @IosifPinelis a bit like programming in Basic in the 80s ;-) $\endgroup$
    – David Roberts
    Commented Jun 24 at 6:10
3
$\begingroup$

In my opinion, Fedor Petrov's answer is very slick and the right explanation. But a routine way to verify this fact, at least for purposes of this paper, is to simply apply Stirling's formula.

We mostly care about the regime where $b= p\cdot a$ for some $p\in [0.001,0.999]$. Recall that Stirling's formula says that $n! \sim C\sqrt{n}\cdot (n/e)^n$ for some constant $C$. Let's just forget about the non-exponential part, and pretend $n! "=" (n/e)^n$ (in the actual computation, the lower order terms are actually in one's favor, but for the purposes of this Ramsey result, you can ignore these subexponential factors).

Okay, so now $$\binom{a}{b} = \frac{a!}{b!(a-b)!} "="\frac{(a/e)^a}{(b/e)^b ((a-b)/e)^{a-b}} = \frac{a^a}{b^b (a-b)^{a-b}}$$ $$=\frac{1}{(b/a)^b ((a-b)/a)^{a-b}} = \frac{1}{p^{pa}(1-p)^{(1-p)a}}.$$Taking $\log_2$ of both sides gives $$ \log_2\binom{a}{b}"=" a\cdot (-p\log_2(p) -(1-p)\log_2(1-p)),$$as desired.

$\endgroup$
0
$\begingroup$

As noted in the previous answer, we can rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{100}\label{100}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$.

As was also noted in the previous answer, using an inequality of Hoeffding's, one can just as easily get much stronger inequalities than \eqref{100}: $$\sum_{j=k}^n\binom nj\le\exp(-nH(k/n))\quad\text{if }k\ge n/2 \tag{300}\label{300} $$ and, equivalently, $$\sum_{j=0}^k\binom nj\le\exp(-nH(k/n))\quad\text{if }k\le n/2. \tag{400}\label{400}$$

Here we are going to show that \eqref{300} (and, equivalently, \eqref{400}) can be obtained using the idea in the comment by Fedor Petrov and just a bit more.

Indeed, if $k\ge n/2$, then $p:=\frac kn\ge\frac12$ and hence $p\ge1-p$, and hence $$1\ge\sum_{j=k}^n\binom nj p^j(1-p)^{n-j} \ge\sum_{j=k}^n\binom nj p^k(1-p)^{n-k} =\sum_{j=k}^n\binom nj \exp(nH(k/n)),$$ so that \eqref{300} immediately follows.


On the other hand, this seems to provide a simpler proof of the mentioned inequality of Hoeffding's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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