L'inégalité de Chernoff

a) Markov, appliquée au bon objet. La stratégie : l'inégalité de Markov est grossière appliquée à $X$ ; on l'applique à une fonction croissante, et rapidement croissante, de $X$, puis on choisit la meilleure.

Soit $t\in [1,R[$. Comme $t<R$, la série $\sum P(X=n)t^n$ converge : par la formule de transfert, $t^X$ est d'espérance finie et $E(t^X)=G_X(t)$. Comme $t\ge 1$, $u\mapsto t^u$ est croissante, donc $(X\ge a)\subset (t^X\ge t^a)$. Par croissance de la probabilité, puis par l'inégalité de Markov appliquée à la variable positive $t^X$ et au seuil $t^a>0$, $$P(X\ge a)\le P(t^X\ge t^a)\le \frac{E(t^X)}{t^a}=\frac{G_X(t)}{t^a}.$$ Chaque $t$ de $[1,R[$ fournit une majoration : on garde la meilleure, $P(X\ge a)\le {\inf }_t{G}_X(t)t^{-a}$.

b) La queue de la loi de Poisson. Ici $G_X(t)=e^{\lambda (t-1)}$, de rayon infini. On minimise $h(t)=e^{\lambda (t-1)}{t}^{-a}$ sur $[1,+\infty [$ par son logarithme : $\ln h(t)=\lambda (t-1)-a\ln t$ a pour dérivée $\lambda -\frac{a}{t}$, négative sur $[1,\frac{a}{\lambda }]$ et positive ensuite. Le minimum est atteint en $t^{\ast }=\frac{a}{\lambda }$, qui est bien supérieur à $1$ puisque $a>\lambda$, et il vaut $$h(t^{\ast })=e^{a-\lambda }(\frac{\lambda }{a}{)}^a=e^{-\lambda }(\frac{e\lambda }{a}{)}^a.$$

Les chiffres, pour $\lambda =4$ et $a=12$, où $t^{\ast }=3$. Markov donne $\frac{E(X)}{12}\approx 0,333$ ; Bienaymé-Tchebychev, $P(|X-4|\ge 8)\le \frac{V(X)}{64}=0,0625$ ; Chernoff, $e^{-4}(\frac{e}{3}{)}^{12}\approx 0,0056$ ; la valeur exacte est $0,00092$. Markov se trompe d'un facteur $360$ environ, Bienaymé-Tchebychev d'un facteur $68$, Chernoff d'un facteur $6$ seulement.

c) La queue de la loi binomiale. Ici $G_{S_n}(t)=(\frac{1+t}{2}{)}^n$, de rayon infini. Le a), appliqué au seuil réel $na$, donne pour tout $t\ge 1$ $$P(S_n\ge na)\le (\frac{1+t}{2}{)}^n{t}^{-na}=e^{n\phi (t)},$$ avec $\phi (t)=\ln (1+t)-\ln 2-a\ln t$. Sa dérivée, ${\phi }^{\prime }(t)=\frac{1}{1+t}-\frac{a}{t}=\frac{(1-a)t-a}{t(1+t)}$, est négative sur $[1,t^{\ast }]$ et positive ensuite, avec $t^{\ast }=\frac{a}{1-a}$, qui est strictement supérieur à $1$ puisque $a>\frac{1}{2}$. Au minimum, $1+t^{\ast }=\frac{1}{1-a}$, et $$\phi (t^{\ast })=-\ln (1-a)-\ln 2-a\ln a+a\ln (1-a)=-[a\ln a+(1-a)\ln (1-a)+\ln 2].$$ En écrivant $\ln 2=a\ln 2+(1-a)\ln 2$, le crochet vaut $a\ln (2a)+(1-a)\ln (2(1-a))=I(a)$. D'où $P(S_n\ge na)\le e^{-nI(a)}$.

Le taux est strictement positif. $I$ est dérivable sur $]0,1[$, et $I^{\prime }(a)=\ln (2a)+1-\ln (2(1-a))-1=\ln \frac{a}{1-a}$, strictement positif pour $a>\frac{1}{2}$. Donc $I$ est strictement croissante sur $[\frac{1}{2},1[$, et $I(a)>I\left(\frac{1}{2}\right)=0$. La queue décroît exponentiellement en $n$.

Les chiffres, pour $n=1000$ et $a=0,6$. $I(0,6)=0,6\ln 1,2+0,4\ln 0,8\approx 0,02014$, donc $P(S_{1000}\ge 600)\le e^{-20,14}\approx 1,8\times 10^{-9}$. Bienaymé-Tchebychev, avec $E(S_n)=500$ et $V(S_n)=250$, ne donne que $P(|S_n-500|\ge 100)\le \frac{250}{100^2}=0,025$. La valeur exacte, calculée en fractions exactes, est environ $1,4\times 10^{-10}$ : Chernoff la majore à un facteur $13$ près, Bienaymé-Tchebychev à un facteur $10^8$ près — il ne donne jamais qu'une décroissance en $\frac{1}{n}$, ici $\frac{1}{4n(a-\frac{1}{2}{)}^2}$.

d) Le taux est un déficit d'entropie. L'identité a été obtenue au c) : $I(a)=a\ln a+(1-a)\ln (1-a)+\ln 2=\ln 2-H(a)$.

La limite. Posons $k=\lfloor na\rfloor$ ; l'encadrement $na-1<k\le na$ donne $\frac{k}{n}\to a$, et $k$ comme $n-k$ tendent vers $+\infty$ puisque $0<a<1$. La formule de Stirling, $m!\sim \sqrt{2\pi m}(\frac{m}{e}{)}^m$, donne en passant au logarithme $$\ln m!=m\ln m-m+\frac{1}{2}\ln (2\pi m)+{\epsilon }_m,$$ où ${\epsilon }_m$ tend vers $0$. Appliquons-la à $n$, à $k$ et à $n-k$ dans $\ln \left(\genfrac{}{}{0ex}{}{n}{k}\right)$, où $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ se lit « k parmi n » : les termes $-n+k+(n-k)$ se compensent, et les termes en $\frac{1}{2}\ln (2\pi m)$ et en ${\epsilon }_m$ sont des $O(\ln n)$. En écrivant $n\ln n=k\ln n+(n-k)\ln n$, $$\ln \left(\genfrac{}{}{0ex}{}{n}{k}\right)=-k\ln \frac{k}{n}-(n-k)\ln \frac{n-k}{n}+O(\ln n).$$ En divisant par $n$, et par continuité de $u\mapsto u\ln u$ sur $]0,1[$, $$\frac{1}{n}\ln \left(\genfrac{}{}{0ex}{}{n}{k}\right)=-\frac{k}{n}\ln \frac{k}{n}-(1-\frac{k}{n})\ln (1-\frac{k}{n})+O\left(\frac{\ln n}{n}\right)\underset{n\to +\infty }{\to }H(a).$$ Numériquement, pour $a=0,6$ : $0,6479$ pour $n=100$, $0,6694$ pour $n=1000$, $0,6725$ pour $n=10^4$, contre $H(0,6)\approx 0,6730$.

L'interprétation. $P(S_n=k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{-n}$ : parmi les $2^n=e^{n\ln 2}$ configurations équiprobables de $n$ pièces, environ $e^{nH(a)}$ comptent une proportion $a$ de piles, et leur part est de l'ordre de $e^{-nI(a)}$. La borne de Chernoff a donc le bon taux : $P(S_n=\lceil na\rceil )\le P(S_n\ge na)\le e^{-nI(a)}$, et le même calcul, mené avec $\lceil na\rceil$, montre que $\frac{1}{n}\ln P(S_n=\lceil na\rceil )$ tend vers $H(a)-\ln 2=-I(a)$ ; par encadrement, $\frac{1}{n}\ln P(S_n\ge na)\to -I(a)$ (valeurs $-0,036$, $-0,023$, $-0,021$ pour $n=100$, $1000$, $10^4$, contre $-0,0201$). $H(a)$ est l'entropie de mélange par particule, en unités de $k_B$ : la formule de Boltzmann $S=k_B\ln \Omega$ compte les configurations. Pour $N$ molécules d'un gaz réparties au hasard entre les deux moitiés d'un récipient, la probabilité d'en trouver au moins 60 pour cent à gauche est inférieure à $e^{-0,02N}$ : moins de $2\times 10^{-9}$ pour $N=1000$, un nombre dépourvu de sens physique pour une mole. Une fluctuation macroscopique est exponentiellement rare parce que peu de configurations la réalisent : c'est la raison probabiliste du caractère déterministe de la thermodynamique.

Ce que l'exercice installe. L'inégalité de Markov est grossière appliquée à $X$, redoutable appliquée à $t^X$ et optimisée en $t$ : c'est l'inégalité de Chernoff, qui remplace la décroissance en $\frac{1}{n}$ de Bienaymé-Tchebychev par une décroissance exponentielle, avec le bon taux — un déficit d'entropie, version probabiliste de la formule de Boltzmann. Aucun théorème hors programme n'a servi : Markov, la fonction génératrice et Stirling ont suffi.