# proof of Prohorov inequality

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

 $\displaystyle\exp\left(x\right)-x-1$ $\displaystyle\leq$ $\displaystyle 2\left(\cosh\left(x\right)-1\right)$ $\displaystyle 2\left(\cosh\left(x\right)-1\right)$ $\displaystyle\leq$ $\displaystyle x\sinh\left(x\right)$

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

 $\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}\leq% \exp\left[-\sup_{t>0}\left(t\varepsilon-\psi(t)\right)\right]$

where

 $\psi(t)=\sum_{i=1}^{n}\left(\ln E\left[e^{tX_{i}}\right]-tE\left[X_{i}\right]\right)$

Keeping in mind that the condition

 $\Pr\left\{\left|X_{i}\right|\leq M\right\}=1\text{ \ }\forall i$

implies that, for all $i$,

 $E[\left|X_{i}\right|^{k}]\leq M^{k}\text{ \ }\forall k\geq 0$

(see here (http://planetmath.org/RelationBetweenAlmostSurelyAbsolutelyBoundedRandomVariablesAndTheirAbsoluteMoments) for a proof) and since $\ln x\leq x-1$ $\forall x>0$, and

 $E[\left|X\right|^{k}]\leq M^{k}\text{ \ }\Longrightarrow\text{ \ }E\left[\left% |X\right|^{k}\right]\leq E\left[X^{2}\right]M^{k-2}\text{ \ \ \ \ \ \ \ }% \forall k\geq 2,k\in N$

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

 $\displaystyle\psi(t)$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\left(\ln E\left[e^{tX_{i}}\right]-tE\left[X_{i}% \right]\right)$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n}E\left[e^{tX_{i}}\right]-tE\left[X_{i}\right]-1$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}E\left[e^{tX_{i}}-tX_{i}-1\right]$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n}2E\left[\cosh\left(tX_{i}\right)-1\right]$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n}E\left[tX_{i}\sinh\left(tX_{i}\right)\right]$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n}E\left[\left|tX_{i}\sinh\left(tX_{i}\right)\right|\right]$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}tE\left[\left|X_{i}\right|\sinh\left(t\left|X_{i}% \right|\right)\right]$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}tE\left[\sum_{k=0}^{\infty}\frac{t^{2k+1}\left|X_{i% }\right|^{2k+2}}{\left(2k+1\right)!}\right]$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}t\sum_{k=0}^{\infty}\frac{t^{2k+1}E\left[\left|X_{i% }\right|^{2k+2}\right]}{\left(2k+1\right)!}$ $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n}t\sum_{k=0}^{\infty}\frac{t^{2k+1}E\left[X_{i}^{2}% \right]M^{2k}}{\left(2k+1\right)!}$ $\displaystyle=$ $\displaystyle\frac{t}{M}\sum_{k=0}^{\infty}\frac{t^{2k+1}M^{2k+1}\sum_{i=1}^{n% }E\left[X_{i}^{2}\right]}{\left(2k+1\right)!}$ $\displaystyle=$ $\displaystyle\frac{tv^{2}}{M}\sum_{k=0}^{\infty}\frac{\left(tM\right)^{2k+1}}{% \left(2k+1\right)!}$ $\displaystyle=$ $\displaystyle\frac{tv^{2}}{M}\sinh\left(tM\right).$

One can now write

 $\sup_{t>0}\left(t\varepsilon-\psi(t)\right)\geq\sup_{t>0}\left(t\varepsilon-% \frac{tv^{2}}{M}\sinh\left(tM\right)\right)=\sup_{t>0}\left[\frac{v^{2}}{M^{2}% }\left(\frac{M^{2}\varepsilon}{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\varepsilon}{v^{2}}=Mt_{opt}\cosh\left(Mt_{opt}\right)+\sinh\left(Mt_{% opt}\right)$

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

 $\widetilde{t}=\frac{1}{M}\operatorname{arsinh}\left(\frac{M\varepsilon}{2v^{2}% }\right)$

which, once plugged into the bound, yields

 $\Pr\left\{\sum_{i=1}^{n}\left(X_{i}-E[X_{i}]\right)>\varepsilon\right\}\leq% \exp\left[-\frac{v^{2}}{M^{2}}\left(\frac{M\varepsilon}{2v^{2}}\operatorname{% arsinh}\left(\frac{M\varepsilon}{2v^{2}}\right)\right)\right]$
Title proof of Prohorov inequality ProofOfProhorovInequality 2013-03-22 16:12:58 2013-03-22 16:12:58 Andrea Ambrosio (7332) Andrea Ambrosio (7332) 14 Andrea Ambrosio (7332) Proof msc 60E15