Corollary to Chernoff's bound: $P(x \geq a+b) \leq e^{-2b^2/n}$

Question

Our information theory textbook says as a easy corollary to Chernoff's bound ($P(x>a+b)\leq e^{-n\mathbb{RE}[p+\frac{b}{n}||p]}$), we have $P(x>a+b)\leq e^{-2b^2/n}$, where $\mathbb{RE}[p+\frac{b}{n}||p]=(p+\frac{b}{n})ln\left(\frac{p+\frac{b}{n}}{p}\right)+(1-p-\frac{b}{n})ln\left(\frac{1-p-\frac{b}{n}}{1-p}\right)$. I tried using Taylor Sereis expansion to bound the relative entropy, but did not really get anywhere.

Answer 1

Set $b/n = \epsilon$. Then you need to show $$ \mathbb{RE}(p+\epsilon \| p) \ge 2\epsilon^2$$ for $\epsilon \in (-p, 1-p).$ ($\epsilon = -p$ and $1-p$ are both trivialities, since the LHS is $\infty$ in this case.)

For convenience we will think of $p$ as fixed, and set $u = p + \epsilon.$ Note that $u \in (0,1).$ Let $$f(u) = \mathbb{RE}(u \|p) = u \ln(u) - u\ln(p) + (1-u) \ln(1-u) - (1-u) \ln(1-p).$$

We find that $$ f'(u) = \log \frac{u}{1-u} - \log \frac{p}{1-p}$$

and that (for $u \in (0,1)$), $$f''(u) = \frac{1}{u} + \frac{1}{1-u} \ge 4.$$

(Prove the above). Thus, $f$ is a strongly convex function of $u$. Using strong convexity, we find that for $u \in (0,1),$ $$ f(u) \ge f(p) + f'(p) (u-p) + \frac{1}{2} (4(u-p)^2)$$

But $f(p) = f'(p) = 0.$ Resubstituting $u = p+ \epsilon$ yields the required result.

---

The intuition for this bound really arises from noting that $\mathbb{RE}(p+\epsilon \| p)$ has a local minima at $\epsilon = 0,$ so one should at least be able to locally lower bound it by a quadratic. This happily extends to the entirety of the domain of $\epsilon$ since we find, on computing the second derivate, that the function is actually strongly convex.