La méthode de Chernoff sur la marche aléatoire

La stratégie. L'inégalité de Markov ne demande qu'une variable positive et son espérance. Au lieu de l'appliquer à $S_n^2$, ce qui redonne Tchebychev, on l'applique à $e^{\lambda S_n}$ : l'exponentielle transforme la somme en produit, l'indépendance transforme l'espérance du produit en produit des espérances, et l'on garde un paramètre $\lambda$ libre que l'on optimise à la fin. C'est la méthode de Chernoff.

1) La transformée d'un pas, et son inégalité. Par la formule de transfert, $X_1$ prenant les valeurs $1$ et $-1$ avec probabilité $\frac{1}{2}$ : $$E\left(e^{\lambda X_1}\right)=\frac{1}{2}{e}^{\lambda }+\frac{1}{2}{e}^{-\lambda }=\mathrm{ch}\lambda ,$$ le cosinus hyperbolique de $\lambda$.

L'inégalité $\mathrm{ch}\lambda \le e^{{\lambda }^2/2}$. Comme $\mathrm{ch}\lambda >0$, elle équivaut, par croissance du logarithme, à $\ln \mathrm{ch}\lambda \le \frac{{\lambda }^2}{2}$, c'est-à-dire à $g(\lambda )\ge 0$ où $g(\lambda )=\frac{{\lambda }^2}{2}-\ln \mathrm{ch}\lambda$. La fonction $g$ est dérivable sur $\mathbb{R}$, paire (car $\mathrm{ch}$ est paire), et $g(0)=0-\ln 1=0$. Sa dérivée est $$g^{\prime }(\lambda )=\lambda -\frac{\mathrm{sh}\lambda }{\mathrm{ch}\lambda }=\lambda -\mathrm{th}\lambda .$$ Il reste à montrer que $\mathrm{th}\lambda \le \lambda$ pour $\lambda \ge 0$. Posons $h(\lambda )=\lambda -\mathrm{th}\lambda$ : $h(0)=0$ et $h^{\prime }(\lambda )=1-(1-{\mathrm{th}}^2\lambda )={\mathrm{th}}^2\lambda \ge 0$ (la dérivée de la tangente hyperbolique est $1-{\mathrm{th}}^2$, vue au chapitre des fonctions usuelles). Donc $h$ est croissante sur ${\mathbb{R}}_{+}$ et $h\ge h(0)=0$ : $\mathrm{th}\lambda \le \lambda$ pour $\lambda \ge 0$. Ainsi $g^{\prime }\ge 0$ sur ${\mathbb{R}}_{+}$, $g$ y est croissante, et $g(\lambda )\ge g(0)=0$ pour $\lambda \ge 0$. Par parité, $g\ge 0$ sur $\mathbb{R}$ tout entier : $$\mathrm{ch}\lambda \le e^{{\lambda }^2/2}\text{pour tout }\lambda \in \mathbb{R}.$$ Contrôle. En $\lambda =1$ : $\mathrm{ch}1\approx 1,5431$ et $e^{1/2}\approx 1,6487$. En $\lambda =2$ : $\mathrm{ch}2\approx 3,7622$ et $e^2\approx 7,389$. L'inégalité est serrée près de $0$ — les deux fonctions valent $1+\frac{{\lambda }^2}{2}+o({\lambda }^2)$ — et large ensuite.

2) De la somme au produit. $e^{\lambda S_n}=e^{\lambda X_1}{e}^{\lambda X_2}\cdots e^{\lambda X_n}$. Les variables $e^{\lambda X_i}$ sont des fonctions des $X_i$, qui sont indépendantes ; par le lemme des coalitions (fonctions de paquets disjoints), elles sont indépendantes. Le cours donne alors, pour $n$ variables indépendantes, $E(Z_1\cdots Z_n)=E(Z_1)\cdots E(Z_n)$. Donc $$E\left(e^{\lambda S_n}\right)=\prod _{i=1}^{n}E\left(e^{\lambda X_i}\right)=(\mathrm{ch}\lambda {)}^n\le (e^{{\lambda }^2/2}{)}^n=e^{n{\lambda }^2/2},$$ la dernière inégalité par croissance de $t\mapsto t^n$ sur ${\mathbb{R}}_{+}$ et le 1).

3) Markov sur l'exponentielle, puis l'optimisation. Soit $\lambda >0$. L'exponentielle est strictement croissante, donc les événements $(S_n\ge a)$ et $(e^{\lambda S_n}\ge e^{\lambda a})$ sont égaux. La variable $e^{\lambda S_n}$ est strictement positive ; l'inégalité de Markov, avec le seuil $e^{\lambda a}>0$, donne $$P(S_n\ge a)=P(e^{\lambda S_n}\ge e^{\lambda a})\le \frac{E\left(e^{\lambda S_n}\right)}{e^{\lambda a}}\le e^{-\lambda a+n{\lambda }^2/2}.$$ Cette majoration vaut pour tout $\lambda >0$ : on choisit le meilleur. L'exposant $\psi (\lambda )=-\lambda a+\frac{n{\lambda }^2}{2}$ est un trinôme en $\lambda$, de dérivée $-a+n\lambda$, minimal en $\lambda =\frac{a}{n}>0$, où il vaut $$\psi \left(\frac{a}{n}\right)=-\frac{a^2}{n}+\frac{n}{2}\cdot \frac{a^2}{n^2}=-\frac{a^2}{2n}.$$ Donc $$P(S_n\ge a)\le e^{-a^2/(2n)}.$$

Les deux côtés. Le $n$-uplet $(-X_1,\dots ,-X_n)$ a la même loi que $(X_1,\dots ,X_n)$ : mêmes lois marginales (uniforme sur $\{-1,1\}$, invariante par changement de signe) et indépendance. Donc $-S_n$ a la même loi que $S_n$, et $P(S_n\le -a)=P(-S_n\ge a)=P(S_n\ge a)$. L'événement $(|S_n|\ge a)$ est la réunion des deux, donc $$P(|S_n|\ge a)\le 2e^{-a^2/(2n)}.$$

4) La comparaison. Prenons $a=10\sqrt{n}$. Bienaymé-Tchebychev, avec $E(S_n)=0$ et $V(S_n)=n$ (additivité de la variance pour des variables indépendantes de variance $1$), donne $$P(|S_n|\ge 10\sqrt{n})\le \frac{n}{100n}=\frac{1}{100}.$$ Chernoff donne $$P(|S_n|\ge 10\sqrt{n})\le 2e^{-100n/(2n)}=2e^{-50}\approx 3,9\times 10^{-22}.$$ (Calcul : $50/\ln 10\approx 21,71$, donc $e^{-50}\approx 10^{-21,71}\approx 1,9\times 10^{-22}$.) Un centième d'un côté, quatre dix-milliardièmes de milliardième de l'autre : la borne exponentielle est meilleure d'un facteur de l'ordre de $10^{19}$.

Pourquoi. Tchebychev n'utilise de la loi de $S_n$ que son moment d'ordre deux, et la borne $\frac{V}{{\epsilon }^2}$ décroît comme l'inverse d'un carré. La méthode de Chernoff utilise tous les moments à la fois — l'exponentielle $e^{\lambda S_n}$ les contient tous — et l'indépendance en fait un produit, d'où une décroissance en $e^{-a^2/(2n)}$ : les grands écarts d'une somme de variables indépendantes bornées sont exponentiellement rares, la vraie loi de $S_n$ a des queues gaussiennes. (Pour $a>n$, $P(S_n\ge a)=0$ et la borne est inutile ; elle ne dit rien non plus quand elle dépasse $1$, c'est-à-dire pour $a$ petit devant $\sqrt{2n\ln 2}$.)

Le point délicat. Deux endroits. Le choix de $\lambda$ : la majoration est vraie pour tout $\lambda >0$, et c'est après l'avoir écrite qu'on optimise — un paramètre libre laissé jusqu'à la fin, puis ajusté. Et l'égalité d'événements $(S_n\ge a)=(e^{\lambda S_n}\ge e^{\lambda a})$, qui demande $\lambda >0$ : avec $\lambda <0$, l'exponentielle renverserait l'inégalité.

Ce que l'exercice installe. L'inégalité de Markov est bien plus qu'une inégalité grossière : appliquée à la bonne fonction de la variable — ici l'exponentielle, ailleurs une puissance — et combinée à l'indépendance, elle donne les inégalités de concentration modernes (Chernoff, Hoeffding), qui sont l'outil des grandes déviations en seconde année et de toute l'informatique probabiliste. Le geste à retenir : transformer en produit, factoriser par indépendance, optimiser le paramètre.