|
|
|
Viewing Version
10
of
'proof of Prohorov inequality'
|
[ view 'proof of Prohorov inequality'
|
back to history
]
| Title of object: |
proof of Prohorov inequality |
| Canonical Name: |
ProofOfProhorovInequality |
| Type: |
Proof |
| Created on: |
2006-09-04 14:42:25 |
| Modified on: |
2006-09-09 11:00:23 |
| Classification: |
msc:60E15 |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\DeclareMathOperator{\arsinh}{arsinh} |
Content:
Starting from the basic inequality $\exp \left( -x\right) \geq 1-x$, it's
easy to derive by elementary algebraic manipulations the two inequalities
\begin{eqnarray*}
\exp \left( x\right) -x-1 &\leq &2\left( \cosh \left( x\right) -1\right) \\
2\left( \cosh \left( x\right) -1\right) &\leq &x\sinh \left( x\right)
\end{eqnarray*}
By the \PMlinkname{Chernoff-Cram\`{e}r bound}{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)
\]
Since $\ln x\leq x-1$ $\forall x>0$ and%
\[
E[\left\vert X\right\vert ^{k}]\leq M^{k}\text{ \ }\Longrightarrow \text{ \ }%
E\left[ \left\vert X\right\vert ^{k}\right] \leq E\left[ X^{2}\right] M^{k-2}%
\text{ \ \ \ \ \ \ \ }\forall k\geq 2,k\in N
\]
(see \PMlinkname{here}{AbsoluteMomentsBoundingNecessaryAndSufficientCondition} for a proof), one has:
\begin{eqnarray*}
\psi (t) &=&\sum_{i=1}^{n}\left( \ln E\left[ e^{tX_{i}}\right] -tE\left[
X_{i}\right] \right) \\
&\leq &\sum_{i=1}^{n}E\left[ e^{tX_{i}}\right] -tE\left[ X_{i}\right] -1 \\
&=&\sum_{i=1}^{n}E\left[ e^{tX_{i}}-tX_{i}-1\right] \\
&\leq &\sum_{i=1}^{n}2E\left[ \cosh \left( tX_{i}\right) -1\right] \\
&\leq &\sum_{i=1}^{n}E\left[ tX_{i}\sinh \left( tX_{i}\right) \right] \\
&\leq &\sum_{i=1}^{n}E\left[ \left\vert tX_{i}\sinh \left( tX_{i}\right)
\right\vert \right] \\
&=&\sum_{i=1}^{n}tE\left[ \left\vert X_{i}\right\vert \sinh \left(
t\left\vert X_{i}\right\vert \right) \right] \\
&=&\sum_{i=1}^{n}tE\left[ \sum_{k=0}^{\infty }\frac{t^{2k+1}\left\vert
X_{i}\right\vert ^{2k+2}}{\left( 2k+1\right) !}\right] \\
&=&\sum_{i=1}^{n}t\sum_{k=0}^{\infty }\frac{t^{2k+1}E\left[ \left\vert
X_{i}\right\vert ^{2k+2}\right] }{\left( 2k+1\right) !} \\
&\leq &\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) !} \\
&=&\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) !} \\
&=&\frac{tv^{2}}{M}\sum_{k=0}^{\infty }\frac{\left( tM\right) ^{2k+1}}{%
\left( 2k+1\right) !} \\
&=&\frac{tv^{2}}{M}\sinh \left( tM\right) .
\end{eqnarray*}
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}\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}}%
\arsinh\left( \frac{M\varepsilon }{2v^{2}}\right) \right) \right]
\] |
|
|
|
|
|
