Utilisateur:Maxime.brunin/Brouillon4

Cas général

Pour la première inégalité, $\forall a\geq 0,~\forall t\geq 0$ ,

{\begin{aligned}\mathrm {e} ^{t(X-a)}&\geq {1}_{\{X\geq a\}}\\\Rightarrow E\left[\mathrm {e} ^{t(X-a)}\right]&\geq P(X\geq a)\\\Rightarrow E\left[\mathrm {e} ^{tX}\right]\mathrm {e} ^{-ta}&\geq P(X\geq a).\\\end{aligned}}

D'où,

{\begin{aligned}P(X\geq a)&\leq \mathrm {e} ^{\log(\phi (t))-ta}\\&\leq \mathrm {e} ^{-(ta-\log(\phi (t)))}\\&\leq \mathrm {e} ^{-\sup _{t\geq 0}\{ta-\log(\phi (t))\}}\\&\leq \mathrm {e} ^{-h(a)}.\end{aligned}}

Pour la deuxième inégalité inégalité, $\forall a\geq 0,~\forall t\leq 0$ ,

{\begin{aligned}\mathrm {e} ^{t(X+a)}\geq {1}_{\{X\leq -a\}}\\\Rightarrow P(X\leq -a)&\leq E\left[\mathrm {e} ^{t(X+a)}\right]\\&\leq \mathrm {e} ^{ta}\mathrm {e} ^{\log(\phi (t))}\\&\leq \mathrm {e} ^{-(-ta-\log(\phi (t)))}\\&\leq \mathrm {e} ^{-h(-a)}.\end{aligned}}

Avec des variables symétriques booléennes

Démonstration

Pour la première inégalité, on pose $Z=X-p$ et ${\overline {Z}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}Z_{i}$ où X suit une loi de Bernouilli de paramètre p. Par l'inégalité de Chernoff appliquée à ${\overline {Z}}_{n}$ ,

{\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geq p+\epsilon )&=P({\overline {Z}}_{n}\geq \epsilon )\\&\leq \mathrm {e} ^{-h_{{\overline {Z}}_{n}}(\epsilon )}.\end{aligned}}

Or $h_{{\overline {Z}}_{n}}(\epsilon )=\sup _{t\geq 0}\{\epsilon t-\log(E[\mathrm {e} ^{t{\overline {Z}}_{n}}])\}=nh_{Z}(\epsilon )$ . En effet, comme $\{X_{i}\}_{i\in [\!1,n\!]}$ sont i.i.d et donc $\{Z_{i}\}_{i\in [\!1,n\!]}$ sont i.i.d.,

{\begin{aligned}E[\mathrm {e} ^{t{\overline {Z}}_{n}}]&=\prod _{i=1}^{n}E[\mathrm {e} ^{{\frac {t}{n}}Z_{i}}]\\&=E[\mathrm {e} ^{{\frac {t}{n}}Z}]^{n}.\end{aligned}}

D'où,

{\begin{aligned}h_{{\overline {Z}}_{n}}(\epsilon )&=\sup _{t\geq 0}\{\epsilon t-\log(E[\mathrm {e} ^{t{\overline {Z}}_{n}}])\}\\&=\sup _{t\geq 0}\{\epsilon t-n\log(E[\mathrm {e} ^{{\frac {t}{n}}Z}])\}\\&=n\sup _{t\geq 0}\{\epsilon {\frac {t}{n}}-\log(E[\mathrm {e} ^{{\frac {t}{n}}Z}])\}\\&=nh_{Z}(\epsilon ).\end{aligned}}

Donc,

{\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geq p+\epsilon )&\leq \mathrm {e} ^{-n\sup _{t\geq 0}\{\epsilon t-\log(E[\mathrm {e} ^{tZ}])\}}\\&\leq \mathrm {e} ^{n\inf _{t\geq 0}\{\log(E[\mathrm {e} ^{tZ}])-\epsilon t\}}\\&\leq \mathrm {e} ^{n(\log(E[\mathrm {e} ^{tZ}])-\epsilon t)}({\text{pour }}t\geq 0).\end{aligned}}

On remarque que $E[\mathrm {e} ^{tZ}]=\mathrm {e} ^{-pt}E[\mathrm {e} ^{tX}]=\mathrm {e} ^{-pt}(1-p+\mathrm {e} ^{t})$ .
Donc $\forall t\geq 0,$

{\begin{aligned}\log(E[\mathrm {e} ^{tZ}])-\epsilon t&=\log(1-p+\mathrm {e} ^{t})-(\epsilon +p)t\\&=\Psi (t)-\epsilon t,\end{aligned}}

avec $\forall t\in \mathbb {R} ,~\Psi (t)=-pt+\log(1-p+\mathrm {e} ^{t})$ .
En vue d'utiliser la formule de Taylor Lagrange à l'ordre 2, on calcule les dérivées premières et secondes $\Psi$ ,

{\begin{aligned}\forall t\in \mathbb {R} ,~\Psi ^{'}(t)&=-p+{\frac {p\mathrm {e} ^{t}}{1-p+p\mathrm {e} ^{t}}}\\\Psi ^{''}(t)&={\frac {(1-p)p\mathrm {e} ^{t}}{(1-p+p\mathrm {e} ^{t})^{2}}}\\&={\frac {\alpha \beta }{(\alpha +\beta )^{2}}}\\&\leq {\frac {1}{4}},\end{aligned}}

avec $\alpha =1-p,~\beta =p\mathrm {e} ^{t}$ . On peut majorer $\Psi ^{''}(t)$ par ${\frac {1}{4}}$ .
En effet, $(\alpha +\beta )^{2}=\alpha ^{2}+\beta ^{2}+2\alpha \beta {\text{ et }}(\alpha -\beta )^{2}=\alpha ^{2}+\beta ^{2}-2\alpha \beta \geq 0\Rightarrow 2\alpha \beta \leq \alpha ^{2}+\beta ^{2}\Rightarrow (\alpha +\beta )^{2}\geq 4\alpha \beta$ .

Donc, comme $\Psi (0)=\Psi ^{'}(0)=0$ , d'après la formule de Taylor Lagrange, $\forall t\in \mathbb {R}$ ,

{\begin{aligned}\Psi (t)&=\Psi (0)+t\Psi ^{'}(0)+{\frac {t^{2}}{2}}\Psi ^{''}(\theta t)\\&\leq {\frac {t^{2}}{8}},\end{aligned}}

avec $\theta \in [0,1]$ .
Donc, $\forall t\geq 0$ ,

{\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geq p+\epsilon )&\leq \mathrm {e} ^{n(\log(E[\mathrm {e} ^{tZ}])-\epsilon t)}\\&\leq \mathrm {e} ^{n({\frac {t^{2}}{8}}-\epsilon t)}.\end{aligned}}

Soit $\forall t\geq 0,~g(t)={\frac {t^{2}}{8}}-\epsilon t$ . On remarque $\forall t\geq 0,~g^{'}(t)={\frac {t}{4}}-\epsilon$ .
Donc g admet un minimum en $t=4\epsilon$ .
Ainsi, $\forall \epsilon >0$ ,