Inégalité de Chernoff

Pour les articles homonymes, voir Chernoff.

Cet article est une ébauche concernant les probabilités et la statistique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

${\displaystyle {\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ù,

${\displaystyle {\begin{aligned}P(X\geq a)&\leq e^{-(ta-\ln(\phi (t)))},\end{aligned}}}$

et, comme c'est vrai pour tout ${\displaystyle t\geq 0}$, on obtient que

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

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

${\displaystyle {\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} ^{\ln(\phi (t))}\\&\leq \mathrm {e} ^{-(-ta-\ln(\phi (t)))},\end{aligned}}}$

donc comme précédemment:

${\displaystyle P(X\leq -a)\leq \mathrm {e} ^{-h(-a)}.}$

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

${\displaystyle {\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 ${\displaystyle h_{{\overline {Z}}_{n}}(\epsilon )=\sup _{t\geq 0}\{\epsilon t-\ln(E[\mathrm {e} ^{t{\overline {Z}}_{n}}])\}=nh_{Z}(\epsilon )}$. En effet, comme ${\displaystyle \{X_{i}\}_{i\in [\!1,n\!]}}$ sont i.i.d et donc ${\displaystyle \{Z_{i}\}_{i\in [\!1,n\!]}}$ sont i.i.d.,

${\displaystyle {\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ù,

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

Donc,

${\displaystyle {\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-\ln(E[\mathrm {e} ^{tZ}])\}}\\&\leq \mathrm {e} ^{n\inf _{t\geq 0}\{\ln(E[\mathrm {e} ^{tZ}])-\epsilon t\}}\\&\leq \mathrm {e} ^{n(\ln(E[\mathrm {e} ^{tZ}])-\epsilon t)}({\text{pour }}t\geq 0).\end{aligned}}}$

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

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

avec ${\displaystyle \forall t\in \mathbb {R} ,~\Psi (t)=-pt+\ln(1-p+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 ${\displaystyle \Psi }$,

${\displaystyle {\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 ${\displaystyle \alpha =1-p,~\beta =p\mathrm {e} ^{t}}$. On peut majorer ${\displaystyle \Psi ^{''}(t)}$ par ${\displaystyle {\frac {1}{4}}}$.
En effet, ${\displaystyle (\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 ${\displaystyle \Psi (0)=\Psi ^{'}(0)=0}$, d'après la formule de Taylor Lagrange, ${\displaystyle \forall t\in \mathbb {R} }$,

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

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

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

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

${\displaystyle {\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\geq p+\epsilon )&\leq \mathrm {e} ^{n({\frac {16\epsilon ^{2}}{8}}-4\epsilon ^{2})}\\&\leq \mathrm {e} ^{-2n\epsilon ^{2}}.\end{aligned}}}$

Pour la deuxième inégalité, ${\displaystyle \forall \epsilon >0}$,

${\displaystyle {\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\leq p-\epsilon )&=P({\overline {Z}}_{n}\leq -\epsilon )\\&=P(-{\overline {Z}}_{n}\geq \epsilon )\\&\leq \mathrm {e} ^{-h_{-{\overline {Z}}_{n}}(t)}{\text{ d'après l'inégalité de Chernoff}}\\&\leq \mathrm {e} ^{-nh_{-Z}(t)}\\&\leq \mathrm {e} ^{n\inf _{t\geq 0}\{\ln(E[\mathrm {e} ^{-tZ}])-\epsilon t\}}\\&\leq \mathrm {e} ^{n(\ln(E[\mathrm {e} ^{-tZ}])-\epsilon t)}({\text{pour }}t\geq 0).\end{aligned}}}$

On remarque que : ${\displaystyle \forall t\geq 0}$,

${\displaystyle {\begin{aligned}E[\mathrm {e} ^{-tZ}]&=\mathrm {e} ^{pt}E[\mathrm {e} ^{-tX}]\\&=\mathrm {e} ^{pt}(1-p+p\mathrm {e} ^{-t})\\\Rightarrow \ln(E[\mathrm {e} ^{-tZ}])&=pt+\ln(1-p+p\mathrm {e} ^{-t})\\&=\Psi (-t)\\&\leq {\frac {t^{2}}{8}}.\end{aligned}}}$

Donc, ${\displaystyle \forall \epsilon >0,~\forall t\geq 0}$,

${\displaystyle {\begin{aligned}P({\frac {1}{n}}\sum _{i=1}^{n}X_{i}\leq p-\epsilon )&\leq \mathrm {e} ^{n({\frac {t^{2}}{8}}-\epsilon t)}\\&\leq \mathrm {e} ^{-2n\epsilon ^{2}},\end{aligned}}}$

par un argument similaire qui a servi à démontrer la première inégalité.