Q8
Moment generating functions
Concentration inequality via MGF and Markov's inequality (Chernoff method)
View
Let $n \geqslant 1$ be a natural integer, and let $\left( X _ { 1 } , \ldots , X _ { n } \right)$ be mutually independent discrete real random variables such that, for all $k \in \{ 1 , \ldots , n \}$, $$P \left[ X _ { k } = 1 \right] = P \left[ X _ { k } = - 1 \right] = \frac { 1 } { 2 }$$ We define $$S _ { n } = \frac { 1 } { n } \sum _ { k = 1 } ^ { n } X _ { k }$$ as well as, for all $\lambda \in \mathbb { R }$, $$\psi ( \lambda ) = \log \left( \frac { 1 } { 2 } e ^ { \lambda } + \frac { 1 } { 2 } e ^ { - \lambda } \right)$$ For each $\lambda \geqslant 0$, we set $$m ( \lambda ) = \frac { E \left[ X _ { 1 } \exp \left( \lambda X _ { 1 } \right) \right] } { E \left[ \exp \left( \lambda X _ { 1 } \right) \right] }$$ as well as $$D _ { n } ( \lambda ) = \exp \left( \lambda n S _ { n } - n \psi ( \lambda ) \right)$$ For all $n \geqslant 1 , \lambda \geqslant 0$ and $\varepsilon > 0$, we denote by $I _ { n } ( \lambda , \varepsilon )$ the random variable defined by $$I _ { n } ( \lambda , \varepsilon ) = \begin{cases} 1 & \text { if } \left| S _ { n } - m ( \lambda ) \right| \leqslant \varepsilon \\ 0 & \text { otherwise } \end{cases}$$
(a) Deduce, for each $\lambda \geqslant 0$ and $\varepsilon > 0$, the existence of a sequence $\left( u _ { n } ( \varepsilon ) \right) _ { n \geqslant 1 }$ that tends to 0 as $n$ tends to infinity and such that $$\frac { 1 } { n } \log P \left[ S _ { n } \geqslant m ( \lambda ) - \varepsilon \right] \geqslant \psi ( \lambda ) - \lambda m ( \lambda ) - \lambda \varepsilon + u _ { n } ( \varepsilon )$$
(b) Conclude that for all $t \in [ 0,1 [$, $$\lim _ { n \rightarrow \infty } \frac { 1 } { n } \log P \left[ S _ { n } \geqslant t \right] = \inf _ { \lambda \geqslant 0 } ( \psi ( \lambda ) - \lambda t )$$
(c) Is the preceding formula still valid for $t = 1$ ?