PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of Prohorov inequality (Proof)

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 Chernoff-Cramèr bound, 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\vert X_{i}\right\vert \leq M\right\} =1\text{ \ }\forall i $$ implies that, for all $i$ , $$ E[\left\vert X_{i}\right\vert ^{k}]\leq M^{k} \text{ \ }\forall k\geq 0 $$ (see here for a proof) and since $\ln x\leq x-1$ $\forall x>0$ , and(see here 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] $$




"proof of Prohorov inequality" is owned by Andrea Ambrosio.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: bound, solution, equation, transcendental, expression, proof, implies, algebraic, inequality

This is version 11 of proof of Prohorov inequality, born on 2006-09-04, modified 2006-09-16.
Object id is 8313, canonical name is ProofOfProhorovInequality.
Accessed 835 times total.

Classification:
AMS MSC60E15 (Probability theory and stochastic processes :: Distribution theory :: Inequalities; stochastic orderings)

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)