proof of Prohorov inequality

Starting from the basic inequality $\\exp\\left(-x\\right)\\geq 1-x$ , it’seasy 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 thetranscendental 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 yetmanageable 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]