| Version 3 |
Version 2 |
| Starting from the basic inequality $\exp \left( -x\right) \geq 1-x$, it's |
Starting from the basic inequality $\exp \left( -x\right) \geq 1-x$, it's |
| easy to derive by elementary algebraic manipulations the two inequalities |
easy to derive by elementary algebraic manipulations the two inequalities |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| \exp \left( x\right) -x-1 &\leq &2\left( \cosh \left( x\right) -1\right) \\ |
\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) |
2\left( \cosh \left( x\right) -1\right) &\leq &x\sinh \left( x\right) |
| \end{eqnarray*} |
\end{eqnarray*} |
|
|
| By the \PMlinkname{Chernoff-Cram\`{e}r bound}{ChernoffCramerBound}, we have: |
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\} |
\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] |
\leq \exp \left[ -\sup_{t>0}\left( t\varepsilon -\psi (t)\right) \right] |
| \] |
\] |
|
|
| where |
where |
| \[ |
\[ |
| \psi (t)=\sum_{i=1}^{n}\left( \ln E\left[ e^{tX_{i}}\right] -tE\left[ X_{i}% |
\psi (t)=\sum_{i=1}^{n}\left( \ln E\left[ e^{tX_{i}}\right] -tE\left[ X_{i}% |
| \right] \right) |
\right] \right) |
| \] |
\] |
|
|
| Since $\ln x\leq x-1$ $\forall x > 0$, |
Since $\ln x\leq x-1$ $\forall x > 0$, |
| \begin{eqnarray*} |
\begin{eqnarray*} |
| \psi (t) &=&\sum_{i=1}^{n}\left( \ln E\left[ e^{tX_{i}}\right] -tE\left[ |
\psi (t) &=&\sum_{i=1}^{n}\left( \ln E\left[ e^{tX_{i}}\right] -tE\left[ |
| X_{i}\right] \right) \leq \\ |
X_{i}\right] \right) \leq \\ |
| &\leq &\sum_{i=1}^{n}E\left[ e^{tX_{i}}\right] -tE\left[ X_{i}\right] -1= \\ |
&\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}E\left[ e^{tX_{i}}-tX_{i}-1\right] \leq \\ |
| &\leq &\sum_{i=1}^{n}2E\left[ \cosh \left( tX_{i}\right) -1\right] \leq \\ |
&\leq &\sum_{i=1}^{n}2E\left[ \cosh \left( tX_{i}\right) -1\right] \leq \\ |
| &\leq &\sum_{i=1}^{n}E\left[ tX_{i}\sinh \left( tX_{i}\right) \right] \leq \\ |
&\leq &\sum_{i=1}^{n}E\left[ tX_{i}\sinh \left( tX_{i}\right) \right] \leq \\ |
| &\leq &\sum_{i=1}^{n}E\left[ \left\vert tX_{i}\sinh \left( tX_{i}\right) |
&\leq &\sum_{i=1}^{n}E\left[ \left\vert tX_{i}\sinh \left( tX_{i}\right) |
| \right\vert \right] = \\ |
\right\vert \right] = \\ |
| &=&\sum_{i=1}^{n}tE\left[ \left\vert X_{i}\right\vert \sinh \left( |
&=&\sum_{i=1}^{n}tE\left[ \left\vert X_{i}\right\vert \sinh \left( |
| t\left\vert X_{i}\right\vert \right) \right] = \\ |
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 |
&=&\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] = \\ |
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[ |
&=&\sum_{i=1}^{n}t\sum_{k=0}^{\infty }\frac{t^{2k+1}E\left[ |
| X_{i}^{2}\left\vert X_{i}\right\vert ^{2k}\right] }{\left( 2k+1\right) !}\leq |
X_{i}^{2}\left\vert X_{i}\right\vert ^{2k}\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] |
&=&\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) !}= \\ |
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[ |
&=&\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) !}= \\ |
X_{i}^{2}\right] }{\left( 2k+1\right) !}= \\ |
| &=&\frac{tv^{2}}{M}\sum_{k=0}^{\infty }\frac{\left( tM\right) ^{2k+1}}{% |
&=&\frac{tv^{2}}{M}\sum_{k=0}^{\infty }\frac{\left( tM\right) ^{2k+1}}{% |
| \left( 2k+1\right) !}= \\ |
\left( 2k+1\right) !}= \\ |
| &=&\frac{tv^{2}}{M}\sinh \left( tM\right) . |
&=&\frac{tv^{2}}{M}\sinh \left( tM\right) . |
| \end{eqnarray*} |
\end{eqnarray*} |
|
|
| One can now write |
One can now write |
| \[ |
\[ |
| \sup_{t>0}\left( t\varepsilon -\psi (t)\right) \geq \sup_{t>0}\left( |
\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}% |
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[ \frac{v^{2}}{M^{2}}\left( \frac{M^{2}\varepsilon }{v^{2}}t-tM\sinh |
| \left( tM\right) \right) \right] |
\left( tM\right) \right) \right] |
| \] |
\] |
|
|
| Optimizing this expression with respect to $t$ would lead to solving the |
Optimizing this expression with respect to $t$ would lead to solving the |
| trascendental equation: |
trascendental equation: |
| \[ |
\[ |
| \frac{M\varepsilon }{v^{2}}=Mt_{opt}\cosh \left( Mt_{opt}\right) +\sinh |
\frac{M\varepsilon }{v^{2}}=Mt_{opt}\cosh \left( Mt_{opt}\right) +\sinh |
| \left( Mt_{opt}\right) |
\left( Mt_{opt}\right) |
| \] |
\] |
|
|
| which is analytically infeasible. So, one can choose the sup-optimal yet |
which is analytically infeasible. So, one can choose the sup-optimal yet |
| manageable solution |
manageable solution |
| \[ |
\[ |
|
\widetilde{t}=\frac{1}{M}\arcsinh\left( \frac{M\varepsilon }{2v^{2}}\right)
|
\widetilde{t}=\frac{1}{M}\arcsin h\left( \frac{M\varepsilon }{2v^{2}}\right)
|
| \] |
\] |
|
|
| which, once plugged into the bound, yields |
which, once plugged into the bound, yields |
| \[ |
\[ |
| \Pr\left\{ \sum_{i=1}^{n}\left( X_{i}-E[X_{i}]\right) >\varepsilon \right\} |
\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}}% |
\leq \exp \left[ -\frac{v^{2}}{M^{2}}\left( \frac{M\varepsilon }{2v^{2}}% |
|
\arcsinh\left( \frac{M\varepsilon }{2v^{2}}\right) \right) \right]
|
\arcsin h\left( \frac{M\varepsilon }{2v^{2}}\right) \right) \right]
|
| \] |
\] |
