proof of Bennett inequality

By Chernoff-Cramèr inequality (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\ge 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).$$

Keeping in mind 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) and since $\ln x\le x-1$ $\forall x>0$, and

$$E[{\left|X\right|}^k]\le M^k⟹E\left[{\left|X\right|}^k\right]\le E\left[X^2\right]M^{k-2}\forall k\ge 2,k\in N$$

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

$\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[{\displaystyle \sum _{k=0}^{\mathrm{\infty }}}{\displaystyle \frac{{\left(t{X}_i\right)}^k}{k!}}\right]-tE\left[X_i\right]-1$

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

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

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

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

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

$=$ ${\displaystyle \frac{v^2}{M^2}}{\displaystyle \sum _{k=2}^{\mathrm{\infty }}}{\displaystyle \frac{{\left(tM\right)}^k}{k!}}$

$=$ ${\displaystyle \frac{v^2}{M^2}}\left[\exp \left(tM\right)-tM-1\right]$

One can now write

$$\underset{t\ge 0}{sup}\left(t\epsilon -\psi (t)\right)\ge \underset{t\ge 0}{sup}\left(t\epsilon -\frac{v^2}{M^2}\left(e^{tM}-tM-1\right)\right)=\underset{t>0}{sup}\left[\frac{v^2}{M^2}\left(\frac{M^2\epsilon }{v^2}t-\left(e^{tM}-tM-1\right)\right)\right].$$

By elementary calculus, we obtain the value of $t$ that maximizes the expression in round brackets:

$$t_{opt}=\frac{1}{M}\ln \left(1+\frac{M\epsilon }{v^2}\right)$$

which, once plugged into the bound, yields

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

Observing that $\left(1+x\right)\ln \left(1+x\right)-x\ge \frac{x}{2}\ln \left(1+x\right)$ $\forall x\ge 0$ (see here (http://planetmath.org/ASimpleMethodForComparingRealFunctions)), one gets the sub-optimal yet more easily manageable formula:

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

Title	proof of Bennett inequality
Canonical name	ProofOfBennettInequality
Date of creation	2013-03-22 16:12:27
Last modified on	2013-03-22 16:12:27
Owner	Andrea Ambrosio (7332)
Last modified by	Andrea Ambrosio (7332)
Numerical id	22
Author	Andrea Ambrosio (7332)
Entry type	Proof
Classification	msc 60E15