Inégalité de Chernoff

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é.