Inégalité de Bernstein (probabilités)

L'inégalité de Bernstein est une inégalité de concentration démontrée par en 1926 par le mathématicien russe Sergueï Bernstein^[1]. Cette inégalité se base sur un majoration de la fonction génératrice des moments d'une variable aléatoire, d'une manière similaire aux inégalités de Hoeffding ou de Chernoff. Cette majoration se fait grâce à une hypothèse sur les moments de la variable aléatoire en question.

Énoncé Général

L'énoncé le plus général de l'inégalité de Bernstein est donné ci-dessous^[2]. Cet énoncé peut se simplifier dans certains cas particuliers.

Théorème — Soient ${\displaystyle X_{1},\cdots ,X_{n}}$, ${\displaystyle n}$ variables aléatoires indépendantes, de moyennes nulles et de variances respectives ${\displaystyle v_{1},\cdots ,v_{n}}$. S'il existe ${\displaystyle c\in \mathbb {R^{+}} }$ tel que pour tout ${\displaystyle i\in \{1,\cdots ,n\}}$, pour tout entier ${\displaystyle k\geq 3}$, ${\displaystyle E[\mid X_{i}\mid ^{k}]\leq {\frac {v_{i}}{2}}k!c^{k-2}}$, alors ${\displaystyle P(X_{1}+\cdots +X_{n}\geq \varepsilon )\leq 2e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2c\varepsilon }}}}$ où ${\displaystyle V_{n}=v_{1}+\cdots +v_{n}}$ .

Démonstration

La démonstration de cette inégalité se fait en 3 étapes.

  - 1) Montrer que ${\displaystyle E\left[e^{t(X_{1}+\cdots +X_{n})}\right]\leq e^{\frac {V_{n}t^{2}}{2(1-u)}}}$ pour tout réels ${\displaystyle t}$ et ${\displaystyle u}$ tels que ${\displaystyle 0<ct\leq u<1}$.
  - 2) Montrer,  grâce à l'inégalité de Markov, que ${\displaystyle P\left(X_{1}+\cdots +X_{n}>{\frac {V_{n}t}{2(1-u)}}+{\frac {s^{2}}{t}}\right)\leq e^{-s^{2}}}$ pour tout réel ${\displaystyle s}$.
  - 3) Choisir des valeurs de ${\displaystyle t}$, ${\displaystyle u}$ et ${\displaystyle s}$ appropriées pour obtenir le résultat final. 

1) Pour montrer le premier point, commençons par écrire que puisque les ${\displaystyle X_{1},...,X_{n}}$ sont indépendants,

${\displaystyle {\begin{aligned}[lll]E\left[e^{t(X_{1}+\cdots +X_{n})}\right]&=E\left[e^{tX_{1}}\cdots e^{tX_{n}}\right]\\&=E\left[e^{tX_{1}}\right]\cdots E\left[e^{tX_{1}}\right]\end{aligned}}}$ .

Le développement en série entière de l'exponentielle donne que, pour chaque ${\displaystyle i}$,

${\displaystyle e^{tX_{i}}=1+tX_{i}+\sum _{k=2}^{+\infty }{\frac {(tX_{i})^{k}}{k!}}}$.

Donc, en utilisant la linéarité de l'espérance :

${\displaystyle {\begin{aligned}E\left[e^{tX_{i}}\right]&=1+tE[X_{i}]+\sum _{k=2}^{+\infty }{\frac {E\left[(tX_{i})^{k}\right]}{k!}}\\&=1+0+\sum _{k=2}^{+\infty }{\frac {t^{k}E(X_{i}^{k})}{k!}}\end{aligned}}}$

puisque ${\displaystyle E[X_{i}]=0}$. Comme ${\displaystyle E[X_{i}^{k}]\leq E[\left|X_{i}\right|^{k}]}$, en utilisant l'hypothèse sur les moments des ${\displaystyle X_{i}}$, on obtient:

${\displaystyle {\begin{aligned}E[e^{tX_{i}}]&\leq 1+\sum _{k=2}^{+\infty }{\frac {t^{k}v_{i}c^{k-2}}{2}}\\&=1+0+{\frac {v_{i}}{2c^{2}}}\sum _{k=2}^{+\infty }(tc)^{k}\\&=1+{\frac {v_{i}}{2c^{2}}}{\frac {(tc)^{2}}{1-tc}}\\&=1+{\frac {v_{i}}{2}}{\frac {t^{2}}{1-tc}}\\\end{aligned}}}$

puisque ${\displaystyle \sum _{k=2}^{+\infty }(tc)^{k}}$ est une série géométrique de raison entre 0 et 1 (par hypothèse sur ${\displaystyle t}$). En prenant ${\displaystyle u>tc}$, on obtient que ${\displaystyle E[e^{tX_{i}}]\leq 1+{\frac {(tc)^{2}}{1-u}}}$ et enfin, en utilisant que ${\displaystyle 1+z\leq e^{z}}$, on obtient que

${\displaystyle E[e^{tX_{i}}]\leq e^{\frac {v_{i}t^{2}}{2(1-u)}}}$

Et donc,

${\displaystyle E[e^{t(X_{1}+\cdots +X_{n}}]\leq e^{\frac {v_{1}t^{2}}{2(1-u)}}\cdots e^{\frac {v_{n}t^{2}}{2(1-u)}}\leq e^{\frac {V_{n}t^{2}}{2(1-u)}}}$ .

2) Le second point se démontre grâce à l'inégalité de Markov. Soit ${\displaystyle s\in \mathbb {R} }$. Remarquons d'abord que

${\displaystyle P\left(X_{1}+...+X_{n}>{\frac {V_{n}t}{2(1-u)}}+{\frac {s^{2}}{t}}\right)=P\left(e^{t(X_{1}+...+X_{n})}>e^{\frac {V_{n}t}{2(1-u)}}e^{\frac {s^{2}}{t}}\right)}$.

L'inégalité de Markov donne alors

${\displaystyle P\left(e^{t(X_{1}+...+X_{n})}>e^{\frac {V_{n}t}{2(1-u)}}e^{\frac {s^{2}}{t}}\right)\leq E\left[e^{t(X_{1}+...+X_{n})}\right]e^{-{\frac {V_{n}t}{2(1-u)}}}e^{-{\frac {s^{2}}{t}}}}$.

Comme d'après le point 1), ${\displaystyle E\left[e^{t(X_{1}+...+X_{n})}\right]\leq e^{\frac {V_{n}t^{2}}{2(1-u)}}}$, on obtient, après simplification,

${\displaystyle P\left(X_{1}+\cdots +X_{n}>{\frac {V_{n}t}{2(1-u)}}+{\frac {s^{2}}{t}}\right)\leq e^{-s^{2}}}$.

3) Soit ${\displaystyle \varepsilon >0}$. Prenons ${\displaystyle t={\frac {\varepsilon }{V_{n}}}(1-u)}$, ${\displaystyle s={\frac {\varepsilon {\sqrt {1-u}}}{\sqrt {2V_{n}}}}}$ et ${\displaystyle u={\frac {c\varepsilon }{V_{n}+\varepsilon }}}$ (on peut vérifier qu'on a alors bien ${\displaystyle ct\leq u\leq 1}$). L'inégalité obtenue au point 2) se réécrit alors

${\displaystyle P\left(X_{1}+\cdots +X_{n}>\varepsilon \right)\leq e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2c\varepsilon }}}}$.

Comme le raisonnement précédent s'applique identiquement aux variables aléatoires ${\displaystyle -X_{1},\cdots ,-X_{n}}$, on a aussi

${\displaystyle P\left(-X_{1}-\cdots -X_{n}>\varepsilon \right)\leq e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2c\varepsilon }}}}$.

D'où:

${\displaystyle P\left(X_{1}+\cdots +X_{n}<-\varepsilon \right)\leq e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2c\varepsilon }}}}$.

On peut donc conclure:

${\displaystyle P\left(\left|X_{1}+\cdots +X_{n}\right|>\varepsilon \right)\leq 2e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2c\varepsilon }}}}$.

Cas de variables aléatoires bornées

Si les variables ${\displaystyle X_{i}}$ sont bornées alors, elles satisfont la condition des moments de l'inégalité de Bernstein.

Théorème — Soient ${\displaystyle X_{1},\cdots ,X_{n}}$, ${\displaystyle n}$ variables aléatoires indépendantes, de moyennes nulles, de variances respectives ${\displaystyle v_{1},\cdots ,v_{n}}$ et telles qu'il existe ${\displaystyle M\in \mathbb {R^{+}} }$ tel que pour tout ${\displaystyle i\in \{1,\cdots ,n\}}$, ${\displaystyle \left|X_{i}\right|\leq M}$ avec probabilité 1. Alors, ${\displaystyle P\left(X_{1}+\cdots +X_{n}\geq \varepsilon \right)\leq 2e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2M\varepsilon /3}}}}$. où ${\displaystyle V_{n}=v_{1}+\cdots +v_{n}}$ .

Démonstration

Comme les ${\displaystyle X_{i}}$ sont bornés, il est facile de montrer que pour tout entier ${\displaystyle k\geq 3}$,${\displaystyle E[\left|X_{i}\right|^{k}]\leq v_{i}M^{k-2}\leq {\frac {v_{i}}{2}}k!(M/3)^{k-2}}$. L'inégalité de Bernstein peut donc être utilisée avec ${\displaystyle c={\frac {M}{3}}}$.

Exemple: variables binaires

Soient ${\displaystyle X_{1},\cdots ,X_{n}}$ des variables aléatoires indépendantes suivant une loi de Bernouilli avec probabilité de succès ${\displaystyle p}$. Alors, comme ces variables aléatoires sont bornées en valeur absolue par ${\displaystyle 1}$, on a

${\displaystyle P(\left|X_{1}+\cdots +X_{n}\right|>\varepsilon )\leq 2e^{-{\frac {\varepsilon ^{2}}{2V_{n}+2\varepsilon /3}}}}$ où dans ce cas, ${\displaystyle V_{n}=np(1-p)}$, puisque les ${\displaystyle X_{i}}$ ont tous la même variance.

Si l'on préfère obtenir l'inégalité de concentration pour la moyenne empirique des ${\displaystyle X_{i}}$, il suffit de remarquer que ${\displaystyle P\left(\left|{\frac {1}{n}}(X_{1}+\cdots +X_{n})\right|>\varepsilon \right)=P\left(\left|X_{1}+\cdots +X_{n}\right|>n\varepsilon \right)}$. On peut donc simplement remplacer ${\displaystyle \varepsilon }$ par ${\displaystyle n\varepsilon }$ dans l'expression précédente. On obtient, après simplification:

${\displaystyle P\left(\left|{\frac {1}{n}}(X_{1}+\cdots +X_{n})\right|>\varepsilon \right)\leq 2e^{-{\frac {n\varepsilon ^{2}}{2p(1-p)+2\varepsilon /3}}}}$.

Voir aussi

• Inégalité d'Azuma
• Inégalité de Bienaymé-Tchebychev
• Inégalité de Chernoff
• Inégalité de Hoeffding
• Inégalité de Markov

Notes et références

1. Ian Cook, A dictionary of statistics, Oxford University Press, 2008 (ISBN 978-0-19-954145-4, 0-19-954145-0 et 978-0-19-172686-6, OCLC 191929569, lire en ligne)
2. Uspensky, J. V. (James Victor), 1883-1947., Introduction to mathematical probability, McGraw-Hill Book Company, Inc, 1937 (OCLC 996937, lire en ligne)

• Portail des probabilités et de la statistique