proof of Bernstein inequalities

1) By Chernoff-Cramèr bound (http://planetmath.org/ChernoffCramerBound), we have:

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le \exp \left[-\underset{t>0}{sup}\left(t\epsilon -\psi (t)\right)\right]$$

where

$$\psi (t)=\sum _{i=1}^n\left(\ln E\left[e^{t{X}_i}\right]-tE\left[X_i\right]\right)$$

Since $\ln x\le x-1$ $\forall x\ge 0$,

$\psi (t)$$=$${\displaystyle \sum _{i=1}^n}\left(\ln E\left[e^{t{X}_i}\right]-tE\left[X_i\right]\right)$

$\le$${\displaystyle \sum _{i=1}^n}E\left[e^{t{X}_i}\right]-tE\left[X_i\right]-1$

$=$${\displaystyle \sum _{i=1}^n}E\left[1+t{X}_i+{\displaystyle \frac{1}{2}}{t}^2{X}_i^2+{\displaystyle \sum _{k=3}^{+\mathrm{\infty }}}{\displaystyle \frac{t^k{X}_i^k}{k!}}\right]-tE\left[X_i\right]-1$

$=$${\displaystyle \sum _{i=1}^n}\left({\displaystyle \frac{1}{2}}{t}^{2}E\left[X_i^2\right]+{\displaystyle \sum _{k=3}^{+\mathrm{\infty }}}{\displaystyle \frac{t^{k}E\left[X_i^k\right]}{k!}}\right)$

$=$${\displaystyle \frac{1}{2}}{t}^2{\displaystyle \sum _{i=1}^n}E\left[X_i^2\right]+{\displaystyle \sum _{k=3}^{+\mathrm{\infty }}}{\displaystyle \frac{t^k{\sum }_{i=1}^{n}E\left[X_i^k\right]}{k!}}$

$\le$${\displaystyle \frac{1}{2}}{t}^2{\displaystyle \sum _{i=1}^n}E\left[X_i^2\right]+{\displaystyle \sum _{k=3}^{+\mathrm{\infty }}}{\displaystyle \frac{t^k{\sum }_{i=1}^{n}E\left[{\left|X_i\right|}^k\right]}{k!}},$

and, keeping in mind hypotheses a) and b),

$\psi (t)$$\le$${\displaystyle \frac{1}{2}}{t}^2{v}^2+{\displaystyle \sum _{k=3}^{+\mathrm{\infty }}}{\displaystyle \frac{t^k}{2}}{v}^2{c}^{k-2}={\displaystyle \frac{1}{2}}{t}^2{v}^2+{\displaystyle \frac{1}{2}}{t}^3{v}^{2}c{\displaystyle \sum _{k=0}^{+\mathrm{\infty }}}{\left(tc\right)}^k$

Now, if , we obtain

$$\psi (t)\le \frac{1}{2}{t}^2{v}^2\left(1+\frac{tc}{1-tc}\right)=\frac{v^2{t}^2}{2\left(1-tc\right)}$$

whence

By elementary calculus, we obtain the value of $t$ that maximizes theexpression in brackets (out of the two roots of the second degree polynomial equation, we choose the one which is ):

$$t_{opt}=\frac{v^2+2c\epsilon -v^2\sqrt{1+\frac{2c\epsilon }{v^2}}}{c\left(v^2+2c\epsilon \right)}=\frac{1}{c}\left(1-\frac{1}{\sqrt{1+\frac{2c\epsilon }{v^2}}}\right)$$

which, once plugged into the bounds, yields

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le \exp \left[-\frac{v^2}{c^2}\left(1+\frac{c\epsilon }{v^2}-\sqrt{1+2\frac{c\epsilon }{v^2}}\right)\right]$$

Observing that $\sqrt{1+x}\le 1+\frac{1}{2}x$, one gets:

Plugging $t^{\prime }$ in the bound expression, the sub-optimal yet moreeasily manageable formula is obtained:

$$\mathrm{Pr}\left\{\sum _{i=1}^n\left(X_i-E[X_i]\right)>\epsilon \right\}\le \exp \left(-\frac{{\epsilon }^2}{2\left(v^2+c\epsilon \right)}\right)$$

which is obviously a worse bound than the preceeding one, since $t^{\prime }\ne t_{opt}$. One can also verify the consistency of this inequalitydirectly proving that, for any $x\ge 0$,

$$1+x-\sqrt{1+2x}\ge \frac{x^2}{2\left(1+x\right)}$$

(see here (http://planetmath.org/ASimpleMethodForComparingRealFunctions) for an easy way, which can be used with $x_0=0$)

2) To prove this more specialized statement let’s recall that the condition

$$\mathrm{Pr}\left\{\left|X_i\right|\le M\right\}=1\forall i$$

implies that, for all $i$,

$$E[{\left|X_i\right|}^k]\le M^k\forall k\ge 0$$

(See here (http://planetmath.org/RelationBetweenAlmostSurelyAbsolutelyBoundedRandomVariablesAndTheirAbsoluteMoments) for a proof.)

Now, it’s enough to verify that the condition

$$E[{\left|X_i\right|}^k]\le M^k$$

imply both conditions a) and b) in part 1).

Indeed, part a) is obvious, while for part b) one happens to have:

$$E[{\left|X_i\right|}^k]\le E\left[X_i^2\right]M^{k-2}$$

(see here (http://planetmath.org/AbsoluteMomentsBoundingNecessaryAndSufficientCondition) for a proof).

So

$$\sum _{i=1}^{n}E[{\left|X_i\right|}^k]\le \sum _{i=1}^{n}E\left[X_i^2\right]M^{k-2}=v^2{M}^{k-2}$$

Let’s find a value for $c$ such that $v^2{M}^{k-2}\le \frac{k!}{2}{v}^2{c}^{k-2}$,thus satisfying part b) of the hypotheses.

After simplifying, we have to study the inequality

$$k!c^{k-2}\ge 2\cdot M^{k-2}$$

for any $k\ge 3$. Let’s proceed by induction. For $k=3$, we have

$$6c\ge 2M$$

which suggests $c=\frac{M}{3}$. Let’s now verify if this position isconsistent with the inductive hypothesis:

$$\left(k+1\right)!=\left(k+1\right)k!\ge \left(k+1\right)\cdot 2\cdot 3^{k-2}\ge 3\cdot 2\cdot 3^{k-2}=2\cdot 3^{(k+1)-2}$$

which confirms the validity of the choice $c=\frac{M}{3}$, which has to beplugged into the former bound to obtain the new one.

[to be continued…]