We study inequalities that play important roles in obtaining Chernoff bounds. These inequalities are related to the following function defined as

h(t)=(1+t)ln⁡(1+t)−t ,∀t>−1. h(t) = (1 + t) \ln (1 + t) - t\,,\qquad \forall t > -1.

Note that

h′(t)=ln⁡(1+t) ,h(2+n)(t)=(−1)n⋅n!⋅(1+t)−(n+1) ,∀n∈N \begin{aligned} h'(t) &= \ln (1 + t) \,, \\ h^{ (2 + n) } (t) &= (-1)^n \cdot n! \cdot (1 + t)^{ - (n + 1) } \,, \qquad \forall n \in \mathbb{N} \end{aligned}

Hence,

h(0)=h′(0)=0 , and h(2+n)(0)=(−1)n⋅n! ,∀n∈N . \begin{aligned} h(0) = h'(0) = 0 \,, \text{ and } \quad h^{ (2 + n) } (0) = (-1)^n \cdot n!\,, \qquad \forall n \in \mathbb{N} \,. \end{aligned}

Inequalities

♢\diamondsuit

h(t)≥11+t⋅t22 h(t) \ge \frac{1}{1 + t} \cdot \frac{t^2}{2}

Plot of h(t)−11+t⋅t22h(t) - \frac{1}{1 + t} \cdot \frac{t^2}{2}.

Proof.

Via Taylor's expansion, ∃c∈[0,t]\exists c \in [0, t], s.t.,

h(t)=h(0)+h′(0)⋅t+h′′(c)⋅t22=11+c⋅t22≥11+t⋅t22. \begin{aligned} h(t) = h(0) + h'(0) \cdot t + h''(c) \cdot \frac{t^2}{2} = \frac{1}{1 + c} \cdot \frac{t^2}{2} \ge \frac{1}{1 + t} \cdot \frac{t^2}{2}. \end{aligned}

□\square

♣\clubsuit

h(t)≥t22+t=11+t/2⋅t22 h(t) \ge \frac{t^2}{2 + t} = \frac{1}{1 + t /2 } \cdot \frac{t^2}{2}

Plot of h(t)−11+t/2⋅t22h(t) - \frac{1}{1 + t / 2} \cdot \frac{t^2}{2}.

Proof. By convexity of f(x)≐1/(1+tx)f(x) \doteq 1 / (1 + tx), we have

ln⁡(1+t)=∫0111+tx d (tx)≥t⋅11+∫01tx d x=t1+t/2. \ln (1 + t) = \int_0^1 \frac{1}{1 + tx} \, d\, (tx) \ge t \cdot \frac{1}{1 + \int_0^1 tx \, d\, x } = \frac{t}{1 + t / 2}.

It follows that

h(t)=(1+t)ln⁡(1+t)−t≥t2+t−t−t2/21+t/2=t2/21+t/2. h(t) = (1 + t) \ln (1 + t) - t \ge \frac{t^2 + t - t - t^2 / 2}{1 + t / 2} = \frac{t^2 / 2}{1 + t / 2}.

□\square

♠\spadesuit

h(t)≥t22+(2/3)⋅t=11+t/3⋅t22 h(t) \ge \frac{t^2}{2 + (2 / 3) \cdot t} = \frac{1}{1 + t / 3} \cdot \frac{t^2}{2}

Plot of h(t)−11+t/3⋅t22h(t) - \frac{1}{1 + t / 3} \cdot \frac{t^2}{2}.

Proof 1.

h(t)−h(0)=∫01h′(tx) d (tx)=∫01(h′(0)+∫0xh′′(ty) d (ty))d (tx)=h′(0)⋅t+t2∫01(∫0xh′′(ty) d y)d x \begin{aligned} h(t) - h(0) &= \int_0^1 h'( tx) \, d\, (tx) \\ &= \int_0^1 \left( h'(0) + \int_0^x h''( ty) \, d\, (ty) \right) d\, (tx) \\ &= h'(0) \cdot t + t^2 \int_0^1 \left( \int_0^x h''( ty) \, d\, y \right) d\, x \\ \end{aligned}

Substituting h(0)=h′(0)=0h(0) = h'(0) = 0, and h′′(ty)=1/(1+ty)h''(ty) = 1 / (1 + ty), we get

h(t)=t2∫01∫0x11+ty d y d x. \begin{aligned} h(t) &= t^2 \int_0^1 \int_0^x \frac{1}{1 + ty} \, d\, y \, d\, x . \end{aligned}

Let S≐{0≤x≤1,0≤y≤x}S \doteq \{ 0 \le x \le 1, 0 \le y \le x \}. Its area, denoted as ∣S∣|S|, equals 1/21 / 2.

Consider the convex function f(x,y)=1/(1+ty)f(x, y) = 1 / (1 + ty) defined on SS. By Jensen's inequality,

1∣S∣⋅∫01∫0x11+ty d y d x≥11+t⋅∫01∫0x1∣S∣⋅y d y d x=11+t/3. \begin{aligned} \frac{1}{|S|} \cdot \int_0^1 \int_0^x \frac{1}{1 + ty} \, d\, y \, d\, x &\ge \frac{1}{1 + t \cdot \int_0^1 \int_0^x \frac{1}{|S|} \cdot y \, d\, y \, d\, x } = \frac{1}{1 + t / 3}. \end{aligned}

□\square

Proof 2. Define

f(t)=h(t)−3t+3⋅t22=h(t)−32⋅t2−9+9t+3=h(t)−32⋅(t−3+9t+3) \begin{aligned} f(t) &= h(t) - \frac{3}{t + 3} \cdot \frac{t^2}{2} \\ &= h(t) - \frac{3}{2} \cdot \frac{t^2 - 9 + 9}{t + 3} \\ &= h(t) - \frac{3}{2} \cdot \Big( t - 3 + \frac{9}{t + 3} \Big) \end{aligned}

Then

f′(t)=ln⁡(1+t)−32⋅(1−9(t+3)2) ,f′′(t)=11+t−27(t+3)3=t3+3t2⋅3+3t⋅9+27−27−27t(1+t)(t+3)3=t3+9t2(1+t)(t+3)3≥0. \begin{aligned} f'(t) &= \ln (1 + t) - \frac{3}{2} \cdot \Big( 1 - \frac{9}{(t + 3)^2} \Big) \,, \\ f''(t) &= \frac{1}{1 + t} - \frac{27}{ (t + 3)^3 } \\ &= \frac{ t^3 + 3 t^2 \cdot 3 + 3 t \cdot 9 + 27 - 27 - 27t }{ (1 + t) (t + 3)^3} \\ &= \frac{ t^3 + 9 t^2 }{ (1 + t) (t + 3)^3} \\ &\ge 0. \end{aligned}

Hence, for all t≥0t \ge 0,

f′(t)≥f′(0)=0 ,f(t)≥f(0)=0. \begin{aligned} f'(t) &\ge f'(0) = 0 \,, \\ f(t) &\ge f(0) = 0. \end{aligned}

□\square

Reference

[1]. David Pollard. Chapter 2, MiniEmpirical. http://www.stat.yale.edu/~pollard/Books/Mini/, 2015. Manuscript