proof of Prohorov inequality

Starting from the basic inequality $\exp \left(-x\right)\ge 1-x$, it’s easy to derive by elementary algebraic manipulations the two inequalities

$\exp \left(x\right)-x-1$ $\le$ $2\left(\cosh \left(x\right)-1\right)$

$2\left(\cosh \left(x\right)-1\right)$ $\le$ $x\sinh \left(x\right)$

By the 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)$$

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[e^{t{X}_i}-t{X}_i-1\right]$

$\le$ ${\displaystyle \sum _{i=1}^n}2E\left[\cosh \left(t{X}_i\right)-1\right]$

$\le$ ${\displaystyle \sum _{i=1}^n}E\left[t{X}_i\sinh \left(t{X}_i\right)\right]$

$\le$ ${\displaystyle \sum _{i=1}^n}E\left[\left|t{X}_i\sinh \left(t{X}_i\right)\right|\right]$

$=$ ${\displaystyle \sum _{i=1}^n}tE\left[\left|X_i\right|\sinh \left(t\left|X_i\right|\right)\right]$

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

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

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

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

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

$=$ ${\displaystyle \frac{t{v}^2}{M}}\sinh \left(tM\right).$

One can now write

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

Optimizing this expression with respect to $t$ would lead to solving the transcendental equation:

$$\frac{M\epsilon }{v^2}=M{t}_{opt}\cosh \left(M{t}_{opt}\right)+\sinh \left(M{t}_{opt}\right)$$

which is analytically infeasible. So, one can choose the sup-optimal yet manageable solution

$$\tilde{t}=\frac{1}{M}\mathrm{arsinh}\left(\frac{M\epsilon }{2v^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(\frac{M\epsilon }{2v^2}\mathrm{arsinh}\left(\frac{M\epsilon }{2v^2}\right)\right)\right]$$

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