L'entropie en probabilités

En physique, l'entropie d'un système hamiltonien à l'énergie E est définie comme le log du volume de l'espace des phases qui est à l'énergie E :

On veut définir un analogue en théorie des probabilités. L'idée est que, comme en physique statistique, on va regarder une variable $X_N$

dépendant d'un grand nombre N d'événements élémentaires. La constante de Boltzmann ci-dessus, k, est égale à la constante des gaz parfaits divisée par le nombre de particules impliquées (le nombre d'Avogadro), on est donc tenté de remplacer cette constante par $1/N$

. Le volume s'interprète tout naturellement en terme de probabilité, et on pose :

L'idée est qu'on arrive souvent à évaluer l'entropie d'un événement au moyen de la théorie de l'information. Cela fournit alors directement une évaluation de la probabilité d'un événement : presque par définition, un événement apportant une quantité d'information H a une probabilité $\exp -NH$ .

On commence par donner l'exemple le plus simple d'une telle situation, avant d'expliquer en termes d'entropie les théorèmes plus généraux.

Le théorème de Sanov discret

On considère un alphabet fini à n lettres $\Sigma=\{a_1,\ldots,a_n\}$ . On se donne une loi de probabilité $\mu$ sur cet alphabet et on tire, de manière indépendante, une suite de lettres $X_1,X_2,\ldots,X_N,\ldots$ selon cette loi. La proportion de $X_i$

qui sont égales à une lettre $a_k$

est, d'après la loi des grands nombres, $\mu(a_k)$ . Ce qui nous intéresse est le comportement asymptotique de la probabilité que, sur les N premières lettres, cette proportion ait une valeur très différente, mettons $\nu(a_k)$ . Autrement dit : quelle est la probabilité qu'un dé non pipé sorte des « six » un quart du temps ? (Ou : si un dé prétendu non pipé sort des « six » un quart du temps, que doit-on conclure ?)

est une variable aléatoire dont la valeur est une mesure de probabilité sur $\Sigma$ . (À noter que n'importe quelle mesure sur $\Sigma$ ne peut pas être une mesure empirique : les fréquences doivent être des multiples de $1/N$

Ce qui nous intéresse est d'évaluer la probabilité que $L_N$

soit proche d'une certaine mesure $\nu$ sur $\Sigma$ . Pour cela, on va évaluer la quantité d'information H fournie par l'événement « la mesure empirique est $\nu$ », et la réponse sera alors : la probabilité est $\exp(-NH)$ .

Entropie relative de mesures

On rappelle qu'en théorie de l'information, l'occurrence d'un événement x qui était de probabilité $\mu(x)$ apporte une information

Spécifier un élément d'un ensemble, sachant que cet élément allait être tiré selon la loi $\mu$ , apporte donc en moyenne une information $H(\mu)$ .

Maintenant, on peut se demander quelle information (par rapport à $\mu$ ) est apportée par l'affirmation suivante : « en fait, l'élément va être tiré selon une autre loi $\nu$ ». Cela apporte assurément une information : par exemple, si $\nu$ est concentrée en un point x, cela revient à donner directement x ce qui apporte une information $I_\mu(x)$ . On définit l'information relative :

$H(\nu|\mu)=\E_\nu I_{\nu|\mu}=\sum \nu(x)\log \frac{\nu(x)}{\mu(x)}=\sum \frac{\nu(x)}{\mu(x)}\log \frac{\nu(x)}{\mu(x)}\,\, \mu(x)$

On montre que $H(\nu|\mu)\geq 0$ , d'où le choix des signes (c'est essentiellement la convexité de $x\mapsto x\log x$ ).

L'interprétation est la suivante : si on tire un élément sous la loi $\nu$ , l'information moyenne qui sera au final obtenue sera $\E_\nu I_\mu$ , par rapport à $\mu$ . Or effectuer un tirage selon une loi $\nu$ ne fait apparaître, dans l'absolu, qu'une information $H(\nu)$ . C'est donc qu'en sachant que l'élément allait être tiré selon $\nu$ , on possédait dès le départ une information $\E_\nu I_\mu-H(\nu)=H(\nu|\mu)$ , par rapport à la loi $\mu$ .

Moralement, cette quantité d'information peut servir à définir une distance sur l'espace des mesures de probabilité sur un ensemble (mais elle n'est pas symétrique).

Grandes déviations pour la mesure empirique

Revenons à la loi de la mesure empirique $L_N$

de variables aléatoires $X_i$

tirées dans $\Sigma$ selon la loi $\mu$ . Un raisonnement intuitif, à ce point, permettrait d'obtenir le résultat. En effet, si la loi empirique est $L_N$

, c'est comme si on avait tiré N fois de suite les $X_i$

selon la loi $L_N$

. Ceci apporte une information $NH(L_N|\mu)$ . Un événement d'information H ayant probabilité $\exp(-H)$ , on en conclut que la probabilité que la mesure empirique $L_N$

soit égale à une certaine loi $\nu$ se comporte comme $\exp(-NH(\nu|\mu))$ .

Cela se passe presque ainsi. Soit donc $\nu$ une loi sur $\Sigma$ . Soit $x_1,x_2,\ldots,x_N$ une suite de lettres de $\Sigma$ , telle que la proportion de $x_i$

égaux à une lettre $a_k\in \Sigma$ soit $\nu(a_k)$ . Calculons la probabilité (sous $\mu$ ) que $X_i=x_i$

. Cette probabilité est $\prod_i \mu(x_i)=\prod_k \mu(a_k)^{N\nu(a_k)}$ , et ou encore $\exp(N\sum \nu(a_k)\log \mu(a_k))$ , soit encore

Pour évaluer la probabilité que la fréquence empirique soit $\nu$ , il reste donc à multiplier cette quantité par le nombre de suites $x_1,\ldots,x_N$ telles que la proportion des $x_i$

égaux à la letrte $a_k$

soit $\nu$ . Pour cela, on suppose bien sûr que $\nu$ est réalisable comme une telle fréquence, i.e. que les valeurs de $\nu$ sont multiples de $1/N$

Ce nombre vaut $N!/\prod_k (N\nu(a_k))!$ , qui, par un calcul très simple (essentiellement, celui de Boltzmann), vaut environ $\exp(NH(\nu))$ quand N est grand (à un facteur polynomial en N près), ce qui est bien naturel quand on sait que spécifier une suite particulière parmi l'ensemble des suites de fréquence empirique $\nu$ , fournit une information $NH(\nu)$ .

Conclusion : si $\nu$ est réalisable comme fréquence d'une suite à N termes, alors la probabilité, sous $\mu$ , que la fréquence empirique $L_N$

soit égale à $\nu$ est donc environ $\exp(NH(\nu))\exp(-N(H(\nu)+H(\nu|\mu)))$ , soit

Pour se débarrasser des problèmes de lois réalisables ou non, on va plutôt calculer la probabilité que $L_N$

tombe dans un petit ensemble autour de $\nu$ . On énonce alors le théorème de Sanov :

Théorème.

Soit A une partie de l'ensemble des mesures de probabilité sur $\Sigma$ , et soit $\overset{\circ}A$ son intérieur. La probabilité que la mesure empirique $L_N$

d'une suite de variables indépendantes tirées dans $\Sigma$ avec la loi $\mu$ , appartienne à A, vérifie :

$-\inf_{\nu\in \overset{\circ}A}H(\nu|\mu)\leq \vliminf_{N\rightarrow \infty}\frac 1N \log\P_\mu(L_N\in A) \leq \vlimsup_{N\rightarrow \infty}\frac 1N \log\P_\mu(L_N\in A) \leq -\inf_{\nu\in A} H(\nu|\mu)$

Autrement dit, c'est la mesure la plus « proche » de $\mu$ au sens de la distance $H(\nu|\mu)$ qui contrôle le taux de décroissance de cette probabilité.

Le principe des grandes déviations

Le principe des grandes déviations est une généralisation de la situation précédente. En particulier, on ne demande plus forcément l'indépendance. On considère donc une suite de mesures de probabilité $\mu_N$ sur un espace X régulier (par exemple, métrisable avec sa tribu borélienne). On comprend que la mesure $\mu_N$ dépend de N « événements de base ». L'information ne croît pas forcément linéairement en N, on considère donc une suite de nombres $a_N$

qui jauge cette croissance.

On considère une fonction $I:X\rightarrow[0;\infty]$ candidate à être la fonction entropie des $\mu_N$ . On suppose en général que I est semi-continue inférieurement (c'est-à-dire que les $I^{-1}([0;A])$ sont fermés), et on qualifie cette fonction de « bonne fonction de taux » si les $I^{-1}([0;A])$ sont compacts.

On dit alors que la famille $\mu_N$ satisfait le principe des grandes déviations pour la bonne fonction de taux I, si pour tout fermé $F\subset X$ , on a

$\vliminf_{N\rightarrow\infty}\frac1{a_N}\log \mu_N(\mathcal{O})\geq -\inf_{\mathcal{O}}I$

Le principe de grandes déviations est donc analogue à l'existence d'une entropie.

Les gaussiennes

Si on a des variables satisfaisant un principe de grandes déviations, et que la fonction d'entropie I admet un minimum (qui vaut alors forcément $0$

, la probabilité totale étant $1$

) et est régulière, il est tentant de développer I à l'ordre $2$

au voisinage de ce minimum, pour trouver que la renormalisation en $1/\sqrt{N}$ plutôt qu'en $1/N$

, autour de la moyenne, donne une gaussienne... Bien sûr, on aurait aussi pu développer la probabilité à l'ordre $2$

au voisinage de son maximum, on aurait trouvé que localement la probabilité se comportait comme une parabole osculant la gaussienne ci-dessus à l'ordre $2$

. Pour que la probabilité ressemble vraiment à une gaussienne, il faut donc vérifier que le développement de I est valable (par exemple, il suffit que la dérivée troisième soit contrôlée).

Alors, si I a un unique minimum au point z, on peut vérifier que $I(z+a/\sqrt{N})\sim I''(z)\,a^2/2N$ et que la probabilité correspondante est donc $\approx e^{-NI}\approx e^{-I''(z)a^2\!/2}$ , autrement dit qu'on a une gaussienne de variance $1/I''(z)$

On avait vu en théorie de l'information que les gaussiennes maximisaient l'entropie à variance donnée, c'est exactement le phénomène qu'on retrouve ici : notre estimation de probabilités provient d'une maximisation d'entropie, et on renormalise à l'ordre deux au voisinage du maximum. Une fois de plus, les gaussiennes trouvent leur origine dans une quantité d'information...

Le théorème de Gärtner-Ellis

Première généralisation

À ce stade, on peut donner une première généralisation : plutôt que de s'intéresser à la mesure empirique des $X_i$

, on peut considérer une fonction quelconque $f:\Sigma\rightarrow \R^d$ , et s'intéresser à sa moyenne empirique $\widehat{f}=\frac1N\sum f(X_i)$ . Si on prend $d=\abs{\Sigma}$ et qu'on prend $f(a_k)$

égal au k-ième vecteur d'une base de $\R^d$ , on retrouve bien évidemment le cas précédent.

Si $\widehat{f}=y$ , cela signifie que la fréquence empirique $L_N$

des

vérifie $\E_{L_N}f=y$ , par définition. On est donc tenté de dire que la probabilité que $\widehat{f}=y$ est la somme, pour toutes les mesures $\nu$ sur $\Sigma$ satisfaisant $\E_\nu f=y$ , de la probabilité que $L_N=\nu$ . Cette probabilité, comme ci-dessus, est asymptotiquement $\exp(-NH(\nu|\mu))$ .

Quand N est grand, seule la contribution du meilleur $\nu$ (c'est-à-dire celui minimisant la « distance » $H(\nu|\mu)$ ) compte, les autres devenant négligeables. Posons donc, pour $y\in \R^d$ :

$I(y)=\inf \{H(\nu|\mu), \nu\text{ mesure de probabilité sur }\Sigma\text{ telle que }\E_\nu f=y\}$

Théorème.

Soit $A\subset \R^d$ , d'intérieur $\overset{\circ}A$ . La probabilité que la moyenne empirique $\widehat{f}$ tombe dans A vérifie

$-\inf_{\overset{\circ}A}I\leq \vliminf_{N\rightarrow\infty} \frac 1N \log \P_\mu(\widehat{f}\in A) \leq \vlimsup_{N\rightarrow\infty} \frac 1N \log \P_\mu(\widehat{f}\in A) \leq -\inf_{A} I$

Cas général

On va désormais illustrer ce principe dans un cas un peu plus général que le théorème de Sanov. Soient $X_i$

des variables aléatoires à valeurs dans $\R^d$ , éventuellement non indépendantes, ni identiquement distribuées. On considère la moyenne empirique $S_N=\frac1N\sum_{i=1}^N X_i$ . Soit $\mu_N$ la loi de $S_N$

. On va montrer que sous certaines hypothèses, $\mu_N$ satisfait un principe de grandes déviations, pour une fonction de taux à déterminer.

Comme précédemment, on a envie de dire que si $S_N=y$

, cela signifie qu'en fait, les $X_i$

ont collectivement une distribution empirique $\nu$ qui est de moyenne y, i.e. $\int_{t\in\R^d} t \,d\nu(t)=y$ .

On voudrait alors dire que la probabilité d'une telle situation est $\exp -H(\nu|\mu_N)$ , ou plutôt $\exp -\inf H(\nu|\mu_N)$ , l'inf étant pris sur toutes les mesures $\nu$ satisfaisant la contrainte d'être de moyenne y : asymptotiquement, les contributions des mesures ne réalisant pas l'inf sont négligeables.

Comme les

ne sont pas indépendantes, on va plutôt travailler avec la loi jointe $\rho_N$ du N-uplet $(X_i)$

dans $(\R^d)^N$ . On cherche maintenant des lois $\nu$ sur $(\R^d)^N$ soumises à la contrainte que $\sum_{i=1}^N \int_{t\in \R^d} t \,d\nu_i=Ny$ , où $\nu_i$ est la loi de la i-ième composante de $\nu$ : la somme des moyennes sur chaque composante doit être égale à Ny. Parmi celles-ci on cherche celle qui a l'entropie minimale par rapport à la mesure $\rho_N$ .

Ici intervient la remarque fondamentale suivante : à moyenne fixée, les distributions qui minimisent l'entropie sont les distributions exponentielles (ou maxwelliennes) de la forme $d\nu(x)=e^{\lambda.x}/Z$ , où $Z=\int e^{\lambda.x}$ est la constante de normalisation, appelée fonction de partition par les physiciens. Ceci se démontre par un calcul variationnel simple, identique à celui qui montre qu'à variance fixées, ce sont les gaussiennes.

Pour minimiser l'entropie par rapport à la mesure $\rho_N$ , il est donc suffisant de chercher parmi les mesures de la forme $d\nu(x)=\frac1Z e^{\lambda. Ex}\,d\rho_N(x)$ où $\lambda$ est un élément de $\R^d$ , le produit $\lambda. Ex$ étant un produit scalaire. Cet élément $\lambda$ est à déterminer de sorte que la moyenne $\E E=E \int_{x\in(\R^d)^n} x\,d\nu$ soit égale à Ny.

Ce qui nous intéresse est l'entropie de la distribution. Or pour les distributions exponentielles, il y a une relation simple entre entropie et moyenne. La moyenne de la distribution $e^{\lambda.x}/Z$ est $\E E=\frac1Z \int x e^{\lambda.x}$ et son entropie est $\frac1Z \int e^{\lambda. x} \log(e^{\lambda. x}/Z)=\E E-\log Z$ .

On voit donc qu'une distribution exponentielle de moyenne $\E_\nu E=Ny$ a une entropie $\lambda Ny-\log Z$ .

Reste quand même à déterminer $\lambda$ . Là encore la forme exponentielle de la loi de probabilité joue : la dérivée de $\log Z$ par rapport à $\lambda$ est précisément l'espérance de la distribution exponentielle. En effet, on a

$\frac{d}{d\lambda}\log Z= \frac1Z \frac{d}{d\lambda} \int e^{\lambda.x}=\frac1Z \int x e^{\lambda.x}$

Le $\lambda$ recherché vérifie donc $\frac{d}{d\lambda}(\lambda Ny-\log Z)=Ny-\E E=0$ , autrement dit le $\lambda$ recherché est un extrémum de $\lambda Ny-\log Z$ . C'est en fait un maximum car $\log Z$ est une fonction convexe de $\lambda$ .

Dans le principe de grandes déviations $\P\left(\frac1N \sum X_i=y\right)\approx e^{-NI(y)}$ , on doit donc poser :

$Z(\lambda)=\int_{(t_1,\ldots,t_N)\in (\R^d)^N} \exp\left(\lambda \sum t_i\right) \,d\rho_N(t_1,\ldots,t_N)$

On a donc réussi, grâce à la remarque que les minima d'entropie sont obtenus pour les distributions exponentielles, à donner une recette de calcul de l'entropie de l'événement « la moyenne est égale à y ».

Ceci nous amène donc à énoncer le théorème de Gärtner-Ellis. Cependant, il faut faire attention à l'énoncé : par exemple, nos raisonnements ci-dessus étaient à N fixé ; il faut donc que $I(y)$

converge quand $N\rightarrow \infty$ , vers une certaine valeur, ce qui ne se produit que si les $X_i$

n'ont pas des distributions trop sauvages.

De plus, lorsque la limite $\frac1N\log Z(\lambda)$ n'est pas différentiable, il n'y a pas forcément de $\lambda$ donnant une exponentielle de moyenne y pour tout y, ce qui n'empêche pas que $\sup_{\lambda \in \R^d} \lambda.y - \frac1N \log Z(\lambda)$ ait une certaine valeur. Un même $\lambda$ peut ainsi maximiser $\lambda.y - \frac1N \log Z(\lambda)$ pour plusieurs y. Disons que $y\in \R^d$ est un point exposé si le $\lambda$ maximisant cette quantité ne maximise pas aussi cette quantité pour un autre $y'$

, cela revient à dire que y est exposé s'il existe un $\lambda$ tel que pour tout $y'\neq y$ , on a $\lambda. y- \sup_{\lambda'}(\lambda'.y-\frac1N\log Z(\lambda')) > \lambda. y' - \sup_{\lambda'}(\lambda'.y'-\frac1N\log Z(\lambda'))$ . Les points exposés sont ceux pour lesquels le fait que $\lambda$ maximise l'entropie implique bien que l'espérance de la distribution exponentielle de paramètre $\lambda$ vaut y.

L'énoncé est alors le suivant. Il se place dans un cadre un peu plus général où on ne considère pas forcément une somme de variables aléatoires ; de plus, il se peut que la bonne renormalisation ne soit pas N mais $a_N$

où

est une suite tendant vers l'infini.

Théorème.

Soit $(\mu_N)$ une suite de lois de probabilité sur $\R^d$ et soit $a_N$

une suite tendant vers l'infini. Pour $\lambda \in \R^d$ , on pose

$Z_N(\lambda)=\E_{\mu_N} e^{a_N\,\lambda.t}$

et on suppose que la limite

$\Lambda(\lambda)=\lim_N \frac1{a_N}\log Z_N(\lambda)$

existe et est finie pour $\lambda$ dans un voisinage de $0$

. Pour $y\in\R^d$ , soit

$I(y)=\sup_{\lambda\in\R^d} \lambda.y-\Lambda(\lambda)$

et soit $\mathcal{P}$ l'ensemble des points y exposés. Alors, si A est une partie de $\R^n$ , d'adhérence $\overline{A}$ et d'intérieur $\overset{\circ}A$ , on a

$\vlimsup_N \frac1{a_N}\log \mu_N(A)\leq -\inf_{\overline{A}} I$

$\vliminf_N\frac1{a_N}\log \mu_N(A)\geq -\inf_{\overset{\circ}A \cap \mathcal{P}} I$

Reconnaissons que sans explication par la théorie de l'information, l'énoncé pourrait rester mystérieux.

Là encore, le sujet n'est pas clos : on peut chercher à montrer qu'un principe des grandes déviations est satisfait dans des contextes plus généraux (par exemple des chaînes de Markov), vouloir obtenir des bornes explicites plutôt que des relations asymptotiques, montrer que les grandes déviations sont contrôlées uniformément pour un grand nombre de fonctions-tests de la variable étudiée, ou encore étudier les innombrables et délicates applications à la physique statistique...