\documentclass[A4paper]{article} \usepackage{amsmath,amssymb} \usepackage[ansinew]{inputenc} \usepackage[francais]{babel} \usepackage[pdftex]{graphicx} \usepackage{color} \usepackage{fig4tex} \textwidth=15truecm \textheight=22.8truecm \hoffset=-12mm \voffset=-9mm \baselineskip=12pt \newdimen\finwidth \finwidth=\textwidth \advance \finwidth by -3cm \def\finducours#1{ \vskip.5cm \hbox{{\vrule height 2pt width \finwidth} Fin du cours n$^0$#1} \vskip.5cm\par} \def\sugg#1#2{ \medskip {\bf Suggestion d'exercice} : n$^0$#1, feuille #2. \medskip} \title{Entropie} \author{P. Pansu} \newtheorem{theo}{Th{\'e}or{\`e}me} \newtheorem{lemme}{Lemme} \newtheorem{prop}[lemme]{Proposition} \newtheorem{cor}[lemme]{Corollaire} \newtheorem{defi}[lemme]{D{\'e}finition} \newtheorem{rem}[lemme]{Remarque} \newtheorem{ex}[lemme]{Exemple} \newtheorem{exo}[lemme]{Exercice} \newtheorem{rappel}[lemme]{Rappel} \newtheorem{nota}[lemme]{Notation} \newtheorem{ques}[lemme]{Question} \newenvironment{pf}{\begin{trivlist}\item[]{\bf Preuve}} {\mbox{}\hfill\rule{.08in}{.08in}\end{trivlist}} \def\R{\mathbb{R}} \def\C{\mathbb{C}} \def\Q{\mathbb{Q}} \def\Z{\mathbb{Z}} \def\N{\mathbb{N}} \def\E{\mathbb{E}} \def\P{\mathbb{P}} \def\div{\hskip-2pt\setminus\hskip-2pt} \def\eps{\epsilon} \def\d{\displaystyle} \def\n#1{|\hskip-1pt |#1|\hskip-1pt|} \begin{document} \maketitle \section*{Conventions} En \textcolor{blue}{bleu}, les paragraphes qui n'ont pas été traités, ou alors de façon évasive. %En \textcolor{red}{rouge}, les démonstrations que tout étudiant doit être capable de refaire. %Les logarithmes seront toujours en base $2$. \section{Motivation} \subsection{L'entropie dans les sciences} L'entropie est une invention de physiciens. Elle apparaît en thermodynamique macroscopique, comme une nécessité théorique : le second principe de la thermodynamique exprime seulement son existence (Clausius 1854). Il y a une formule pour sa variation lors de certaines transformations, mais pas d'expression directe. La physique statistique (Boltzmann) donne de nouvelles fondations, microscopiques, à la thermodynamique, et fournit enfin une expression pour l'entropie d'un système : c'est le logarithme du nombre de configurations microscopiques possibles pour le système. Après la seconde guerre mondiale, l'essor des communications et de nouveaux problèmes (codage, compression) donnent naissance à la théorie de l'information aux Etats-Unis. En 1948, Claude Shannon introduit l'entropie d'une distribution de probabilité finie, l'information mutuelle de deux distributions de probabilité, et la capacité d'un canal de transmission comme l'information mutuelle maximale entre les signaux d'entrée et de sortie. Il prouve que cette capacité est la bien la borne supérieure des taux de transmission autorisés par le canal. Non seulement ces notions capturent bien l'idée de quantité d'information nécessaire pour décrire une variable aléatoire, mais elles permettent de fonder l'entropie des physiciens sur des bases solides. En URSS, Andrei Kolmogorov et Yakov Sinai définissent en 1958 l'entropie d'une transformation préservant la mesure. En 1966, Roy Adler, Alan Konheim et M. McAndrew introduisent l'entropie topologique d'une transformation continue d'un espace topologique compact, les deux notions sont très utiles en systèmes dynamiques. Kolmogorov, et, aux Etats-Unis, Ray Solomonov et Gregory Chaitin, définissent vers 1965 l'entropie d'un mot écrit dans un alphabet fini comme la longueur minimale d'un programme permettant à un ordinateur de produire ce mot. Cette notion s'avère étroitement reliée à l'entropie de Shannon. L'entropie est une notion récente. Elle a déjà envahi beaucoup de domaines des mathématiques (probabilités, statistiques, systèmes dynamiques) et aussi de la physique et de l'informatique théorique. C'est le signe de son intérêt. \subsection{Simulation d'une distribution de probabilité} \label{simul} On lance un dé truqué $n$ fois. Truqué signifie que, pour $k=1,\ldots,6$, la probabilité $p(k)$ de sortie du chiffre $k$ n'est pas égale à $\frac{1}{6}$. On obtient des suites $(x_1 ,\ldots,x_n)$, $x_i \in\{1,\ldots,6\}$. Quelle est la probabilité d'obtenir une suite ``typique''. Par suite typique, on veut dire toutes sauf une fraction qui tend vers $0$ quand $n$ tend vers l'infini. La probabilité d'obtenir la suite $(x_1 ,\ldots,x_n)$ est le produit \begin{eqnarray*} p(x_{1})p(x_{2})\cdots p(x_{n})=\prod_{k=1}^{6}p(k)^{N_k}, \end{eqnarray*} où $N_k$ est le nombre de fois que le chiffre $k$ apparaît dans la suite $(x_1 ,\ldots,x_n)$. Or, d'après la loi des grands nombres, lorsque $n$ est grand, avec forte probabilité, ce nombre $N_k$ est proche de $np(k)$. Donc, pour la très grande majorité des tirages, la probabilité cherchée est proche de \begin{eqnarray*} \prod_{k=1}^{6}p(k)^{np(k)}=\left(\prod_{k=1}^{6}p(k)^{p(k)}\right)^n =2^{-nH}, \end{eqnarray*} où \begin{eqnarray*} H=-\sum_{k=1}^{6}p(k)\log_2 (p(k)). \end{eqnarray*} Pour un dé non pipé, toutes les suites sont obtenues avec la même probabilité $2^{-n\log_2 (6)}$. Pour un dé pipé, la répartition est inégale. La suite typique est obtenue avec une probabilité plus forte, et cette probabilité s'exprime au moyen de la quantité $H$. On appelle $H$ l'entropie de la distribution de probabilité $p$. Le fait que $2^{-nH}\geq 2^{-n\log_2 (6)}$ ne saute pas aux yeux. C'est l'une des nombreuses identités et inégalités qui constituent les paroles de la théorie de l'information. La musique, ce sont les nombreuses interprétations qu'on peut donner des résultats dans différents champs de la science. On va commencer par établir un certain nombre d'identités et d'inégalités. On passera ensuite aux interprétations. \subsection{Bibliographie} On suit de près, et dans cet ordre, les chapitres 2, 5, 4, 3, 7, 16 du livre Thomas Cover and Joy Thomas, {\em Elements of Information Theory}, John Wiley and Sons, Hoboken, NJ (2006). Cote 003.54 COV ele à la BU (rez de jardin). Puis on passe aux livres Vladimir Arnold et André Avez, \emph{Problèmes ergodiques de la mécanique classique}, Gauthier-Villars, Paris (1967). Chapitre 12 et appendices 18 et 19. Ne se trouve pas à la BU, mais à la Bibliothèque Jacques Hadamard. Karl Petersen, {\em Ergodic Theory}, Cambridge Studies in Advanced Mathematics, 2. Cambridge University Press, Cambridge (1989). Chapitres 5 et 6. En magasin, cote K41366 à la BU. \section{Premières propriétés} \subsection{Définition} \begin{defi} Soit $E$ un ensemble fini. Une distribution de probabilité sur $E$, c'est une fonction $p:E\to\R_+$ telle que $\sum_{x\in E}p(x)=1$. L'{\em entropie} de la distribution de probabilité $p$ est le nombre \begin{eqnarray*} H(p)=-\sum_{x\in E}p(x)\log_2 (p(x)). \end{eqnarray*} Elle est mesurée en bits. \end{defi} Par convention, $0\log_2 (0)=0$. Remarquer que $H(p)\geq 0$, avec égalité si et seulement si $p$ est concentrée sur un seul élément de $E$. \def\GraphLegend{$y = -x\log_2 (x)$} % 1. Definition of characteristic points \figinit{mm} \def\Xmin{0} \def\Ymin{0} \def\Xmax{80.00000} \def\Ymax{59.99999} \def\Xori{0} \def\Yori{0} \figpt0:(\Xori,\Yori) % 2. Creation of the graphical file \figdrawbegin{} \def\Xmaxx{\Xmax} % To customize the position \def\Ymaxx{\Ymax} % of the arrow-heads of the axes. \figdrawaxes 0(\Xmin, \Xmaxx, \Ymin, \Ymaxx) \figdrawlineC( 0 0, .89887 8.22590, 1.79775 13.91127, 2.69662 18.63774, 3.59550 22.74148, 4.49438 26.38219, 5.39325 29.65388, 6.29213 32.61871, 7.19101 35.32085, 8.08988 37.79330, 8.98876 40.06172, 9.88764 42.14656, 10.78651 44.06458, 11.68539 45.82970, 12.58426 47.45371, 13.48314 48.94670, 14.38202 50.31744, 15.28089 51.57356, 16.17977 52.72182, 17.07865 53.76822, 17.97752 54.71811, 18.87640 55.57634, 19.77528 56.34727, 20.67415 57.03487, 21.57303 57.64277, 22.47191 58.17428, 23.37078 58.63248, 24.26966 59.02017, 25.16853 59.33997, 26.06741 59.59430, 26.96629 59.78543, 27.86516 59.91546, 28.76404 59.98637, 29.66292 59.99999, 30.56179 59.95808, 31.46067 59.86226, 32.35955 59.71407, 33.25842 59.51496, 34.15730 59.26632, 35.05617 58.96945, 35.95505 58.62559, 36.85393 58.23590, 37.75280 57.80151, 38.65168 57.32349, 39.55056 56.80284, 40.44943 56.24054, 41.34831 55.63751, 42.24719 54.99464, 43.14606 54.31277, 44.04494 53.59272, 44.94382 52.83527, 45.84269 52.04116, 46.74157 51.21112, 47.64044 50.34583, 48.53932 49.44597, 49.43820 48.51216, 50.33707 47.54503, 51.23595 46.54518, 52.13483 45.51317, 53.03370 44.44957, 53.93258 43.35490, 54.83146 42.22969, 55.73033 41.07443, 56.62921 39.88962, 57.52808 38.67571, 58.42696 37.43317, 59.32584 36.16243, 60.22471 34.86393, 61.12359 33.53807, 62.02247 32.18526, 62.92134 30.80589, 63.82022 29.40034, 64.71910 27.96898, 65.61797 26.51216, 66.51685 25.03024, 67.41573 23.52355, 68.31460 21.99243, 69.21348 20.43719, 70.11235 18.85816, 71.01123 17.25562, 71.91011 15.62989, 72.80898 13.98125, 73.70786 12.30999, 74.60674 10.61637, 75.50561 8.90068, 76.40449 7.16317, 77.30337 5.40410, 78.20224 3.62371, 79.10112 1.82227, 80.00000 0 ) \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figptsaxes 1:0(\Xmin, \Xmaxx, \Ymin, \Ymaxx) % Points 1 and 2 are the end points of the arrows \figwritee 1:(5pt) \figwriten 2:(5pt) \figptsaxes 1:0(\Xmin, \Xmax, \Ymin, \Ymax) % Points 1 and 2 are the first two end points of the axes \figwrites 1:$1.0$(5pt) \figwritew 2:$.5$(8pt) % Points 3 and 4 are the two other end points of the axes \figpttraC 3:=0/\Xmin,0/ \figwrites 3:$0$(5pt) \figpttraC 4:=0/0,\Ymin/ \figwritew 4:$0$(8pt) } \centerline{\box\figBoxA} \begin{ex} L'entropie de la distribution uniforme sur $E$ vaut $\log_2 |E|$ bits. \end{ex} Une distribution uniforme sur un ensemble $E$ à $2^n$ éléments a donc une entropie de $n$ bits. D'ailleurs, on peut numéroter les éléments de $E$ avec $n$ bits seulement. Plus généralement, on verra plus tard que l'entropie est aussi le nombre moyen (au sens de la distribution $p$) de bits nécessaire pour coder $E$. C'est pourquoi on prend le logarithme en base $2$ et l'unité choisie est appelée bit. \sugg11 \begin{ex} Soit $a\in[0,1]$. Soit $E=\{0,1\}$. Soit $p_a =\mathcal{B}(a)$ la distribution de Bernoulli de paramètre $a$, i.e $p_a (1)=a$, $p_a (0)=1-a$. L'entropie de $\mathcal{B}(a)$ vaut $h(a):=-a\log_2 (a)-(1-a)\log_2 (1-a)$ bits. \end{ex} Voir courbe représentative de $h$. %\input fig4tex \def\GraphLegend{$y = -x\log_2 (x)-(1-x)\log_2 (1-x)$} % 1. Definition of characteristic points \figinit{mm} \def\Xmin{0} \def\Ymin{0} \def\Xmax{80.00000} \def\Ymax{59.99999} \def\Xori{0} \def\Yori{0} \figpt0:(\Xori,\Yori) % 2. Creation of the graphical file \figdrawbegin{} \def\Xmaxx{\Xmax} % To customize the position \def\Ymaxx{\Ymax} % of the arrow-heads of the axes. \figdrawaxes 0(\Xmin, \Xmaxx, \Ymin, \Ymaxx) \figdrawlineC( 0 0, .89887 5.33326, 1.79775 9.30704, 2.69662 12.76068, 3.59550 15.87248, 4.49438 18.72707, 5.39325 21.37423, 6.29213 23.84679, 7.19101 26.16806, 8.08988 28.35541, 8.98876 30.42230, 9.88764 32.37945, 10.78651 34.23558, 11.68539 35.99793, 12.58426 37.67258, 13.48314 39.26472, 14.38202 40.77882, 15.28089 42.21877, 16.17977 43.58795, 17.07865 44.88937, 17.97752 46.12567, 18.87640 47.29923, 19.77528 48.41214, 20.67415 49.46630, 21.57303 50.46342, 22.47191 51.40504, 23.37078 52.29254, 24.26966 53.12718, 25.16853 53.91009, 26.06741 54.64231, 26.96629 55.32478, 27.86516 55.95832, 28.76404 56.54371, 29.66292 57.08164, 30.56179 57.57271, 31.46067 58.01749, 32.35955 58.41646, 33.25842 58.77005, 34.15730 59.07864, 35.05617 59.34255, 35.95505 59.56207, 36.85393 59.73742, 37.75280 59.86877, 38.65168 59.95627, 39.55056 59.99999, 40.44943 59.99999, 41.34831 59.95627, 42.24719 59.86877, 43.14606 59.73742, 44.04494 59.56207, 44.94382 59.34255, 45.84269 59.07864, 46.74157 58.77005, 47.64044 58.41646, 48.53932 58.01749, 49.43820 57.57271, 50.33707 57.08164, 51.23595 56.54371, 52.13483 55.95832, 53.03370 55.32478, 53.93258 54.64231, 54.83146 53.91009, 55.73033 53.12718, 56.62921 52.29254, 57.52808 51.40504, 58.42696 50.46342, 59.32584 49.46630, 60.22471 48.41214, 61.12359 47.29923, 62.02247 46.12567, 62.92134 44.88937, 63.82022 43.58795, 64.71910 42.21877, 65.61797 40.77882, 66.51685 39.26472, 67.41573 37.67258, 68.31460 35.99793, 69.21348 34.23558, 70.11235 32.37945, 71.01123 30.42230, 71.91011 28.35541, 72.80898 26.16806, 73.70786 23.84679, 74.60674 21.37423, 75.50561 18.72707, 76.40449 15.87248, 77.30337 12.76068, 78.20224 9.30704, 79.10112 5.33326, 80.00000 0 ) \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figptsaxes 1:0(\Xmin, \Xmaxx, \Ymin, \Ymaxx) % Points 1 and 2 are the end points of the arrows \figwritee 1:(5pt) \figwriten 2:(5pt) \figptsaxes 1:0(\Xmin, \Xmax, \Ymin, \Ymax) % Points 1 and 2 are the first two end points of the axes \figwrites 1:$1.0$(5pt) \figwritew 2:$1.0$(8pt) % Points 3 and 4 are the two other end points of the axes \figpttraC 3:=0/\Xmin,0/ \figwrites 3:$0$(5pt) \figpttraC 4:=0/0,\Ymin/ \figwritew 4:$0$(8pt) } \centerline{\box\figBoxA} On constate que $h$ est une fonction concave de $a$. On va le démontrer bientôt (Exemple \ref{exconvD}). \subsection{Vocabulaire probabiliste} On fixe une fois pour toutes un ensemble $\Omega$ muni d'une tribu et d'une mesure de probabilité $\P$. Soit $E$ un ensemble muni d'une tribu (ce sera pratiquement toujours un ensemble fini muni de la tribu de tous ses sous-ensembles). Une variable aléatoire à valeurs dans $E$ est une fonction mesurable $X:\Omega\to E$. La {\em loi} ou la {\em distribution} de $X$ est la distribution de probabilité $p_X$ sur $E$ définie par \begin{eqnarray*} p_X (x)=\P(X=x). \end{eqnarray*} L'espérance de $X$ est le nombre \begin{eqnarray*} \E(X)=\int_{\Omega}X\,d\P=\int_{E}x\,dp_X (x)=\sum_{x\in E}x p_X (x) \end{eqnarray*} dans le cas où $E$ est fini. \begin{nota} Si $X$ est une variable aléatoire de distribution $p_X$, on note $H(X)=H(p_X)$, et on l'appelle l'{\em entropie} de $X$. On peut l'exprimer comme une espérance, \begin{eqnarray*} H(X)=\E(-\log_2 p(X)). \end{eqnarray*} \end{nota} Si on cherche à mesurer la quantité d'information $I(A)$ contenue dans l'évènement $X\in A$, $A\subset E$, la formule qui s'impose est $I(A)=\log\frac{1}{\P(X\in A)}$. En effet, $I$ doit être fonction décroissante de $\P(X\in A)$, et pour deux évènements $A$ et $B$ indépendants, on souhaite que \begin{eqnarray*} I(A\cap B)=I(A)+I(B), \end{eqnarray*} donc $I$ est positivement proportionnelle à $\log\frac{1}{\P(X\in A)}$. L'entropie est donc la quantité d'information fournie en moyenne par $X$. Tant qu'on ne connait pas $X$, il s'agit plutôt d'une quantité d'incertitude. Si $X$ est constante, $H(X)=0$. De toutes les variables de Bernoulli, c'est $\mathcal{B}(\frac{1}{2})$ qui est la plus incertaine. \sugg21 \subsection{Entropie relative et information mutuelle} \begin{defi} Soient $p$ et $q$ deux distributions de probabilité sur le même ensemble $E$. Leur {\em entropie relative} est \begin{eqnarray*} D(p||q):=\sum_{x\in E_X}p(x)\log_2 (\frac{p(x)}{q(x)}). \end{eqnarray*} \end{defi} On verra bientôt qu'on peut penser à l'entropie relative comme à une sorte de distance entre $p$ et $q$ (elle est positive, elle est nulle seulement si $p=q$). Toutefois, elle n'est pas symétrique. Attention, elle prend la valeur $+\infty$ s'il existe $x$ tel que $q(x)=0$ mais $p(x)\not=0$. \begin{ex} Soit $\mathcal{B}(a)$ la distribution de Bernoulli sur $\{0,1\}$, qui met le poids $a$ sur $1$ et $1-a$ sur $0$. Alors \begin{eqnarray*} D(\mathcal{B}(a)||\mathcal{B}(a'))=(1-a)\log_2 (\frac{1-a}{1-a'})+a\log_2(\frac{a}{a'}) \end{eqnarray*} n'est pas symétrique en $a$, $a'$. \end{ex} Attention à la notation $||$. \begin{defi} Soient $X$ et $Y$ deux variables aléatoires. Leur {\em information mutuelle} est l'entropie relative de la loi du couple $p_{(X,Y)}$ et du produit des lois marginales $p_X \otimes p_Y$ sur $E_X \times E_Y$, \begin{eqnarray*} I(X;Y):&=&D(p_{(X,Y)}||p_X \otimes p_Y)\\ &=&\sum_{(x,y)\in E_X \times E_Y}p_{(X,Y)}(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_X (x)p_Y (y)}). \end{eqnarray*} \end{defi} Attention au ;. On verra qu'on peut interpréter $I(X;Y)$ comme la quantité d'information sur $X$ qu'on gagne en apprenant $Y$. Par définition, $I(Y;X)=I(X;Y)$, donc on apprend autant sur $X$ en découvrant $Y$ qu'on apprend sur $Y$ en découvrant $X$. \begin{ex} Si $X$ et $Y$ sont indépendantes, leur information mutuelle est nulle. \end{ex} \subsection{Inégalité de Jensen} C'est l'outil utilisé pour prouver les inégalités annoncées plus haut. \begin{defi} Soit $I$ un intervalle de $\R$. Une fonction $f:I\to\R$ est {\em convexe} si sa courbe représentative est en-dessous de toutes ses cordes. Autrement dit, si, pour tous $x$, $y\in I$ et $t\in[0,1]$, \begin{eqnarray*} f((1-t)x+ty)\leq (1-t)f(x)+tf(y). \end{eqnarray*} $f$ est {\em concave} si $-f$ est convexe. On dit que $f$ est {\em strictement convexe} si l'inégalité est stricte dès que $x\not=y$ et $t\in]0,1[$. Plus généralement, si $C\subset\R^n$ est un ensemble convexe, on dit qu'une fonction $f:C\to\R$ est convexe si sa restriction à tout segment de droite est convexe. \end{defi} \begin{prop} Si $f:I\to\R$ est de classe $C^2$ et $f''\geq 0$, alors $f$ est convexe. Si $f''>0$, alors $f$ est strictement convexe. \end{prop} \begin{pf} On pose $g_{\eps}(t)=f((1-t)x+ty)-(1-t)f(x)-tf(y)-\eps t(1-t)$. Alors $g(0)=g(1)=0$. Par l'absurde. Si $g_{\eps}$ prend une valeur $>0$, alors elle atteint son maximum en $c\in]0,1[$. En ce point, $g'_{\eps}(c)=0$ et $g''_{\eps}(c)\leq 0$. Or $g''_{\eps}(c)=f''((1-c)x+cy)+2\eps>0$, contradiction. On conclut que $g_{\eps}\leq 0$ partout. Comme ceci est vrai pour tout $\eps>0$, on conclut que $f((1-t)x+ty)-(1-t)f(x)-tf(y)\leq 0$ pour tout $t\in[0,1]$. Lorsque $f''>0$ et $x\not=y$, on modifie le raisonnement par l'absurde comme suit. On pose $\eps=0$. On suppose que $g_0$ prend une valeur $\geq 0$ dans l'intervalle $]0,1[$. Elle atteint son maximum en $c\in]0,1[$. En ce point, $g''_{0}(c)\leq 0$. Or $g''_{0}(c)=(y-x)^2 f''((1-c)x+cy)>0$, contradiction. On conclut que $g_0 <0$ sur $]0,1[$, donc $f((1-t)x+ty)-(1-t)f(x)-tf(y)< 0$ pour tout $t\in]0,1[$. \end{pf} \begin{ex} $f(x)=|x|$ est convexe, $x^2$, $2^x$ sont strictement convexes, $f(x)=1/x$, $x\log_2 x$ sont strictement convexes sur $]0,+\infty[$, $f(x)=\sqrt{x}$, $\log_2 (x)$ sont strictement concaves sur $]0,+\infty[$. Les fonctions affines sont à la fois convexes et concaves sur $\R$. \end{ex} \begin{prop}\label{aff} Soit $f:I\to\R$ une fonction convexe. Alors $f$ est la borne supérieure d'une famille de fonctions affines. \end{prop} \begin{pf} Soit $x\in I$. Comme le graphe de $f$ passe en dessous de ses cordes, la pentes des cordes issues de $x$, i.e. le taux de variation $y\mapsto \Delta(y)=\frac{f(y)-f(x)}{y-x}$, est une fonction croissante. Il possède donc une limite à droite $f'(x+)$ en $x$. Pour $y\geq x$, \begin{eqnarray*} f(y)=f(x)+\Delta(y)(y-x)\geq f(x)+f'(x+)(y-x). \end{eqnarray*} Pour $y\leq x$, la même inégalité a lieu ($\Delta (y)\leq f'(x+)$ mais $y-x\leq 0$). Dans les deux cas, $f\geq a_x (y)$ où $a_x$ est la fonction affine définie par $a_x (y)=f(x)+f'(x+)(y-x)$. Il y a égalité en $x$. On conclut que $f$ est la borne supérieure des fonctions affines $a_x$ lorsque $x$ décrit $I$. \end{pf} \begin{theo}[Inégalité de Jensen] Soit $I$ un intervalle de $\R$ et $f:I\to\R$ une fonction convexe. Pour toute variable aléatoire $X$ à valeurs dans $I$, \begin{eqnarray*} f(\E(X))\leq\E(f(X)). \end{eqnarray*} Si $f$ est strictement convexe, l'égalité entraîne que $X$ est presque partout constante. \end{theo} \begin{rem} Lorsque $X$ ne prend qu'un nombre fini $n$ de valeurs, l'inégalité de Jensen n'est autre que \begin{eqnarray*} f(\frac{\sum_{i=1}^{n} a_i x_i}{\sum_{i=1}^{n} a_i})\leq\frac{\sum_{i=1}^{n} a_i f(x_i)}{\sum_{i=1}^{n} a_i}, \end{eqnarray*} lorsque $a_i \geq 0$ pour tout $i$, avec égalité si et seulement si $f$ prend la même valeur à tous les points $x_i$ dont le poids $a_i$ est non nul, dans le cas où $f$ est strictement convexe. \end{rem} \begin{pf} Bien que ce ne soit pas nécessaire, on commence par traiter le cas fini. On raisonne par récurrence sur $n$. Par définition, elle est vraie pour $n=2$. Supposons l'inégalité vraie pour $n$ points. Etant donnés $a_0 ,a_1 ,\ldots,a_n \geq 0$ et $x_0 ,x_1 ,\ldots,x_n$, posons $a'_1 =a_0 +a_1$, $x'_1 =\frac{a_0 x_0 +a_1 x_1}{a_0 +a_1}$, et, pour $i\geq 2$, $a'_i =a_i$, $x'_i =x_i$. Par convexité de $f$, \begin{eqnarray*} f(x'_1)\leq\frac{a_0 f(x_0)+a_1 f(x_1)}{a_0 +a_1}. \end{eqnarray*} Avec l'hypothèse de récurrence, \begin{eqnarray*} f(\frac{\sum_{i=0}^{n} a_i x_i}{\sum_{i=0}^{n} a_i}) &=&f(\frac{\sum_{i=1}^{n} a'_i x'_i}{\sum_{i=1}^{n} a'_i})\\ &\leq&\frac{\sum_{i=1}^{n} a'_i f(x'_i)}{\sum_{i=1}^{n} a'_i}\\ &=&\frac{(a_0 +a_1)f(x'_1)+\sum_{i=2}^{n} a_i f(x_i)}{\sum_{i=0}^{n} a_i}\\ &\leq&\frac{\sum_{i=0}^{n} a_i f(x_i)}{\sum_{i=0}^{n} a_i}, \end{eqnarray*} ce qu'il fallait démontrer. Par l'hypothèse de récurrence, l'égalité entraîne que $f$ prend la même valeur en tous les $x'_i$ dont les poids sont non nuls, et que cette valeur est égale à $\frac{a_0 f(x_0)+a_1 f(x_1)}{a_0 +a_1}$. Si $a_0$ et $a_1$ sont non nuls, cela entraîne que $f(x_0)=f(x_1)=f(x_2)=\cdots=f(x_n)$. Dans le cas général, on utilise la Proposition \ref{aff}. Par hypothèse, $f=\sup_{j\in J}a_j$ où chaque fonction $a_j$ est affine. Alors pour tout $j$, $\E(f(X))\geq\E(a_j (X))=a_j (\E(X))$. En prenant le sup sur $J$, il vient $f(\E(X))\leq\E(f(X))$. Cas d'égalité. Supposons que $f(\E(X))=\E(f(X))$. On pose $x=\E(X)$. On decompose $\Omega$ en $\Omega_1 =\{X0$ et $1-t>0$. On munit $\Omega_1$ de la mesure de probabilité $\frac{1}{1-t}\P_{|\Omega_1}$ et $\Omega_2$ de la mesure de probabilité $\frac{1}{t}\P_{|\Omega_2}$. Soit $X_i$ la restriction de $X$ à $\Omega_i$. Alors $X_1$ et $X_2$ sont des variables aléatoires (ce sont les conditionnements de $X$ aux évènements $\{X<\E(X))\}$ et $\{X\geq \E(X)\}$). On pose $x_i =\E(X_i)$ (on pourrait les noter $\E(X|X0} Soient $p$ et $q$ deux distributions de probabilité sur le même ensemble $E$. Alors $D(p||q)\geq 0$ avec égalité si et seulement si $p=q$. \end{theo} \begin{pf} Soit $X$ une variable aléatoire de distribution $p$. En utilisant l'inégalité de Jensen, il vient \begin{eqnarray*} D(p||q)&=&\E(\log_2 (\frac{p(X)}{q(X)}))=\E(-\log_2 (\frac{q(X)}{p(X)}))\\ &\geq&-\log_2(\E(\frac{q(X)}{p(X)}))=-\log_2(\sum_{x\in E}p(x)\frac{q(x)}{p(x)})=-\log_2(\sum_{x\in E}q(x))\\ &=&0. \end{eqnarray*} Par stricte concavité du log, l'égalité entraîne que la variable $\frac{q(X)}{p(X)}$ est constante, donc $p$ et $q$ sont proportionnelles, donc elles sont égales (puisque la somme de leurs valeurs vaut $1$). \end{pf} \begin{ex} Pour toute distribution $p$ sur un ensemble fini $E$, $H(p)\leq\log_2 |E|$ avec égalité si et seulement si $p$ est la distribution uniforme. \end{ex} En effet, soit $u$ la distribution uniforme sur $E$. Alors \begin{eqnarray*} 0\leq D(p||u)=\log_2 |E|-H(X), \end{eqnarray*} avec égalité si et seulement si $p=u$. \begin{cor} Soient $X$ et $Y$ deux variables aléatoires. Alors $I(X;Y)\geq 0$, avec égalité si et seulement si $X$ et $Y$ sont indépendantes. \end{cor} Interprétation : l'information fournie par $Y$ fait diminuer l'incertitude sur $X$, elle diminue strictement sauf si $Y$ est independante de $X$. \begin{pf} Par définition, $I(X;Y)$ est l'entropie relative de la loi du couple et de la loi produit. Elle est donc positive, et nulle seulement si $p_{(X,Y)}=p_X p_Y$, i.e. $X$ et $Y$ sont indépendantes. \end{pf} \sugg31 \subsection{Entropie conditionnelle} \begin{rappel} Soient $X$ et $Y$ deux variables aléatoires, à valeurs dans $E_X$ et $E_Y$ respectivement. Le couple $(X,Y)$ est une variable aléatoire à valeurs dans $E_X \times E_Y$, on note $p_{(X,Y)}$ sa distribution, i.e. pour $x\in E_X$ et $y\in E_Y$, \begin{eqnarray*} p_{(X,Y)}(x,y)=\P(X=x\textrm{ et }Y=y). \end{eqnarray*} Les distributions $p_X$ et $p_Y$ s'en déduisent, \begin{eqnarray*} p_X (x)=\sum_{y\in E_Y}p_{(X,Y)}(x,y),\quad p_Y (y)=\sum_{x\in E_X}p_{(X,Y)}(x,y). \end{eqnarray*} \end{rappel} \begin{nota} Soient $X$ et $Y$ deux variables aléatoires. L'entropie du couple $(X,Y)$ est notée $H(X,Y)$ plutôt que $H((X,Y))$. Autrement dit, \begin{eqnarray*} H(X,Y)=-\sum_{(x,y)\in E_X \times E_Y}p_{(X,Y)}(x,y)\log_2 (p_{(X,Y)}(x,y)). \end{eqnarray*} \end{nota} \begin{rappel} La {\em loi conditionnelle de $Y$ sachant que $X=x$} est la distribution de probabilité notée $p_{Y|X=x}$ définie par \begin{eqnarray*} p_{Y|X=x}(y)=\frac{p_{(X,Y)}(x,y)}{p_X (x)}. \end{eqnarray*} On dit que {\em $X$ et $Y$ sont indépendantes} si $p_{Y|X=x}=p_Y$ pour tout $x$, i.e. si $p_{(X,Y)}(x,y)=p_X (x)p_Y (y)$ pour tout $(x,y)$. \end{rappel} \begin{defi} Soient $X$ et $Y$ deux variables aléatoires, à valeurs dans $E_X$ et $E_Y$ respectivement. On appelle {\em entropie conditionnelle de $Y$ sachant $X$}, et on note $H(Y|X)$ le nombre \begin{eqnarray*} H(Y|X)=\sum_{x\in E_X}p_X (x)H(p_{Y|X=x}). \end{eqnarray*} \end{defi} Autres expressions : \begin{eqnarray*} H(Y|X)&=&-\sum_{x\in E_X}p_X (x)\sum_{y\in E_Y}p_{Y|X=x}(y)\log_2 (p_{Y|X=x}(y))\\ &=&-\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_X (x)}). \end{eqnarray*} \begin{ex} Lorsque $Y=X$, $H(X|X)=0$. \end{ex} En effet, la loi conditionnelle de $X$ sachant que $X=x$ est concentrée en $x$, son entropie est nulle. Informellement, si on connait $X$, il n'y a plus aucune incertitude concernant $X$, d'où une entropie conditionnelle nulle. \begin{prop}\label{entrcond} Soient $X$ et $Y$ deux variables aléatoires. Alors \begin{eqnarray*} H(X,Y)=H(X)+H(Y|X). \end{eqnarray*} \end{prop} \begin{pf} \begin{eqnarray*} H(Y|X)&=&-\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_X (x)})\\ &=&-\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log_2 (p_{(X,Y)}(x,y))+\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log_2 (p_X (x))\\ &=&H(X,Y)+\sum_{x\in E_X}p_X (x)\log_2 (p_X (x))\\ &=&H(X,Y)-H(X). \end{eqnarray*} \end{pf} \finducours1 \sugg41 \begin{rem} En général, $H(Y|X)\not=H(X|Y)$. \end{rem} Car $H(X,Y)=H(Y,X)$ et $H(X)\not=H(Y)$ en général. \medskip Voici une version conditionnelle de la Proposition \ref{entrcond}. \begin{cor}\label{entrcondcond} Soient $X$, $Y$ et $Z$ trois variables aléatoires. Alors \begin{eqnarray*} H(X,Y|Z)=H(X|Z)+H(Y|X,Z). \end{eqnarray*} \end{cor} \begin{pf} \begin{eqnarray*} H(X,Y|Z)&=&H(X,Y,Z)-H(Z)\\ &=&H(X,Y,Z)-H(X,Z)+H(X,Z)-H(Z)\\ &=&H(Y|X,Z)+H(X|Z). \end{eqnarray*} \end{pf} En utilisant de façon répétée la Proposition \ref{entrcond}, on obtient \begin{cor}\label{chain} Soient $(X_1 ,\ldots,X_n)$ des variables aléatoires. Alors \begin{eqnarray*} H(X_1 ,\ldots,X_n)=H(X_1)+\sum_{i=2}^{n}H(X_i |X_{i-1},\ldots,X_{1}). \end{eqnarray*} \end{cor} \begin{pf} \begin{eqnarray*} H(X_1 ,X_2)&=&H(X_1)+H(X_2 |X_1),\\ H(X_1 ,X_2 ,X_3)&=&H(X_1 ,X_2)+H(X_3 |(X_1 ,X_2))\\ &=&H(X_1)+H(X_2 |X_1)+H(X_3 |X_1 ,X_2)\\ \end{eqnarray*} etc... \end{pf} \subsection{Information mutuelle et entropie conditionnelle} \begin{prop}\label{infmut} Soient $X$ et $Y$ deux variables aléatoires. Alors \begin{eqnarray*} I(X;Y)=H(X)-H(X|Y). \end{eqnarray*} \end{prop} Interprétation : $I(X;Y)$ mesure la diminution de l'incertitude contenue dans $X$ lorsqu'on apprend $Y$. \begin{pf} \begin{eqnarray*} I(X;Y) &=&\sum_{(x,y)\in E_X \times E_Y}p_{(X,Y)}(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_X (x)p_Y (y)})\\ &=&\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_Y (y)})-\sum_{(x,y)\in E_X \times E_Y}p_{(X,Y)}(x,y)\log_2 (p_X (x))\\ &=&-H(X|Y)-\sum_{x\in E_X}p_{X}(x)\log_2 (p_X (x))\\ &=&-H(X|Y)+H(X). \end{eqnarray*} \end{pf} \begin{ex} $I(X;X)=H(X)$ \end{ex} En effet, $H(X|X)=0$. Informellement, en apprenant $X$, on sait tout sur $X$, donc l'incertitude passe de $H(X)$ à $0$, la diminution d'incertitude est $H(X)$. \begin{cor} $I(X;Y)=H(X)+H(Y)-H(X,Y)$. \end{cor} \begin{pf} Combinaison des propositions \ref{entrcond} et \ref{infmut}. \end{pf} \sugg41 \subsection{Conditionner diminue l'entropie} \begin{prop}\label{conddiminentr} Soient $X$ et $Y$ deux variables aléatoires. Alors $H(X|Y)\leq H(X)$, avec égalité si et seulement si $X$ et $Y$ sont indépendantes. \end{prop} \begin{pf} $0\leq I(X;Y)=H(X)-H(X|Y)$. \end{pf} Interprétation : conditionnellement à $Y$, l'incertitude sur $X$ diminue toujours, et diminue strictement sauf si $Y$ est independante de $X$. Attention, c'est seulement vrai en moyenne : pour une valeur particulière $y$, $H(X|Y=y)$ peut être plus grand que $H(X)$ (certaines informations supplémentaires peuvent ajouter à la confusion, alors que d'autres renseignent sur $X$). Voir un exemple en Exercice 5, TD1. \sugg51 \begin{cor} Soient $X$ et $Y$ deux variables aléatoires. Alors $H(X,Y)\leq H(X)+H(Y)$, avec égalité si et seulement si $X$ et $Y$ sont indépendantes. \end{cor} \begin{pf} $H(X,Y)=H(X)+H(Y|X)\leq H(X)+H(Y)$. \end{pf} \subsection{Information mutuelle conditionnelle} On va voir que le principe ``conditionner diminue l'entropie'' a une portée plus générale. Il s'applique aussi à l'entropie conditionnelle (Corollaire \ref{condcond}). Pour le montrer, on a recours à une notion supplémentaire, celle d'information mutuelle conditionnelle. \begin{defi} Soient $X$, $Y$ et $Z$ des variables aléatoires. L'{\em information mutuelle conditionnelle} de $X$ et $Y$ sachant $Z$ est la moyenne, pondérée par la loi $p_Z$ de $Z$, des informations mutuelles des variables conditionnées $X|Z=z$ et $Y|Z=z$, \begin{eqnarray*} I(X;Y|Z)=\sum_{z\in E_Z}p_Z (z)I(X|Z=z;Y|Z=z). \end{eqnarray*} Autre expression : \begin{eqnarray*} I(X;Y|Z)=\sum_{x,y,z} p_{(X,Y,Z)}(x,y,z)\log_2 \frac{\frac{p_{(X,Y,Z)}(x,y,z)}{p_Z (z)}}{\frac{p_{(X,Z)}(x,z)}{p_Z (z)}\frac{p_{(Y,Z)}(y,z)}{p_Z (z)}}. \end{eqnarray*} \end{defi} Comme c'est une moyenne d'informations mutuelles, $I(X;Y|Z)\geq 0$. Comme dans l'information mutuelle, $X$ et $Y$ jouent des rôles symétriques : $I(X;Y|Z)=I(Y;X|Z)$. \medskip Il y a une version conditionnelle de la formule $I(X;Y)=H(X)-H(X|Y)$ (Proposition \ref{infmut}) : \begin{prop}\label{infmutcond} Soient $X$, $Y$ et $Z$ des variables aléatoires. Alors \begin{eqnarray*} I(X;Y|Z)=H(X|Z)-H(X|Y,Z). \end{eqnarray*} \end{prop} \begin{pf} Pour tout $z\in E_Z$, $I(X|Z=z;Y|Z=z)=H(X|Z=z)-H((X|Z=z)|(Y|Z=z))$, d'où \begin{eqnarray*} I(X;Y|Z)&=&\sum_{z\in E_Z}p_Z (z)I(X|Z=z;Y|Z=z)\\ &=&\sum_{z\in E_Z}p_Z (z)H(X|Z=z)-\sum_{z\in E_Z}p_Z (z)H((X|Z=z)|(Y|Z=z))\\ &=&H(X|Z)-\sum_{(y,z)\in E_Y \times E_Z}p_Z (z)p_{Y|Z=z}(y)H((X|Z=z)|(Y|Z=z)=y)\\ &=&H(X|Z)-\sum_{(y,z)\in E_Y \times E_Z}p_{(Y,Z)} (y,z)H(X|Y=y,Z=z)\\ &=&H(X|Z)-H(X|Y,Z). \end{eqnarray*} Pour calculer $H((X|Z = z)|(Y |Z = z) = y)$, on a calculé la loi conditionnelle de $X|Y=y$ sous la probabilité conditionnelle sachant $Z=z$, notée $\P_z$, \begin{eqnarray*} \P_{(X|Z = z)|(Y |Z = z) = y}(x) &=&(\P_z)_{X|Y=y}(x)\\ &=&\frac{\P_z (X=x,Y=y)}{\P_z (Y)}\\ &=&\frac{\P(X=x,Y=y|Z=z)}{\P(Y|Z=z)}\\ &=&\frac{\P_{(X,Y,Z)}(x,y,z)}{\P_{(Y,Z)}(y,z)}\\ &=&\P_{X|(Y=y,Z=z)}(x). \end{eqnarray*} %On se rappelle que %\begin{eqnarray*}-H(X|Y,Z)&=&-\sum_{y,z}p_{(Y,Z)}(y,z)H(X|Y=y,\,Z=z)\\ %&=&\sum_{y,z}p_{(Y,Z)}(y,z)\sum_{x}\frac{p_{(X,Y,Z}(x,y,z)}{p_{(Y,Z)}(y,z)}\log_2 \frac{p_{(X,Y,Z)}(y,z)}{p_{(Y,Z)}(y,z)}\\&=&\sum_{x,y,z}p_{(X,Y,Z)}(x,y,z)\log_2 \frac{p_{(X,Y,Z)}(y,z)}{p_{(Y,Z)}(y,z)},\end{eqnarray*} %et que %\begin{eqnarray*}H(X|Z)&=&\sum_{z}p_Z (z)H(X|Z=z)=-\sum_{x,z}p_{(X,Z)}(x,z)\log_2 \frac{p_{(X,Z)(x,z)}}{p_Z (z)}\\&=&-\sum_{x,y,z}p_{(X,Y,Z)}(x,y,z)\log_2 \frac{p_{(X,Z)(x,z)}}{p_Z (z)},\end{eqnarray*} %d'où, en additionnant, %\begin{eqnarray*}H(X|Z)-H(X|Y,Z)&=&\sum_{x,y,z}p_{(X,Y,Z)}(x,y,z)\log_2 \frac{\frac{p_{(X,Y,Z)}(y,z)}{p_{(Y,Z)}(y,z)}}{\frac{p_{(X,Z)(x,z)}}{p_Z (z)}}\\&=&\sum_{x,y,z} p_{(X,Y,Z)}(x,y,z)\log_2 \frac{\frac{p_{(X,Y,Z)}(x,y,z)}{p_Z (z)}}{\frac{p_{(X,Z)}(x,z)}{p_Z (z)}\frac{p_{(Y,Z)}(y,z)}{p_Z (z)}}\\&=&I(X;Y|Z).\end{eqnarray*} \end{pf} \begin{cor}\label{condcond} Soient $X$, $Y$ et $Z$ des variables aléatoires. Alors $H(X|Y,Z)\leq H(X|Y)$. \end{cor} De même, avec la Proposition \ref{entrcondcond}, \begin{cor} Soient $X$, $Y$ et $Z$ des variables aléatoires. Alors $H(X,Y|Z)\leq H(X|Z)+H(Y|Z)$. \end{cor} (Cela peut aussi se montrer directement : pour tout $z$, $H(X,Y|Z=z)\leq H(X|Z=z)+H(Y|Z=z)$, donc c'est vrai en moyenne). \medskip Enfin, l'information mutuelle satisfait une règle d'addition analogue à la Proposition \ref{entrcond} et au Corollaire \ref{chain}. \begin{prop}\label{infmutchain} Soient $X$, $Y$, $Z$ des variables aléatoires. Alors \begin{eqnarray*} I(X,Y;Z)=I(X;Z)+I(Y;Z|X),\quad I(X;Y,Z)=I(X;Z)+I(X;Y|Z). \end{eqnarray*} Plus généralement, soient $X_1 ,\ldots,X_n$ et $Z$ des variables aléatoires. Alors \begin{eqnarray*} I(X_1 ,\ldots,X_n ;Z)=I(X_1 ;Z)+\sum_{i=2}^{n}I(X_i ;Z|X_{i-1},\ldots,X_{1}). \end{eqnarray*} \end{prop} \begin{pf} On exprime l'information mutuelle en fonction d'entropies conditionnelles, on applique la Proposition \ref{entrcond} et on conclut avec la Proposition \ref{infmutcond}. \begin{eqnarray*} I(X,Y;Z)&=&H(X,Y)-H(X,Y|Z)\\ &=&H(X)+H(Y|X)-(H(X|Z)+H(Y|X,Z))\\ &=&I(X;Z)+I(Y;Z|X). \end{eqnarray*} La seconde formule s'obtient en échangeant $X$ et $Z$ et en observant que $I(Y;Z|X)=I(Z;Y|X)$. Quand il y a davantage de variables, le Corollaire \ref{chain} remplace la Proposition \ref{entrcond}. \begin{eqnarray*} I(X_1 ,\ldots,X_n ;Z) &=& H(X_1 ,\ldots,X_n)-H(X_1 ,\ldots,X_n |Z)\\ &=&H(X_1)+\sum_{i=2}^{n}H(X_i |X_{i-1},\ldots,X_{1})\\ &&-\left(H(X_1 |Z)+\sum_{i=2}^{n}H(X_i |X_{i-1},\ldots,X_{1},Z)\right)\\ &=&I(X_1 |Z)+\sum_{i=2}^{n}I(X_i ;Z|X_{i-1},\ldots,X_{1}). \end{eqnarray*} \end{pf} \sugg61 \sugg71 \subsection{Entropie relative conditionnelle} \begin{defi} Soient $E_X$, $E_Y$ des ensembles finis, soient $p$ et $q$ des distributions de probabilité sur $E_X \times E_Y$. L'{\em entropie relative conditionnelle} $D(p_{Y|X}||q_{Y|X})$ est la moyenne selon la marginale $p_X$ des entropies relatives $D(p_{Y|X=x}||q_{Y|X=x})$, i.e. \begin{eqnarray*} D(p_{Y|X}||q_{Y|X})=\sum_{x\in E_X}p_X (x)D(p_{Y|X=x}||q_{Y|X=x}). \end{eqnarray*} \end{defi} Remarquer que $D(p_{Y|X}||q_{Y|X})$ est une moyenne de quantités positives ou nulles, donc $D(p_{Y|X}||q_{Y|X})\geq 0$. Autres expressions : \begin{eqnarray*} D(p_{Y|X}||q_{Y|X})&=&\sum_{x\in E_X}p_X (x)\sum_{y\in E_Y}p_{Y|X=x}(y)\log\frac{p_{Y|X=x}(y)}{q_{Y|X=x}(y)}\\ &=&\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log\frac{\frac{p(x,y)}{\sum_{z}p(x,z)}}{\frac{q(x,y)}{\sum_{z}q(x,z)}}. \end{eqnarray*} \begin{prop}\label{chainD} Soient $E_X$, $E_Y$ des ensembles finis, soient $p$ et $q$ des distributions de probabilité sur $E_X \times E_Y$. On peut exprimer l'entropie relative $p$ et $q$ comme suit. \begin{eqnarray*} D(p||q)=D(p_X ||q_X)+D(p_{Y|X}||q_{Y|X}). \end{eqnarray*} \end{prop} \begin{pf} \begin{eqnarray*} D(p_{Y|X}||q_{Y|X})&=&\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log\frac{p(x,y)}{q(x,y)}+\sum_{(x,y)\in E_X \times E_Y}p(x,y)\log\frac{\sum_{z}q(x,z)}{\sum_{z}p(x,z)}\\ &=&D(p||q)-D(p_X ||q_X). \end{eqnarray*} \end{pf} \begin{rem} En particulier, $D(p||q)\geq D(p_{Y|X}||q_{Y|X})$, encore une manifestation du principe selon lequel conditionner diminue l'entropie. \end{rem} On utilisera l'entropie relative conditionnelle dans la preuve du Théorème \ref{Ddecroit}. \subsection{Convexité de l'entropie relative} \begin{theo}\label{convD} Soit $E$ un ensemble fini. L'entropie relative est une fonction convexe sur l'ensemble $\mathcal{P}(E)\times \mathcal{P}(E)$, où $\mathcal{P}(E)$ est l'ensemble des distributions de probabilité sur $E$. \end{theo} Remarquer que $\mathcal{P}(E)$ est un polyèdre convexe de $\R^{|E|}$, et $\mathcal{P}(E)\times \mathcal{P}(E)$ un polyèdre convexe de $\R^{2|E|}$. On peut donc parler de convexité d'une fonction définie sur $\mathcal{P}(E)\times \mathcal{P}(E)$. \finducours2 \begin{pf} Soient $p_1$, $p_2$, $q_1$ et $q_2$ des distributions de probabilité sur $E$. Soit $t\in]0,1[$. Soit $x\in E$. On écrit \begin{eqnarray*} \frac{(1-t)p_1 (x)+tp_2(x)}{(1-t)q_1 (x)+tq_2(x)}=(1-\lambda)a+\lambda b,\quad\textrm{où }a=\frac{p_1 (x)}{q_1 (x)},~b=\frac{p_2 (x)}{q_2 (x)},~\lambda=\frac{tq_2 (x)}{(1-t)q_1 (x)+tq_2(x)}. \end{eqnarray*} Comme $x\mapsto f(x)=x\log_2 x$ est convexe, \begin{eqnarray*} f(\frac{(1-t)p_1 (x)+tp_2(x)}{(1-t)q_1 (x)+tq_2(x)}) &=&f((1-\lambda)a+\lambda b)\\ &\leq& (1-\lambda)f(a)+\lambda f(b)\\ &=&\frac{(1-t)q_1 (x)}{(1-t)q_1 (x)+tq_2(x)}f(\frac{p_1 (x)}{q_1 (x)})+\frac{tq_2 (x)}{(1-t)q_1 (x)+tq_2(x)}f(\frac{p_2 (x)}{q_2 (x)})\\ &=&\frac{(1-t)p_1 (x)}{(1-t)q_1 (x)+tq_2(x)}\log_2 (\frac{p_1 (x)}{q_1 (x)})+\frac{tp_2 (x)}{(1-t)q_1 (x)+tq_2(x)}\log_2(\frac{p_2 (x)}{q_2 (x)}), \end{eqnarray*} d'où \begin{eqnarray*} ((1-t)p_1 (x)+tp_2(x))\log_2 (\frac{(1-t)p_1 (x)+tp_2(x)}{(1-t)q_1 (x)+tq_2(x)})\leq (1-t)p_1 (x)\log_2 (\frac{p_1 (x)}{q_1 (x)})+tp_2 (x)\log_2(\frac{p_2 (x)}{q_2 (x)}). \end{eqnarray*} En sommant sur $x\in E$, il vient \begin{eqnarray*} D((1-t)p_1 +tp_2 || (1-t)q_1 +tpq_2 )\leq (1-t)D(p_1|| q_1)+tD(p_2 || q_2). \end{eqnarray*} \end{pf} \begin{cor} L'entropie est une fonction concave sur l'ensemble des distributions de probabilité sur $E$. Elle atteint son maximum à la distribution uniforme. \end{cor} \begin{pf} Soit $u:x\mapsto \frac{1}{|E|}$ la distribution uniforme sur $E$. Alors pour toute distribution de probabilité $p$, \begin{eqnarray*} D(p||u)=\sum_{x\in E}p(x)\log_2 (\frac{p(x)}{u(x)})=\log_2 (|E|)-H(p), \end{eqnarray*} est une fonction convexe de $p$, positive ou nulle, et nulle exactement en $u$. \end{pf} \begin{ex}\label{exconvD} L'entropie de la distribution de Bernoulli $q\mapsto H(\mathcal{B}(q))$ est une fonction concave sur $[0,1]$, elle atteint son maximum en $\frac{1}{2}$. \end{ex} \sugg81 \subsection{A retenir} \begin{itemize} \item Les notions absolues : entropie, entropie relative, information mutuelle. \item Leurs versions conditionnelles : entropie conditionnelle, entropie relative conditionnelle, information mutuelle conditionnelle. Les formules d'addition correspondantes. \item Le lien entre information mutuelle et entropie conditionnelle (et sa version conditionnelle). \item Les inégalités : toutes les entropies/informations sont positives ou nulles, conditionner diminue l'entropie, concavité de l'entropie (resp. convexité de l'entropie relative) comme fonction de la distribution (resp. de deux distributions). \end{itemize} Il s'agit d'un chapitre théorique, avec plein de définitions et d'énoncés qui seront utilisés ensuite. \section{Compression de données} \subsection{Motivation} Il est notoire que l'anglais est plus concis que le français : la traduction anglaise d'un texte français est presque toujours nettement plus courte que le texte original. Jusqu'où peut on aller dans cette direction ? Peut on fabriquer une langue artificielle qui soit encore plus économe ? \medskip Ignorons la grammaire pour ne travailler que sur le vocabulaire. La langue artificielle - appelons la le codage - est définie par un dictionnaire : à chaque mot français $x$ correspond son équivalent $C(x)$, une chaîne de caractères pris dans l'alphabet latin $\mathcal{D}$, qui possède $D=26$ lettres. On note $\ell(x)$ la longueur de $C(x)$. Etant donné un texte français $T$, i.e. une suite de mots, la longueur totale de sa traduction est $\sum_{x\in E}N(x,T)\ell(x)$ où $E$ est l'ensemble des mots français et $N(x,T)$ est le nombre d'apparitions du mot $x$ dans le texte $T$. La performance du codage est \begin{eqnarray*} \sum_{x\in E}\frac{N(x,T)}{N(T)}\ell(x)=\sum_{x\in E}p_T (x)\ell(x), \end{eqnarray*} où $N(T)$ est le nombre total de mots dans $T$, et $p_T (x)$ la fréquence d'apparition du mot $x$ dans $T$. Pour de grands textes, l'expérience montre que les fréquences $p_T$ convergent vers une distribution de probabilité sur $E$, la fréquence d'utilisation de chaque mot en français. \subsection{Modélisation} La langue française est donc modélisée par une variable aléatoire $X$ à valeurs dans un ensemble fini $E$, le codage par une application $C:E\to \mathcal{D}^*$ (ensemble des suites finies de lettres prises dans $\mathcal{D}$), et la performance du codage par l'espérance $\E(\ell(X))$. Le codage des textes est l'application $C^* :E^* \to\mathcal{D}^*$ qui envoie le texte (i.e. la suite de mots) $(x_1 ,x_2 ,\ldots,x_k)$ sur sa traduction $C(x_1)C(x_2)\cdots C(x_k)$. Par souci d'économie, les mots codés sont concaténés sans séparateurs (pas d'espace ni de ponctuation). \begin{defi} Un codage $C$ est {\em uniquement décodable} si l'application $C^* :E^* \to\mathcal{D}^*$ est injective. \end{defi} C'est la moindre des choses. \begin{ques}[Problème du codage de source] Quelle est la meilleure performance $\E(\ell(X))$ accomplie par les codages uniquement décodables ? \end{ques} Ce problème s'intitule problème du {\em codage de source}, par opposition au codage des transmissions, qu'on étudiera plus loin. On voit la variable aléatoire $X$ comme une source de mots. Dans notre exemple initial, la source, c'est la littérature française. \sugg12 \subsection{Inégalité de Kraft} Dans un codage uniquement décodable, les mots codés ne peuvent pas tous être courts. Le théorème suivant donne une borne inférieure optimale sur les longueurs. \begin{theo}[L. Kraft (1949), B. McMillan (1953)]\label{kraft} Soit $C:E\to\mathcal{D}^*$ un codage uniquement décodable dans un alphabet à $D=|\mathcal{D}|$ lettres. Alors \begin{eqnarray*} \sum_{x\in E}D^{-\ell(x)}\leq 1. \end{eqnarray*} Inversement, toute fonction $\ell:E\to\N\setminus\{0\}$ qui satisfait l'inégalité précédente est la fonction longueur d'un codage uniquement décodable. \end{theo} \begin{pf} Soit $k\geq 1$ un entier. On développe \begin{eqnarray*} (\sum_{x\in E} D^{-\ell(x)})^k &=&\sum_{(x_1 ,\ldots,x_k)\in E^k}D^{-\sum_i \ell(x_i)}\\ &=&\sum_{T\in E^k}D^{-|C^* (T)|}. \end{eqnarray*} Ici $E^k$ désigne l'ensemble des textes à $k$ mots et $|C^* (T)|$ est la longueur de la traduction de $T$. Soit \begin{eqnarray*} L=\max_{x\in E}\ell(x) \end{eqnarray*} la longueur maximale d'un mot codé. On note $N(m)$ le nombre de textes à $k$ mots codés par des suites de $m$ lettres. Alors \begin{eqnarray*} \sum_{T\in E^k}D^{-|C^* (T)|}=\sum_{m=1}^{kL}N(m)D^{-m} \end{eqnarray*} Comme $C^*$ est injective, et comme il y a seulement $D^m$ suites de $m$ lettres distinctes, $N(m)\leq D^m$. Il vient \begin{eqnarray*} (\sum_{x\in E} D^{-\ell(x)})^k \leq\sum_{m=1}^{kL}D^m D^{-m}=kL, \end{eqnarray*} d'où $\sum_{x\in E} D^{-\ell(x)}\leq (kL)^{1/k}$ pour tout $k\geq 1$. En faisant tendre $k$ vers $+\infty$, on trouve que $\sum_{x\in E} D^{-\ell(x)}\leq 1$. Réciproquement, soit $\ell:E\to\N\setminus\{0\}$ une fonction qui satisfait l'inégalité $\sum_{x\in E} D^{-\ell(x)}\leq 1$. On ordonne les éléments de $E=\{x_1 ,x_2 ,\ldots\}$ de sorte que $\ell$ soit croissante. On ordonne $\mathcal{D}$ aussi. L'ensemble $\mathcal{A}_0 =\mathcal{D}^*$ est ordonné par l'ordre lexicographique. On construit par récurrence des éléments $C(x_1),C(x_2),\ldots$ et des sous-ensembles décroissants $\mathcal{A}_0 \supset \mathcal{A}_1 \supset \mathcal{A}_2 \supset\cdots$ comme suit. Soit $C(x_1)$ le premier élément de $\mathcal{D}^*$ (dans l'ordre lexicographique) de longueur $\ell(x_1)$. Soit $\mathcal{A}_1 =\mathcal{A}_0$ privé de toutes les suites qui commencent par $C(x_1)$. Soit $C(x_2)$ le premier élément de $\mathcal{A}_1$ (dans l'ordre lexicographique) de longueur $\ell(x_2)$. Soit $\mathcal{A}_2 =\mathcal{A}_1$ privé de toutes les suites qui commencent par $C(x_2)$, etc.... La condition $\sum_{i}D^{-\ell(x_i)}\leq 1$ garantit qu'à chaque étape, $\mathcal{A}_i$ possède bien des éléments de longueur $\ell(x_{i})$. En effet, soit de nouveau $L=\max_{x\in E}\ell(x)$. Soit $N(j)$ le nombre de suites de longueur $L$ qui n'appartiennent pas à $\mathcal{A}_j$. Par construction, $N(0)=0$. En passant de $\mathcal{A}_{j-1}$ à $\mathcal{A}_{j}$, on supprime toutes les suites de longueur $L$ commençant par $C(x_j)$, il y en a exactement $D^{L-\ell(x_j)}$. Par conséquent, \begin{eqnarray*} N(j)=N(j-1)+D^{L-\ell(x_i)},\quad \textrm{d'où}\quad N(j)=\sum_{i=1}^{j}D^{L-\ell(x_i)}\leq D^L, \end{eqnarray*} avec inégalité stricte tant que $E$ n'est pas épuisé. Il y a donc des éléments de longueur $L$ (et donc, de toute longueur $\leq L$) dans $\mathcal{A}_{j-1}$ jusqu'à la dernière étape de la construction. Il est commode de visualiser chaque ensemble ordonné $\mathcal{A}_j$ sous la forme d'un arbre enraciné, sous-arbre de l'arbre associé à $\mathcal{D}^*$. Ci-dessous, l'arbre final lorsque $D=2$, $E=\{x_1 ,x_2 ,x_3\}$, $\ell(x_1)=\ell(x_2)=2$, $\ell(x_3)=3$ (les flèches désignent les branches de l'arbre qui se poursuivent sans changement). Le codage est $C(x_1)=00$, $C(x_2)=01$, $C(x_3)=011$. \medskip \def\GraphLegend{Arbre schématisant la construction du codage} \figinit{cm} \figpt0:(\Xori,\Yori) \figpt1:(2,1) \figpt2:(2.5,2) \figpt3:(1.5,2) \figpt4:(-2,1) \figpt5:(-1.5,2) \figpt6:(-2.5,2) \figpt7:(1.25,3) \figpt8:(1.75,3) \figpt9:(2.625,2.5) \figpt{10}:(2.375,2.5) \figpt{11}:(1.875,3.5) \figpt{12}:(1.625,3.5) % 2. Creation of the graphical file \figdrawbegin{} \figdrawline [0,1] \figdrawline [1,2] \figdrawline [1,3] \figdrawline [0,4] \figdrawline [4,5] \figdrawline [4,6] \figdrawline [3,7] \figdrawline [3,8] \figdrawarrow [2,9] \figdrawarrow [2,10] \figdrawarrow [8,11] \figdrawarrow [8,12] \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figwrites 0:$\emptyset$(5pt) \figwritee 1:$1$(5pt) \figwritee 2:$11$(5pt) \figwritew 3:$10$(5pt) \figwritew 4:$0$(5pt) \figwritee 5:$01$(5pt) \figwritew 6:$00$(5pt) \figwritew 7:$011$(5pt) \figwritee 8:$010$(5pt) } \centerline{\box\figBoxA} \medskip Par construction, aucun des $C(x)$, $x\in E$, n'est un préfixe d'un autre $C(x')$. Par conséquent, une concaténation $w=C(x_{i_1})C(x_{i_2})\cdots C(x_{i_k})$ se décode aisément comme suit. On lit les lettres dans l'ordre jusqu'à ce qu'on reconnaisse un élément de $C(E)$. Il y a exactement un élément $x$ de $E$ tel que $C(x)$ commence par les mêmes lettres que $w$, c'est $x_{i_1}$, donc $w$ est la traduction d'un mot commençant par $x_{i_1}$. On recommence avec $w_1 =C(x_{i_2})\cdots C(x_{i_k})$, etc... Cela prouve que $C^* :E^* \to\mathcal{D}^*$ est injective. \end{pf} \subsection{Théorème du codage de source} L'inégalité de Kraft ramène la question de minimiser la longueur moyenne d'un codage uniquement décodable à une simple inégalité sur les fonctions sur $E$. La réponse fait intervenir l'entropie. \begin{theo}[C. Shannon (1948)]\label{cod} Soit $X$ une variable aléatoire à valeurs dans un ensemble fini $E$. Soit $C:E\to\mathcal{D}^*$ un codage uniquement décodable dans un alphabet à $D=|\mathcal{D}|$ lettres. Soit $\ell:E\to\N$ la longueur des mots-codes. Alors la longueur moyenne satisfait \begin{eqnarray*} \E(\ell(X))\geq \frac{H(X)}{\log_2 (D)}. \end{eqnarray*} Cette borne est atteinte si et seulement si les valeurs $p(x)$, $x\in E$, de la loi de $X$ sont des puissances de $D$. En général, il existe un code $C$ qui réalise \begin{eqnarray*} \frac{H(X)}{\log_2 (D)}\leq\E(\ell(X))<\frac{H(X)}{\log_2 (D)}+1. \end{eqnarray*} Autrement dit, si $L_{ud}(X)$ désigne la borne inférieure des longueurs moyennes des codages uniquement décodables, alors \begin{eqnarray*} \frac{H(X)}{\log_2 (D)}\leq L_{ud}(X)<\frac{H(X)}{\log_2 (D)}+1. \end{eqnarray*} \end{theo} \begin{pf} Soit $c=\sum_{x\in E}D^{-\ell(x)}$. On définit une distribution de probabilité $q$ sur $E$ par $q(x)=\frac{1}{c}D^{-\ell(x)}$. On calcule \begin{eqnarray*} D(p||q)&=&\sum_{x\in E}p(x)\log_2 (\frac{p(x)}{q(x)})\\ &=& -H(X)+\log_2 (c)+\log_2 (D)\E(\ell(X)). \end{eqnarray*} Comme $D(p||q)\geq 0$ (Théorème \ref{D>0}) et $c\leq1$ (Théorème \ref{kraft}), il vient $-H(X)+\log_2 (D)\E(\ell(X))\geq 0$. L'égalité entraîne que $D(p||q)=0$ et $c=1$, et donc que $p=q$ est à valeurs dans les puissances de $D$. Réciproquement, si $p$ est à valeurs dans les puissances de $D$, on pose $\ell=-\log_2 (p)/\log_2 (D)$. C'est une fonction à valeurs entières qui satisfait l'inégalité de Kraft. D'après le Théorème \ref{kraft}, il existe un codage $C$ uniquement décodable dont les longueurs sont données par $\ell$, il réalise la performance $\E(\ell(X))=\frac{H(X)}{\log_2 (D)}$. En général, on pose $\ell=\lceil -\log_2 (p)/\log_2 (D)\rceil$, fonction à valeurs entières qui satisfait l'inégalité de Kraft, donc réalisable par un codage uniquement décodable. On calcule \begin{eqnarray*} \E(\ell(X))&=&\sum_{x\in E}p(x)\lceil -\frac{\log_2 (p)}{\log_2 (D)}\rceil\\ &<&\sum_{x\in E}p(x)(-\frac{\log_2 (p)}{\log_2 (D)} +1)\\ &=&\frac{H(X)}{\log_2 (D)}+1. \end{eqnarray*} \end{pf} Cela confirme l'idée que l'entropie mesure la quantité d'information nécessaire pour décrire une variable aléatoire $X$ : c'est la borne inférieure du nombre de bits nécessaires en moyenne pour coder $X$. \begin{rem} Supposons qu'on est mal informé sur la loi de $X$. On n'en connait qu'une approximation $q$. Le codage qui semble presque optimal a pour longueurs de mots $\ell(x)=\lceil -\frac{\log_2 (q)}{\log_2 (D)}\rceil$, donc pour longueur moyenne \begin{eqnarray*} \frac{H(X)+D(p||q)}{\log_2 (D)}\leq\E(\ell(X))<\frac{H(X)+D(p||q)}{\log_2 (D)}+1. \end{eqnarray*} \end{rem} Autrement dit, l'entropie relative $D(p||q)$ mesure l'augmentation de la complexité de $X$ due au fait qu'on a une information erronnée sur sa loi. \begin{rem} Un code non uniquement décodable ne satisfait pas nécessairement $\E(\ell(X))\geq H(X)$. \end{rem} \finducours3 \sugg22 \sugg32 \subsection{Construction de codes optimaux} Le Théorème \ref{cod} ne fournit un codage optimal que dans le cas où la distribution de probabilité donnée est à valeurs dans les puissances de la taille $D$ de l'alphabet. Il existe un algorithme, dû à D. Huffman, qui produit pour toute distribution de probabilité un codage optimal, voir le livre de Cover et Thomas, chapitre 5, pages 118 à 127. On le décrit ici uniquement pour $D=2$. \subsubsection{Jeu dans la cour d'un collège} On commence par relier ce cas particulier du problème du codage optimal au \emph{jeu des 10 questions} : "Choisis un nombre à trois chiffres, mémorise-le sans le dire. Je vais te poser une série de questions auxquelles tu répondras par oui ou par non. En moins de $10$ questions, je peux deviner de quel nombre il s'agit !" Ce qui nous intéresse, ce n'est pas de déterminer le nombre de questions nécessaire dans le pire des cas, mais d'optimiser le nombre de questions en moyenne, lorsque le nombre est tiré suivant une distribution de probabilité connue. Autrement dit, on se donne une variable aléatoire $X$ à valeurs dans un ensemble fini $E$. Une stratégie est un procédé déterministe qui, à une suite de réponses $s\in\{0,1\}^*$ associe une fonction $f_s :X\to\{0,1\}$. Si $s$ est de longueur $i-1$, $f_s$ représente la question que je pose à l'étape $i$ au vu de la suite de réponses $s$. Lorsque $X=x$, le déroulement du jeu produit des suites de réponses $s_1 =f_\emptyset (x)$, $s_2 =s_1 f_{s_1}(x)$,..., $s_i=s_{i-1}f_{s_{i-1}}$,...,$s_Q$, $Q=Q(x)$. Le jeu s'arrête lorsque la suite de réponses $s_Q (x)$ détermine uniquement $x$, i.e. lorsque pour tout $y\in E$, $s_Q (y)=(x)\Rightarrow y=x$. Autrement dit, $Q(x)$ est la durée du jeu. Il s'agit de trouver la stratégie qui minimise la durée moyenne du jeu, i.e. l'espérance de $Q(X)$. \begin{ques} Quel est le nombre minimum de questions nécessaire, en moyenne, pour déterminer $X$ ? \end{ques} On va utiliser une représentation graphique commode, sous forme d'arbre binaire. Il y a une terminologie pour ces arbres. \begin{defi} Un \emph{arbre binaire} est un arbre muni d'un sommet particulier, la \emph{racine}. Les arêtes sont orientées dans la direction opposée à la racine. Chaque sommet autre que la racine reçoit une arête, qui provient de son \emph{ascendant}. Chaque sommet a ou bien 2 \emph{descendants} (on parle de \emph{noeud}), ou bien 0 (on parle de \emph{feuille}). La \emph{profondeur} d'un sommet est le nombre d'arêtes qui le séparent de la racine, on note cette fonction $\ell$ (ou $\ell_{A}$ quand il faut spécifier qu'il s'agit de l'arbre $A$). On note $\partial A$ l'ensemble des feuilles d'un arbre binaire $A$. \end{defi} \begin{prop}\label{jeu} Etant donnée une distribution de probabilité $p$ sur un ensemble fini $E$, les trois problèmes suivants sont équivalents. \begin{enumerate} \item Construire une stratégie au jeu des questions qui minimise la durée moyenne du jeu. \item Construire un arbre binaire $A$ et une bijection de $E$ sur l'ensemble des feuilles de $A$, qui minimise la profondeur moyenne des feuilles. \item Construire un codage de longueur moyenne minimale parmi ceux qui ont la propriété suivante : aucun mot-code n'est un préfixe d'un autre mot-code. \end{enumerate} \end{prop} \begin{pf} La suite des réponses aux questions jusqu'à terminaison associe une suite $C(x)\in\{0,1\}^*$ à chaque élément de $E$. L'application $C$ est un codage sans préfixe. En effet, supposons qu'il existe $x\not=y\in E$ tels que $C(x)$ est un préfixe de $C(y)$. Les tirages $x$ et $y$ donnent la même suite de réponses de longueur $Q(x)$. Si le jeu s'arrête là dans le cas du tirage $x$, c'est que cette suite détermine uniquement $x$. En particulier, $y=x$, contradiction. La fonction longueur $\ell$ du codage $C$ coïncide avec $Q$, donc la durée moyenne du jeu est égale à la longueur moyenne du codage. On peut représenter graphiquement $C$ par un arbre binaire : la racine a deux descendants numérotés $0$ et $1$, qui ont chacun deux descendants numérotés respectivement $00$ et $01$, $10$ et $11$, etc... On arrête la construction récursive de l'arbre dès que la suite de questions s'arrête, i.e. quand elle caractérise uniquement un élément de $E$. Les feuilles correspondent bijectivement aux éléments $x$ de $E$, elles héritent d'un poids $p(x)$. La profondeur de la feuille associée à $x$ est égale à la longueur $\ell(x)$ du mot-code $C(x)$, la profondeur moyenne est égale à la longueur moyenne du codage. Si un noeud ne possède qu'un seul descendant, on peut le supprimer en contractant l'unique arête qui en part. Cela retire une lettre aux mots-codes dont il était un préfixe, donc cela diminue strictement la longueur moyenne. Cela ne peut pas se produire pour un codage minimal. Les codages minimaux correspondent donc à des arbres binaires. Enfin, un arbre binaire fournit une stratégie pour le jeu des 10 questions. Une suite $s\in\{0,1\}^*$ amène à un noeud $n(s)$ de l'arbre. De ce noeud émanent deux sous-arbres $A_0$ et $A_1$. Soit $f_s$ la fonction qui vaut $1$ sur les feuilles de $A_1$, et $0$ sur toutes les autres feuilles. La réponse à cette question permet de de faire un pas de plus, dans $A_0$ ou $A_1$ suivant que la réponse est $0$ ou $1$. \medskip \def\GraphLegend{Stratégie associée à un arbre : sous arbres lorsque $s=1$} \figinit{cm} \def\Xori{0} \def\Yori{0} \figpt9:(\Xori,\Yori) \figpt8:(2,1) \figpt7:(-2,1) \figpt2:(-4,2) \figpt3:(-1,2) \figpt1:(4,2) \figset(color=0 0 1) \figpt6:(1,2) \figpt4:(0,3) \figpt5:(3,3) \figset(color=1 0 0) \figpt{10}:(3,1.5) % 2. Creation of the graphical file \figdrawbegin{} \figdrawline [9,7] \figdrawline [9,8] \figdrawline [7,2] \figdrawline [7,3] \figset(color=0 0 1) \figdrawline [8,6] \figdrawline [6,4] \figdrawline [6,5] \figset(color=1 0 0) \figdrawline [8,1] \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figwritew 2:$00$(5pt) \figwritee 3:$01$(5pt) \figwrites 7:$0$(5pt) \figwrites 8:$1$(5pt) \figwrites 9:$\emptyset$(5pt) \figset(color=0 0 1) \figwritew 4:$100$(5pt) \figwritee 5:$101$(5pt) \figwritew 6:$10$(5pt) \figwrites 6:$A_0$(10pt) \figset(color=1 0 0) \figwritee 1:$11$(5pt) \figwrites 10:$A_1$(5pt) } \centerline{\box\figBoxA} \medskip Muni de cette stratégie, le jeu s'arrête lorsqu'on atteint une feuille, marquée par un élément $x$ de $E$. Il permet d'identifier uniquement $x$. La durée du jeu en cas de tirage $x$ est égale à la profondeur de $x$, donc profondeur moyenne et durée moyenne du jeu sont égales. \end{pf} \subsubsection{Algorithme de D. Huffman} En entrée : un ensemble fini ordonné $E$ muni d'une distribution de probabilité $p$. En sortie : un arbre binaire $A$ et une bijection de $E$ sur $\partial A$. On construit une suite d'ensembles ordonnés $E=E_0 ,\ldots,E_{|E|-1}$ et de distributions de probabilité $p=p_0 ,\ldots,p_{|E|-1}$. L'algorithme est récursif. On répète l'opération suivante, qui fait diminuer $|E|$ d'une unité, jusqu'à ce que $E$ n'ait plus qu'un élément. Soient $x$ et $x'$ les éléments de $E$ dont les probabilités sont les plus basses (s'il y a plusieurs choix, on choisit les derniers dans l'ordre fixé sur $E$). On les fusionne, i.e. on leur donne un ascendant commun $y$ auquel on affecte la probabilité $p'(y)=p(x)+p(x')$. On pose $E'=E/(x \sim x')=(E\setminus\{x,x'\})\cup\{y\}$. \medskip \textbf{Exemple}. Soit $E=\{1,2,3,4,5\}$ muni de la distribution $(\frac{1}{4},\frac{1}{4},\frac{1}{5},\frac{3}{20},\frac{3}{20})$. \begin{itemize} \item Au premier tour, on fusionne 4 et 5 en un noeud baptisé 6, de probabilité $\frac{3}{20}+\frac{3}{20}=\frac{3}{10}$, d'où $E_1=\{1,2,3,6\}$. \item Au second tour, on fusionne 2 et 3 en un noeud baptisé 7, de probabilité $\frac{1}{5}+\frac{1}{4}=\frac{9}{20}$, d'où $E_2=\{1,6,7\}$. \item Au troisième tour, on fusionne 1 et 6 en un noeud baptisé 8, de probabilité $\frac{1}{4}+\frac{3}{10}=\frac{11}{20}$, d'où $E_3=\{7,8\}$. \item Au dernier tour, on fusionne 7 et 8 en un noeud baptisé 9, de probabilité $\frac{9}{20}+\frac{11}{20}=1$. \end{itemize} \medskip \def\GraphLegend{Arbre de Huffman} \figinit{cm} \def\Xori{0} \def\Yori{0} \figpt9:(\Xori,\Yori) \figpt8:(2,1) \figpt7:(-2,1) \figpt2:(-4,2) \figpt3:(-1,2) \figpt6:(1,2) \figpt1:(4,2) \figpt4:(0,3) \figpt5:(3,3) % 2. Creation of the graphical file \figdrawbegin{} \figdrawline [9,7] \figdrawline [9,8] \figdrawline [8,1] \figdrawline [8,6] \figdrawline [7,2] \figdrawline [7,3] \figdrawline [6,4] \figdrawline [6,5] \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figwritee 1:$1$(5pt) \figwritew 2:$2$(5pt) \figwritee 3:$3$(5pt) \figwritew 4:$4$(5pt) \figwritee 5:$5$(5pt) \figwrites 6:$6$(5pt) \figwrites 7:$7$(5pt) \figwrites 8:$8$(5pt) \figwrites 9:$9$(5pt) } \centerline{\box\figBoxA} \medskip \def\GraphLegend{Codage de Huffman} \figinit{cm} \def\Xori{0} \def\Yori{0} \figpt9:(\Xori,\Yori) \figpt8:(2,1) \figpt7:(-2,1) \figpt2:(-4,2) \figpt3:(-1,2) \figpt6:(1,2) \figpt1:(4,2) \figpt4:(0,3) \figpt5:(3,3) % 2. Creation of the graphical file \figdrawbegin{} \figdrawline [9,7] \figdrawline [9,8] \figdrawline [8,1] \figdrawline [8,6] \figdrawline [7,2] \figdrawline [7,3] \figdrawline [6,4] \figdrawline [6,5] \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figwritee 1:$11$(5pt) \figwritew 2:$00$(5pt) \figwritee 3:$01$(5pt) \figwritew 4:$100$(5pt) \figwritee 5:$101$(5pt) \figwrites 6:$10$(5pt) \figwrites 7:$0$(5pt) \figwrites 8:$1$(5pt) \figwrites 9:$\emptyset$(5pt) } \centerline{\box\figBoxA} \medskip Cela donne le codage suivant. \begin{center} \begin{tabular}{|l|ccccc|} \hline $i$ & 1&2&3&4&5\\ \hline $C(i)$ &11&00&01&100&101\\ \hline \end{tabular} \end{center} Le codage minimal n'est pas unique, loin de là. \begin{prop} Soit $E$ un ensemble fini muni d'une distribution de probabilité $p$. L'algorithme qui vient d'être décrit produit un arbre dont les feuilles sont numérotées par $E$, de profondeur moyenne minimale. \end{prop} \begin{pf} Par récurrence sur $|E|$, on montre que pour tout arbre $A$ et toute bijection $\phi:E\to \partial A$, la profondeur moyenne de $A$, notée $\E(\ell_A \circ\phi)$ est supérieure ou égale à celle de l'arbre $(A_0 ,\phi_0 :E\to\partial A_0)$ construit par l'algorithme. Initialisation. Lorsque $|E|=1$, il n'y a qu'un arbre possible, $A=A_0$ ont même profondeur moyenne. Supposons que l'algorithme construise un arbre optimal pour tous les ensembles $E$ à $n$ éléments. Soit $E$ un ensemble ordonné à $n+1$ éléments, muni d'une distribution de probabilité $p$. Soit $A$ un arbre et $\phi:E\to\partial A$ une bijection. Soit $(A_0 ,\phi_0 :E\to\partial A_0)$ l'arbre construit par l'algorithme. Opération préliminaire. Soit $\{a,a'\}$ une paire de feuilles de profondeur maximale dans $A$, ayant le même ascendant. Soit $\{x,x'\}$ la paire d'éléments de $E$ fusionnée au premier tour. En composant $\phi$ avec une permutation de $E$, remplaçons $\phi$ par $\tilde{\phi}=\phi\circ\sigma:E\to\partial A$, de sorte que $\tilde{\phi}(a)=x$ et $\tilde{\phi}(a')=x'$. La permutation $\sigma$ répartit différemment les probabilités sans changer les profondeurs. Comme $x$ et $x'$ sont de probabilités minimales et $a$, $a'$ de profondeurs maximales, on peut choisir $\sigma$ de sorte qu'elle n'augmente pas la longueur moyenne, $\E(\ell_A \circ\phi)\geq \E(\ell_A \circ\tilde{\phi})$. Supprimons les feuilles $a$ et $a'$. On obtient un arbre $A'$ et une bijection $\phi':E'\to\partial A'$ qu'il faut comparer à l'arbre $A_1$, muni de sa bijection évidente $\phi_1 :E'\to\partial A_1$, produit par l'algorithme. La profondeur moyenne satisfait \begin{eqnarray*} \E(\ell_{A'}\circ\phi')&=&\E(\ell_{A}\circ\tilde{\phi})-p'(y),\\ \E(\ell_{A_1}\circ\phi_1)&=&\E(\ell_{A_0}\circ\phi_0)-p'(y). \end{eqnarray*} Par l'hypothèse de récurrence, $\E(\ell_{A'}\circ\phi')\geq \E(\ell_{A_1} \circ\phi_1)$. Par conséquent, $\E(\ell_{A}\circ\tilde{\phi})\geq\E(\ell_{A_0} \circ\phi_0)$, et donc $\E(\ell_{A}\circ\phi)\geq\E(\ell_{A_0} \circ\phi_0)$. \end{pf} \sugg42 \finducours4 \begin{cor} Au jeu des 10 questions, la durée moyenne du jeu est au moins égale à l'entropie. \end{cor} \begin{pf} D'après la Proposition \ref{jeu}, la question se traduit en termes de codage sans préfixes. Ce codage est en particulier uniquement décodable (on s'en est servi dans la preuve du théorème de codage de source), donc d'après le théorème de codage de source, sa longueur moyenne satisfait $\E(\ell(X))\geq H(X)$. \end{pf} \begin{ex} Soit $X$ une variable qui suit une loi géométrique de paramètre $\frac{1}{2}$ (par exemple, le temps d'obtention de face au jeu de pile ou face). Alors il existe une stratégie dont la durée moyenne est $H(X)=2$ et on ne peut pas faire mieux. \end{ex} Voir l'Exercice 2 de la feuille 1, pour la stratégie de durée moyenne $2$. \sugg52 \sugg62 \subsection{A retenir} \begin{itemize} \item L'interprétation de l'entropie comme longueur moyenne minimale d'un codage d'une source (asymptotiquement). \item L'algorithme de Huffman. \end{itemize} Il s'agit d'un chapitre pratique, où on a utilisé les outils du chapitre précédent pour résoudre un problème concret. \section{Entropie des processus stationnaires} Dans ce chapitre, on cherche à établir le second principe de la thermodynamique. On étudie l'entropie de processus sensés modéliser des systèmes physiques. Il s'avère que leur entropie elle-même n'augmente pas, c'est l'entropie relative à la condition initiale qui augmente. On généralise ensuite la notion d'entropie aux processus aléatoires stationnaires. Pour un processus, c'est l'entropie ``par symbole''qui remplace l'entropie d'une variable isolée. Ce taux de croissance se calcule particulièrement bien dans le cas des chaînes de Markov stationnaires. \subsection{Chaînes de Markov} \begin{defi} Une {\em chaîne de Markov} est une suite $X_0 ,X_1 ,\ldots$ de variables aléatoires à valeurs dans un ensemble $E$ (l'ensemble des {\em états} de la chaîne) dont la dépendance au passé se résume à la dépendance à la dernière position. Autrement dit, pour tous états $x_0 ,\ldots,x_{n+1}\in E$, \begin{eqnarray*} \P(X_{n+1}=x_{n+1}|X_{n}=x_{n},\,X_{n-1}=x_{n-1},\ldots,X_{0}=x_{0})=\P(X_{n+1}=x_{n+1}|X_{n}=x_{n}). \end{eqnarray*} On fera, sans le dire, l'hypothèse supplémentaire que la chaîne est {\em indépendante du temps}, i.e. que les probabilités conditionnelles ne dépendent pas de $n$, \begin{eqnarray*} \P(X_{n+1}=j|X_{n}=i)=P_{ij}. \end{eqnarray*} La matrice $P=(P_{ij})_{i,\,j\in E}$ s'appelle la {\em matrice des probabilités de transition}. \end{defi} \begin{prop}\label{unique} Soit $X_0 ,X_1 ,\ldots$ une chaîne de Markov. La loi de $X_n$ est entièrement déterminée par celle de $X_0$ et par la matrice $P$ des probabilités de transition. Si on représente les distributions de probabilité par des vecteurs lignes, alors \begin{eqnarray*} p_{X_{n}}=p_{X_{n-1}}P=p_{X_0}P^n . \end{eqnarray*} Plus généralement, la loi jointe de $(X_0 ,X_1 ,\ldots,X_n)$ est déterminée par $P$ et par la loi de $X_0$. \end{prop} \begin{pf} La loi de $X_{n+1}$ \begin{eqnarray*} \P(X_{n+1}=y)&=&\sum_{x\in E}\P(X_{n+1}=y \textrm{ et }X_{n}=x)\\ &=&\sum_{x\in E}\P(X_{n+1}=y|X_{n}=x)\P(X_{n}=x)\\ &=&\sum_{x\in E}P_{xy}\P(X_{n}=x) \end{eqnarray*} s'exprime en fonction de $P$ et de la loi de $X_n$. Plus généralement, par la définition d'une chaîne de Markov, la loi jointe \begin{eqnarray*} p_{(X_0 ,\ldots,X_n)}(x_0 ,\ldots,x_n) &=&\P(X_0 =x_0 ,\ldots,X_n =x_n)\\ &=&\P(X_n =x_n |X_0 =x_0 ,\ldots,X_{n-1}=x_{n-1})\P(X_0 =x_0 ,\ldots,X_{n-1}=x_{n-1})\\ &=&\P(X_n =x_n |X_{n-1}=x_{n-1})\P(X_0 =x_0 ,\ldots,X_{n-1}=x_{n-1})\\ &=&P_{x_{n-1}x_{n}}\P(X_0 =x_0 ,\ldots,X_{n-1}=x_{n-1})\\ &\vdots&\\ &=&P_{x_{n-1}x_{n}}P_{x_{n-2}x_{n-1}}\cdots P_{x_1 x_2}p_{X_0}(x_0) \end{eqnarray*} s'exprime directement en fonction de $P$ et $p_{X_0}$. \end{pf} \begin{rem} Représentation graphique. Une chaîne de Markov sur $E$ peut être schématisée par un graphe orienté dont l'ensemble des sommets est $E$. Chaque arête orientée $(x,y)$ porte la probabilité de transition $P_{xy}$. Chaque sommet $x$ porte sa probabilité $p(x)$. \end{rem} Voici le schéma correspondant à la chaîne à 2 états de probabilités respectives $\gamma$ et $1-\gamma$ et de matrice de probabilités de transition $\begin{pmatrix}1-\alpha & \alpha\\ \beta & 1-\beta \end{pmatrix}$. \medskip \def\GraphLegend{Graphe orienté schématisant une chaîne de Markov} \figinit{cm} \figpt0:$\gamma$(0,0) \figpt1:(2,1) \figpt2:(4,1) \figpt3:$1-\gamma$(6,0) \figpt4:(4,-1) \figpt5:(2,-1) \figpt6:(5.75,0.16) \figpt7:(0.25,-.16) \figpt8:(-0.2,-0.5) \figpt9:(-1,-0.5) \figpt{10}:(-1,0.5) \figpt{11}:(-0.2,0.5) \figpt{12}:(6.2,-0.5) \figpt{13}:(7,-0.5) \figpt{14}:(7,0.5) \figpt{15}:(6.2,0.5) % 2. Creation of the graphical file \figdrawbegin{} \figset flowchart(line = curve) \figdrawfcconnect [0,1,2,3] \figdrawfcconnect [3,4,5,0] \figset flowchart(line = curve) \figdrawfcconnect [0,8,9,10,11,0] \figdrawfcconnect [3,12,13,14,15,3] \figdrawfcnode[0,3]{} \figdrawend % 3. Writing text on the figure \figvisu{\figBoxA}{\GraphLegend}{% \figwritec [0,3]{} \figwriten 1:$\alpha$(5pt) \figwrites 4:$\beta$(5pt) \figwritew 9:$1-\alpha$(5pt) \figwritee 13:$1-\beta$(5pt) } \centerline{\box\figBoxA} \bigskip On admettra le théorème suivant (on reviendra sur ce point au paragraphe \ref{produit}). \begin{theo} Soit $P$ une matrice {\em stochastique} (les coefficients sont positifs ou nuls, les sommes par ligne valent $1$) de taille $d$. Soit $\mu$ une distribution de probabilité sur $\{1,\ldots,d\}$. Il existe une chaîne de Markov $X_0 ,X_1 ,\ldots$ à valeurs dans $\{1,\ldots,d\}$ dont la matrice des probabilités de transition est $P$ et telle que la loi de $X_0$ est $\mu$. \end{theo} \begin{ex}[Marches aléatoires] Soit $G=(E,w)$ un graphe pondéré fini : il y a un ensemble fini $E$ de sommets, et pour chaque paire de sommets distincts $\{x,y\}$, un réel positif ou nul $w(x,y)=w(y,x)$ ($w(x,y)=0$ signifie que le graphe $G$ ne contient pas l'arête $xy$). La marche aléatoire d'origine $x_0$ est la chaîne de Markov à valeurs dans $E$ telle que $X_0 =x_0$ et dont la matrice des probabilités de transitions est définie par \begin{eqnarray*} P_{xy}=\frac{w(x,y)}{\sum_{z\not=x}w(x,z)}. \end{eqnarray*} si $x\not= y$, et $P_{xx}=0$. \end{ex} Autrement dit, on saute d'un sommet à l'un de ses voisins le long d'une arête choisie au hasard, avec probabilité proportionnelle à son poids. \subsection{Processus stationnaires} \begin{defi} Un processus aléatoire $\Xi=(X_n)_{n\in\N\,\mathrm{ou}\,\Z}$ est \emph{stationnaire} si pour tout $k\in\N$, la loi jointe de $(X_{n+1},\ldots,X_{n+k})$ ne dépend pas de $n$. \end{defi} Autrement dit, une translation dans le temps n'a pas d'effet sur la loi du processus. \begin{ex} Une suite de variables aléatoires indépendantes est un processus stationnaire si et seulement si les variables ont toutes même loi. \end{ex} \begin{prop} Une chaîne de Markov $X_0 ,X_1 ,\ldots$ de loi initiale $p$ et de matrice de probabilités de transition $P$ est stationnaire si et seulement si $pP=p$. \end{prop} \begin{pf} Si la chaîne est stationnaire, alors $X_0$ et $X_1$ ont même loi, $p=p_{X_0}=p_{X_1}=pP$. Réciproquement, si $p=pP$, alors $p_{X_1}=p$. Le processus $Y_n =X_{n+1}$ a même loi initiale et même matrice de probabilités de transition que $X_n$, donc mêmes lois jointes (Proposition \ref{unique}). Cela entraîne que pour tout $k$ et tout $n$, la loi jointe de $(X_{n},\ldots,X_{n+k})$ coïncide avec la loi de $(X_{0},\ldots,X_{k})$. \end{pf} \begin{ex} Pour une chaîne de Markov à deux états, la matrice des probabilités de transition est de la forme $\begin{pmatrix}1-\alpha & \alpha\\ \beta & 1-\beta \end{pmatrix}$. Il y a une unique distribution stationnaire, le vecteur ligne $(\frac{\beta}{\alpha+\beta}\hskip1em\frac{\alpha}{\alpha+\beta})$. \end{ex} On admettra le théorème élémentaire suivant (algèbre linéaire). \begin{theo} Soit $P$ une matrice {\em stochastique} (les coefficients sont positifs ou nuls, les sommes par ligne valent $1$). On suppose $P$ {\em irréductible} (il existe une puissance de $P$ dont tous les coefficients sont strictement positifs) et {\em apériodique} (pour tout $i$, le pgcd des entiers $n$ tels que $(P^{n})_{ii}>0$ vaut $1$). Alors il existe une unique distribution de probabilité stationnaire $\mu$. Pour toute chaîne de Markov de matrice de probabilités de transitions $P$, la loi de $X_n$ tend vers $\mu$ quand $n$ tend vers l'infini. \end{theo} \begin{ex} Pour la marche aléatoire sur le graphe pondéré $G=(E,w)$, la distribution de probabilité suivante \begin{eqnarray*} \mu(x)=\frac{\sum_{z\not=x}w(x,z)}{\sum_{z\in E}\sum_{z'\not=z}w(z,z')} \end{eqnarray*} est stationnaire. \end{ex} Voir Exercice 1, feuille 3. \sugg13 \subsection{Second principe de la thermodynamique} On considère qu'une chaîne de Markov constitue un bon modèle d'un système physique isolé. En effet, le caractère aléatoire résulte de la simplification d'un modèle déterministe (on substitue aux variables microscopiques des observables macroscopiques obtenues en faisant des moyennes), conformément au paradigme de la physique statistique. La condition sur la dépendance par rapport au passé traduit le fait qu'au niveau microscopique, le système suit une évolution déterministe gouvernée par des équations différentielles (une position et une vitesse initiales, i.e. une position dans un espace des phases, déterminent l'évolution future). L'entropie des physiciens est le logarithme du nombre de configurations microscopiques correspondant à l'état macroscopique du système. On donne fréquemment l'exemple suivant. Soit un système isolé comportant $N$ molécules identiques, qui peuvent occuper différents états numérotés de $1$ à $\ell$. On considère que l'état macroscopique du système est décrit par les effectifs $N_1 ,\ldots,N_\ell$ de chaque état, où, de façon équivalente, par les proportions $p_i =\frac{N_i}{N}$. Un même état macrocopique est réalisé à l'échelle microscopique de multiples manières. Le nombre de façons de répartir les $N$ molécules entre les états dans les proportions prescrites $p_i$ est le coefficient multinômial \begin{eqnarray*} \nu(p_1 ,\ldots,p_\ell)=\frac{N!}{N_1 ! \ldots N_\ell}. \end{eqnarray*} D'après Boltzmann, l'entropie du système dans l'état macroscopique $p=(p_1 ,\ldots,p_\ell)$ est $$S=k\log\nu(p),$$ où $k$ est une constante physique, la \emph{constante de Boltzmann}. En utilisant la formule de Stirling, on voit que, lorsque les $N_i$ sont grands, \begin{eqnarray*} S&\sim&N\log_2 N -\sum_{i=1}^{\ell}N_i \log_2 N_i \\ &=&N(-\sum_{i=1}^{\ell}\frac{N_i}{N}\log_2 \frac{N_i}{N})\\ &=&NH(p), \end{eqnarray*} donc l'entropie par molécule vaut $H(p)$. Il semble que seules les chaînes de Markov dont la distribution stationnaire est uniforme aient une réalité physique. \begin{theo}\label{carnot} Soit $X_0 ,X_1 ,\ldots$ une chaîne de Markov. On suppose que la distribution uniforme est stationnaire. Alors l'entropie augmente : la suite $H(X_n)$ est croissante. \end{theo} \finducours5 \begin{rem} Il est facile de caractériser les chaînes de Markov pour lesquelles la distribution uniforme est stationnaire. \textrm{Voir Exercice 2, feuille 3.} \end{rem} \sugg23 Le Théorème \ref{carnot} résulte du fait plus général suivant. \begin{theo}\label{Ddecroit} Soient $\mu$ et $\mu'$ deux distributions de probabilité sur un ensemble fini $E$. Soient $\mu_n =\mu P^{n}$ et $\mu'_n =\mu' P^{n}$ les évolutions de ces distributions sous une même matrice stochastique $P$. Alors l'entropie relative $D(\mu_n ,\mu'_n)$ décroît. \end{theo} \begin{pf} \textbf{du Théorème \ref{Ddecroit}}. Pour $(x,y)\in E\times E$, on pose $p_n (x,y)=\mu_n (x)P_{xy}$ et $q_n (x,y)=\mu'_n (x)P_{xy}$. Par construction, \begin{eqnarray*} p_{n,X}=\mu_n ,\quad q_{n,X}=\mu'_n , \quad p_{n,Y}=\mu_{n+1} ,\quad q_{n,Y}=\mu'_{n+1} , \end{eqnarray*} et, pour $(x,y)\in E\times E$, \begin{eqnarray*} p_{n,Y|X=x}(y)=\frac{\mu_n (x)P_{xy}}{p_{n,X}(x)}=P_{xy}=q_{n,Y|X=x}(y), \end{eqnarray*} les $D(p_{n,Y|X=x}||q_{n,Y|X=x})$ sont toutes nulles, donc $D(p_{n,Y|X}||q_{n,Y|X})=0$. En utilisant deux fois la proposition \ref{chainD}, on obtient \begin{eqnarray*} D(\mu_n ||\mu'_n) &=&D(p_{n,X} ||q_{n,X})\\ &=&D(p_{n,X} ||q_{n,X})+D(p_{n,Y|X}||q_{n,Y|X})\\ &=&D(p_n ||q_n)\\ &=&D(p_{n,Y} ||q_{n,Y})+D(p_{n,X|Y}||q_{n,X|Y})\\ &\geq& D(\mu_{n+1}||\mu'_{n+1}), \end{eqnarray*} car $D(p_{n,X|Y}||q_{n,X|Y})\geq 0$. \end{pf} \begin{pf} \textbf{du Théorème \ref{carnot}}. On applique le Théorème \ref{Ddecroit} à la loi $\mu$ de $X_0$ et à la distribution uniforme $\mu'$. Par hypothèse, $\mu'$ est stationnaire, donc $\mu'_n =\mu'$. En revanche, $\mu_n$ est la loi de $X_n$, qui dépend de $n$. On sait que $D(\mu_n ,\mu')=\log|E|-H(\mu_n)$, donc $H(\mu_n)=H(X_n)$ décroît. \end{pf} \sugg33 \sugg43 Pour une autre manifestation de la croissance de l'entropie, voir l'Exercice 5, feuille 3. \sugg53 \sugg63 \subsection{Les langues naturelles comme processus stochastiques} Au chapitre précédent, on a vu une langue naturelle comme une source, de lettres ou de mots. Autrement dit, comme une distribution de probabilité sur l'ensemble des $27$ lettres (inclure l'espace), ou sur l'ensemble des mots du dictionnaire. Dans l'hypothèse où les textes seraient des tirages aléatoires indépendants (de lettres ou de mots), l'entropie de cette distribution mesure la probabilité des textes typiques. Ce n'est réaliste que pour les textes produits par un singe tapant à la machine ou tirant des mots dans un dictionnaire. Une modélisation plus fidèle du langage consiste à voir un texte comme une réalisation d'un processus stochastique $\Xi =(X_1 ,X_2 ,\ldots)$ non nécessairement indépendant. En première approximation, on peut penser que ce processus est stationnaire : les règles de production de phrases varient suffisamment lentement dans le temps pour qu'on puisse négliger cette variation. Ce qui nous renseigne sur la probabilité de phrases typiques, c'est l'entropie jointe $H(X_1 ,\ldots,X_n)$. Pour les phrases écrites par le singe, les $X_i$ sont indépendantes, donc $H(X_1 ,\ldots,X_n)=nH(X_1)$ est proportionnelle aux nombre de mots. Pour avoir une quantité qui ne tend pas vers l'infini, on considère l'entropie ``par symbole'' (lettre ou mot) $\frac{1}{n}H(X_1 ,\ldots,X_n)$ même dans le cas général. \subsection{Entropie par symbole} \begin{defi} Soit $\Xi=(X_n)_{n\in\N}$ un processus aléatoire. L'entropie par symbole du processus est la limite \begin{eqnarray*} H(\Xi)=\lim_{n\to\infty}\frac{1}{n}H(X_1 ,\ldots,X_n), \end{eqnarray*} lorsqu'elle existe. \end{defi} \begin{rem} Cette limite n'existe pas toujours. Par exemple, pour une suite de variables indépen\-dantes $\frac{1}{n}H(X_1 ,\ldots,X_n)=\frac{1}{n}\sum_{i=1}^{n}H(X_i)$ peut faire à peu près n'importe quoi. \end{rem} \begin{theo}\label{statentr} Soit $\Xi=(X_n)_{n\in\N}$ un processus stationnaire. Alors les limites suivantes existent et sont égales. \begin{eqnarray*} H(\Xi)=\lim_{n\to\infty}\frac{1}{n}H(X_1 ,\ldots,X_n)=\lim_{n\to\infty}H(X_n |X_{n-1},\ldots,X_1). \end{eqnarray*} \end{theo} \begin{pf} D'après le principe ``conditionner diminue l'entropie'', \begin{eqnarray*} H(X_{n+1} |X_{n},\ldots,X_1)\leq H(X_{n+1} |X_{n-1},\ldots,X_2)=H(X_n |X_{n-1},\ldots,X_1) \end{eqnarray*} par stationnarité. Une suite décroissante positive ayant une limite, la suite $u_n =H(X_n |X_{n-1},\ldots,X_1)$ converge. D'autre part, d'après la Proposition \ref{chain}, \begin{eqnarray*} H(X_1 ,\ldots,X_n)=\sum_{i=1}^{n}H(X_i |X_{i-1},\ldots,X_1)=\sum_{i=1}^{n}u_i . \end{eqnarray*} Pour tout suite convergente $u_n$, $v_n =\frac{1}{n}\sum_{i=1}^{n}u_i$ converge vers la même limite. \end{pf} \begin{ex} Si $\Xi$ est une suite de variables indépendantes de même loi $p$, alors $H(\Xi)=p$. \end{ex} Il faut donc penser à l'entropie par symbole $H(\Xi)$ comme une généralisation aux processus de l'entropie d'une variable isolée. \begin{prop} Soit $\Xi=(X_n)_{n\in\N}$ une chaîne de Markov stationnaire. Alors \begin{eqnarray*} H(\Xi)=H(X_1 |X_0)=-\sum_{x,\,y\in E}\mu(x)P_{xy}\log_2 (P_{xy}), \end{eqnarray*} où $\mu$ désigne la distribution de $X_0$, qui est stationnaire. \end{prop} \begin{pf} Par définition d'une chaîne de Markov, la loi conditionnelle de $X_n |X_{n-1}=x_{n-1},\ldots,$ $X_0 =x_0$ coïncide avec la loi conditionnelle $X_n |X_{n-1}=x_{n-1}$, donc $H(X_n |X_{n-1},\ldots,X_1)=H(X_n |X_{n-1})=H(X_1 ,X_0)$ par stationnarité. Par définition de la matrice des probabilités de transition, la loi conditionnelle $p_{X_1 |X_0 =x}(y)=P_{xy}$, donc $H(p_{X_1 |X_0 =x})=-\sum_{y\in E}$ et $H(X_1 ,X_0)=-\sum_{x,\,y\in E}\mu(x)P_{xy}\log_2 (P_{xy})$. \end{pf} \begin{cor} Soit $\Xi=(X_n)_{n\in\N}$ une chaîne de Markov irréductible et apériodique. Alors l'entropie par symbole est bien définie et vaut $H(\Xi)=-\sum_{x,\,y\in E}\mu(x)P_{xy}\log_2 (P_{xy})$, où $\mu$ est la distribution stationnaire et $P$ la matrice des probabilités de transition. \end{cor} \begin{ex} Soit $G=(E,w)$ un graphe pondéré fini. On pose, pour $x\in E$, $W(x)=\sum_{y\not=x}w(x,y)$ et $W=\sum_{x\in E}W(x)$. On introduit deux distributions de probabilité, $p(x,y)=\frac{w(x,y)}{W}$ sur $E\times E$ et $\mu(x)=\frac{W(x)}{W}$ sur $E$. Soit $\Xi$ une marche aléatoire sur $G$. On suppose qu'elle est irréductible et apériodique. Alors $H(\Xi)=H(p)-H(\mu)$. \end{ex} Voir Exercice 7, feuille 3. \sugg73 \sugg83 \subsection{Entropie par symbole d'une langue naturelle} La mesure directe de l'entropie par lettre (ou par mot) d'une langue naturelle est malaisée. Par exemple, si $X_n$ désigne la $n$-ème lettre d'un texte tiré au hasard, les lois conditionnelles de $X_{5}|X_{4}=x_{4},X_3 = x_3,X_2 = x_2 ,X_1 =x_1$ sont au nombre de $27^4 =531 441$. Evaluer directement ces probabilités nécessite de traiter des millions de bouts de textes. Aller loin au delà n'est pas envisageable, sans parler d'évaluer une limite. En 1951, Shannon a suggéré de procéder autrement, au moyen d'un protocole expérimental faisant intervenir des volontaires (étudiants) à qui on présente des textes tronqués, de longueur $75$. Pour chaque texte, chaque volontaire doit deviner la lettre suivante. Il doit fournir une liste de $27$ lettres ordonnée par probabilité décroissante. Dans chaque liste, l'expérimentateur note le rang de la lettre qui était effectivement la suivante dans le texte examiné. Par exemple, confronté au texte "\emph{allons enfants de la patrie le jour de gloire est arrive contre nous de la }", le volontaire répond la liste ordonnée : \emph{m, t, e, c, a, b,...,} et l'expérimentateur note : $2$. Il fait de même avec $11$ autres volontaires, confrontés à $10$ textes chacun, soigneusement tirés au hasard dans un gros livre. Il obtient $120$ notes comprises entre $1$ et $27$, dont il fait un histogramme, i.e. le tableau des effectifs $N_1 ,\ldots,N_{27}$. Il calcule une \emph{entropie empirique} \begin{eqnarray*} h=-\sum_{i=1}^{27}\frac{N_i}{120}\log_2 (\frac{N_i}{120}). \end{eqnarray*} L'expérience, conduite par Shannon en 1950, a donné une valeur de 1.3 bits par lettre pour la langue anglaise. Pourquoi cette valeur expérimentale constitue t'elle une valeur approchée de l'entropie de la langue anglaise ? On fait l'hypothèse que les volontaires connaissent bien leur langue, et qu'ils produisent tous leurs listes en suivant le même raisonnement déterministe. La note ne dépend alors que du texte. Si le texte est tiré au hasard, cette note devient une variable aléatoire $Y$ à valeurs dans $E=\{1,\ldots,27\}$. Cette variable contient la même information que la variable $X_{76}$ : étant donné un texte $t=t_1 \ldots t_{76}$, la $76$ème lettre $t_{76}=X_{76}(t)$ de $t$ est uniquement déterminée par $t_1 \ldots t_{75}$ et $Y(t_1 \ldots t_{75})$. Donc les lois conditionnelles de $Y$ et de $X_{76}$ sachant les $75$ premières lettres sont les mêmes, à une bijection de $E$ sur l'alphabet près. En particulier, l'entropie $H(Y)=H(X_{76}|X_1 ,\ldots,X_{75})$. L'expérience constitue une simulation de la variable $Y$. D'après la loi des grands nombres, quand le nombre de volontaires tend vers l'infini, l'histogramme des notes converge vers la loi de $Y$, donc l'entropie empirique calculée à partir de cet histogramme converge vers $H(X_{76}|X_1 ,\ldots,X_{75})$. Celle-ci constitue un majorant de l'entropie par lettre de la langue anglaise. Les hésitations et erreurs introduites par les volontaires tendent à augmenter l'entropie de $Y$, cela va dans le même sens : la valeur réelle de l'entropie par lettre de la langue anglaise est inférieure à la valeur empirique. Comment interpréter la valeur numérique 1.3 bits par lettre ? Il faut d'abord la comparer au maximum possible, $\log_2 (27)=4.75$, atteinte lorsque les lettres sont tirées indépendamment selon la distribution uniforme. Lorsqu'on tire les lettres indépendamment selon la distribution qu'elles ont en anglais, donnée par le tableau suivant, \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline lettre&e&t&a&o&i&n&s&h&r&d&l&c&u\\ \hline \%&13& 9& 8& 7,5& 7& 6,8& 6,5& 6,2& 6& 4& 3,8& 2,8& 2,7 \\ \hline lettre &m&w&f&g&y&p&b&v&k&j&x&q&z\\ \hline \%& 2,5& 2,4& 2,3 &2,1 &2& 1,9& 1,5& 1,1& 0,9& 0,2& 0,2& 0,1& 0,1 \\ \hline \end{tabular} \end{center} l'entropie vaut 4.2. Une meilleure approximation est obtenue par une chaîne de Markov stationnaire dont la matrice des probabilités de transition est tirée du tableau des fréquences des couples de lettres en anglais. L'entropie par lettre de cette chaîne vaut 4.03 bits par lettre. On peut raffiner en tirant chaque lettre supplémentaire en respectant la loi jointe de 3 ou de 4 lettres, dont l'entropie vaut 2.3 bits par lettre. Une entropie nettement plus basse, de 1.3 bits par lettre, signifie que l'anglais est bien plus déterministe, du fait des règles de grammaire et de construction des mots. \subsection{A retenir} \begin{itemize} \item La notion de chaîne de Markov. \item La notion d'entropie par symbole. \item Le cas des chaînes de Markov. \end{itemize} Il s'agit d'un chapitre mi-théorique, mi-pratique, où on donne une définition précise à une notion qui provient de problèmes concrets, tout en posant les bases de développements ultérieurs. \section{Equipartition asymptotique} Dans cette section, on donne une nouvelle preuve du théorème du codage de source, basée sur l'idée que la loi jointe de variables iid est concentrée. \subsection{Comportement typique pour une suite de variables iid}\label{iid} \begin{nota} Un {\em processus aléatoire} à valeurs dans un ensemble $E$, c'est simplement une suite de variables aléatoires $\Xi=(X_n)_{n\in I}$ à valeurs dans $E$, indexée par $I=\N$, $\N\setminus\{0\}$ ou $\Z$. Pour $m\leq n$, on note $X_m^n =(X_m ,X_{m+1},\ldots,X_n)$. On note $p_m^n$ sa loi, une distribution de probabilité sur $E^n$. \end{nota} On s'intéresse à la probabilité de sortie d'une suite $(x_1 ,\ldots,x_n)\in E^n$, $p_{1}^{n}(x_1 ,\ldots,x_n)$, vue comme variable aléatoire. Autrement dit, $p_1^n$ est une fonction sur $E^n$, et on considère la variable aléatoire $p_{1}^{n}(X_1 ,\ldots,X_n)$, qu'on peut noter $p_1^n (X_1^n)$. \begin{ques} Etant donné un processus aléatoire $\Xi=(X_n)_{n\in\N}$, quel est le comportement asymptotique de la variable aléatoire $p_1^n (X_1^n)$ lorsque $n$ tend vers l'infini ? \end{ques} On va formaliser le raisonnement indiqué au début du cours (paragraphe \ref{simul}). \begin{rappel}[Loi des grands nombres] Soit $\Xi=(X_n)_{n\in\N}$ une suite de variables aléatoires indépendantes, de même loi, intégrables (i.e. $\E(|X_0|)<+\infty$). Alors la suite $S_n =\frac{1}{n}\sum_{i=1}^{n}X_i$ converge presque sûrement vers la constante $\E(X_0)$. En particulier, elle converge en probabilité, i.e. pour tout $\eps>0$, la probabilité $\P(|S_n-\E(X_0)|>\eps)$ tend vers $0$ quand $n$ tend vers $+\infty$. \end{rappel} A toutes fins utiles, on donne au paragraphe \ref{interlude} une preuve de la loi des grands nombres sous l'hypothèse (suffisante pour l'application ci-dessous) que $X_0$ est bornée. Et on explique pourquoi convergence presque sûre implique convergence en probabilité. \begin{theo}[Equipartition asymptotique]\label{aep} Soit $\Xi=(X_n)_{n\in\N}$ une suite de variables aléatoi\-res indépendantes, de même loi $p$. Alors $-\frac{1}{n}\log_2 p_1^n (X_1^n)$ converge presque partout et en probabilité vers la constante $H(p)$. En particulier, pour tout $\eps>0$, la probabilité $\P(|-\frac{1}{n}\log_2 p_1^n (X_1^n)-H(p)|>\eps)$ tend vers $0$ quand $n$ tend vers $+\infty$. \end{theo} \begin{pf} Par indépendance, $p_1^n (x_1 ,\ldots,x_n)=p(x_1)\cdots p(x_n)$. Les variables $Z_i =-\log_2 p(X_i)$ sont indépendantes, donc, d'après la loi des grands nombres \begin{eqnarray*} -\frac{1}{n}\log_2 p_1^n (X_1^n)=\frac{1}{n}\sum_{i=1}^{n}Z_i \to \E(-\log_2 p(X_0))=H(p), \end{eqnarray*} en probabilité. \end{pf} Interprétation : Etant donné $\eps>0$ et $n\in\N$, soit $T$ le sous-ensemble de $E^n$ défini par \begin{eqnarray*} T=\{t \in E^n \,;\, 2^{-n(H(p)+\eps)}\leq p_1^n (t) \leq 2^{-n(H(p)-\eps)}\}, \end{eqnarray*} et soit $S$ son complémentaire. Alors $p_1^n (S)$ tend vers $0$ quand $n$ tend vers $+\infty$ à $\eps$ fixé. De plus, comme $p$ est presque constante sur $T$, le nombre d'éléments de $T$ est de l'ordre de $2^{nH(p)}$. Précisément, pour $n$ assez grand, \begin{eqnarray*} (1-\eps)2^{n(H(p)-\eps)}\leq|T|\leq 2^{n(H(p)+\eps)}. \end{eqnarray*} On pense à $T$ comme à l'ensemble des ``suites typiques'', ce sont celles qui ont le plus de chances de sortir. \sugg14 \subsection{Suites conjointement typiques} Il s'agit d'une variante de l'équipartition qui permet de donner une interprétation à l'information mutuelle. De plus, cette notion va être à l'origine d'un procédé de décodage utilisé au chapitre \ref{transmission}. \begin{defi} Considérons deux variables aléatoires $X$ et $Y$ de loi jointe $p_{(X,Y)}$. Soient $n\in\N$ et $\eps>0$. L'ensemble $T=T(n,\eps)\subset (E_X \times E_Y)^n$ des suites \emph{conjointement typiques} est l'ensemble des suites $(x,y)_1^n$ telles que \begin{enumerate} \item $|-\frac{1}{n}\log_2 (p_X (x_1)\cdots p_X (x_n))-H(X)|<\eps$. \item $|-\frac{1}{n}\log_2 (p_Y (y_1)\cdots p_Y (y_n))-H(Y)|<\eps$. \item $|-\frac{1}{n}\log_2 (p_{(X,Y)} (x_1 ,y_1)\cdots p_{(X,Y)} (x_n ,y_n))-H(X,Y)|<\eps$. \end{enumerate} \end{defi} Autrement dit, $x_1^n$ est typique pour $p_X$, $y_1^n$ est typique pour $p_Y$ et $((x_1,y_1),\ldots(x_n ,y_n))$ est typique pour $p_{(X,Y)}$. \begin{prop}\label{jointtypique} Soit $(X,Y)_1^n$ une suite de variables indépendantes et de même loi $p_{(X,Y)}$. Alors, pour $n$ assez grand, \begin{enumerate} \item $\P((X,Y)_1^n \in T)$ tend vers $1$ quand $n$ tend vers $+\infty$. \item $(1-\eps)2^{n(H(X,Y)+\eps)}\leq|T|\leq 2^{n(H(X,Y)+\eps)}$. \item Soient $\tilde{X}_1^n$ et $\tilde{Y}_1^n$ des variables indépendantes, de lois respectives $p_X$ et $p_Y$. Alors, pour $n$ assez grand, \begin{eqnarray*} (1-\eps)2^{-n(I(X;Y)+3\eps)}\leq\P((\tilde{X},\tilde{Y})_1^n \in T)\leq 2^{-n(I(X;Y)-3\eps)}. \end{eqnarray*} \end{enumerate} \end{prop} \begin{pf} 1. On applique la loi des grands nombres aux trois variables \begin{eqnarray*} -\log_2 p_X (X_n),\quad -\log_2 p_Y (Y_n),\quad -\log_2 p_{(X,Y)} (X_n ,Y_n). \end{eqnarray*} Presque sûrement, les trois convergent respectivement vers $H(X)$, $H(Y)$ et $H(X,Y)$. En particulier, il y a convergence en probabilité. 2. Pour chaque $t\in T$, pour $n$ assez grand, \begin{eqnarray*} 2^{-n(H(X,Y)+\eps)}\leq\P((X,Y)_1^n =t)\leq 2^{-n(H(X,Y)-\eps)}. \end{eqnarray*} On écrit \begin{eqnarray*} 1\geq \P((X,Y)_1^n \in T)=\sum_{t\in T}\P((X,Y)_1^n =t)\geq|T|2^{-n(H(X,Y)+\eps)}, \end{eqnarray*} D'où $|T|\leq 2^{n(H(X,Y)+\eps}$. Inversement, pour $n$ assez grand, $\P((X,Y)_1^n \in T)\geq1-\eps$, ce qui s'écrit \begin{eqnarray*} 1-\eps\leq\sum_{t\in T}\P((X,Y)_1^n =t)\leq |T|2^{-n(H(X,Y)-\eps)}, \end{eqnarray*} soit $|T|\geq (1-\eps)2^{n(H(X,Y)-\eps)}$. 3. Par hypothèse, pour $t=((x_1,y_1),\ldots,(x_n,y_n))\in T$, \begin{eqnarray*} P((\tilde{X},\tilde{Y})_1^n =t)&=&p_X (x_1)\cdots p_X (x_n) p_Y (y_1)\cdots p_Y (y_n)\\ &\leq&2^{-n(H(X)-\eps)}2^{-n(H(Y)-\eps)}, \end{eqnarray*} d'où \begin{eqnarray*} \P((\tilde{X},\tilde{Y})_1^n \in T)\leq 2^{-n(H(X)-\eps)}2^{-n(H(Y)-\eps)}|T|\leq 2^{-n(H(X,Y)-H(X)-H(Y)-3\eps)}. \end{eqnarray*} De même, pour $t\in T$, \begin{eqnarray*} P((\tilde{X},\tilde{Y})_1^n =t)\geq 2^{-n(H(X)+\eps)}2^{-n(H(Y)+\eps)}, \end{eqnarray*} d'où \begin{eqnarray*} \P((\tilde{X},\tilde{Y})_1^n \in T)\geq 2^{-n(H(X)+\eps)}2^{-n(H(Y)+\eps)}|T|\geq (1-\eps)2^{-n(H(X)+H(Y)-H(X,Y)+3\eps)}. \end{eqnarray*} \end{pf} \finducours6 \subsection{Application au codage de source} \begin{prop}\label{source} Soit $\Xi=(X_n)_{n\in\N}$ une suite de variables aléatoires indépendantes, de même loi $p$. Soit $\mathcal{D}$ un alphabet à $D=|\mathcal{D}|$ lettres. Soit $\eps>0$. Il existe $n_0 \in\N$ tel que, pour tout $n\geq n_0$, il se produit la chose suivante. \begin{enumerate} \item Pour toute application injective $C^* :E^n \to \mathcal{D}^*$, la longueur moyenne \begin{eqnarray*} \E(\frac{1}{n}\ell(X_1^n))\geq \frac{1}{\log_2 D}H(p)-\eps. \end{eqnarray*} \item Il existe une application injective $C^* :E^n \to \mathcal{D}^*$ dont la longueur moyenne \begin{eqnarray*} \E(\frac{1}{n}\ell(X_1^n))\leq \frac{1}{\log_2 D}H(p)+\eps. \end{eqnarray*} \end{enumerate} \end{prop} Le premier énoncé est un peu plus fort que celui du Théorème \ref{cod}. En effet, si $C:E\to \mathcal{D}^*$ est un codage uniquement décodable, son extension aux textes $C^*:E^* \to \mathcal{D}^*$ est injective, et en particulier sa restriction à l'ensemble $E^n$ des textes à $n$ mots est injective. De plus, dans le contexte du Théorème \ref{cod}, $C^* (x_1^n)=C(x_1)\cdots C(x_n)$, donc $\ell(x_1^n)=\sum_{i=1}^{n}\ell(x_i)$, $\E(\ell(X_1^n))=\sum_{i=1}^{n}\E(\ell(X_i))=n\E(\ell(X_0))$. En faisant varier $\eps$ et en faisant tendre $n$ vers l'infini, l'inégalité $\E(\ell(X_0))=\E(\frac{1}{n}\ell(X_1^n))\geq \frac{1}{\log_2 D}H(p)-\eps$ entraîne que $\E(\ell(X_0))\geq \frac{1}{\log_2 D}H(X_0)=\frac{H(p)}{\log_2 D}$. Donc la proposition \ref{source} implique bien la borne inférieure pour la longueur moyenne des codages uniquement décodables donnée par le Théorème \ref{cod}. C'était d'ailleurs l'argument que Shannon avait en tête. Le second énoncé ne se compare pas directement à celui de Shannon. Néanmoins, il indique bien que la borne par l'entropie est essentiellement optimale. \begin{pf} On étend à $D$ quelconque le résultat de l'exercice 3 de la feuille 2, limité au cas où $D=2$. Par hypothèse, $C^*$ est un codage non singulier de $E^n$. Dans un codage non singulier optimal, les $D$ premiers éléments sont codés par des suites de longueur $1$, les $D^2$ suivant par des suites de longueur $2$, etc... La longueur $\ell(x_i)$ du $i$-ème élément de $E$ satisfait \begin{eqnarray*} \sum_{k=1}^{\ell(x_i)-1}D^k < i \leq \sum_{k=1}^{\ell(x_i)}D^k , \end{eqnarray*} i.e. \begin{eqnarray*} \frac{D^{\ell(x_i)}-1}{D-1}-1 < i \leq \frac{D^{\ell(x_i)+1}-1}{D-1}-1 , \end{eqnarray*} ce qui s'écrit aussi \begin{eqnarray*} \ell(x_i)<\log_D ((D-1)(i+1)+1)\leq\ell(x_i)+1, \end{eqnarray*} soit $\ell(x_i)=\lceil \log_D ((D-1)(i+1)+1)\rceil=\lceil \log_D (\frac{(D-1)i}{D}+1)\rceil$. D'où l'inégalité \begin{eqnarray*} \E(\ell(X))\geq\sum_{i=1}^{|E|}p(x_i)\lceil \log_D (\frac{(D-1)i}{D}+1) \rceil\geq M:=\sum_{i=1}^{|E|}p(x_i)\log_D (\frac{(D-1)i}{D}+1). \end{eqnarray*} On pose \begin{eqnarray*} c=\sum_{i=1}^{|E^n|}\frac{1}{\frac{(D-1)i}{D}+1}, \quad q(x_i)=\frac{1}{c}\frac{1}{\frac{(D-1)i}{D}+1}. \end{eqnarray*} Comme $q$ est une distribution de probabilité, on peut appliquer le Théorème \ref{D>0}, \begin{eqnarray*} 0&\leq& \frac{D(p||q)}{\log_2 (D)}=\sum_{i=1}^{|E|^n}p(x_i)\log_D p(x_i)-\sum_{i=1}^{|E|^n}p(x_i)\log_D q(x_i)\\ &=&-\frac{H(p)}{\log_2 D}+\sum_{i=1}^{|E|^n}p(x_i)\log_D (c(\frac{(D-1)i}{D}+1))\\ &=&-\frac{H(p)}{\log_2 D}+\log_D (c)+M, \end{eqnarray*} d'où $\frac{H(p)}{\log_2 D}-M\leq\log_D (c)$. Il reste à majorer $c$. On utilise l'encadrement de la série harmonique par le logarithme népérien : si $h(k)=\sum_{j=1}^{n}\frac{1}{j}$, alors $h(k)\leq \ell n(k)+1$. Ici, \begin{eqnarray*} c=\sum_{i=1}^{|E|^n}\frac{1}{\frac{(D-1)i}{D}+1}=\frac{D}{D-1}\sum_{i=1}^{|E|^n}\frac{1}{i+\frac{D}{D-1}}\leq 2(h(|E|^n+1)-1)\leq 2\ell n(|E|^n +1)-2\leq 2n\ell n(|E|). \end{eqnarray*} On voit que $\log_D (c)\leq O(\log(n))$. D'où la minoration $\E(\frac{1}{n}\ell(X))\geq \frac{H(p)}{\log_2 D}-O(\frac{\log n}{n})\geq \frac{H(p)}{\log_2 D}-\eps$ pour $n$ assez grand. Inversement, soit $T=T(n,\eps)$ l'ensemble des suites typiques et $S$ son complémentaire. Soit $L$ le plus petit entier tel que $|T|\leq D^L$. Alors $L\leq n\frac{(H(p)+\eps)}{\log_2 D}+1$. Il existe une application injective $C:T\to \mathcal{D}^L$, on choisit n'importe laquelle. Soit $L'$ le plus petit entier $>L$ tel que $|E^n|\leq D^{L'}$. Alors $L'\leq n\frac{\log_2 |E|}{\log_2 D}+1$. Sur $S$, on choisit une application injective à valeurs dans $\mathcal{D}^{L'}$. On calcule \begin{eqnarray*} \E(\frac{1}{n}\ell(X_1^n))&=&\sum_{t\in T}p_1^n (t)\frac{L}{n} +\sum_{s\in S}p_1^n (s)\frac{L'}{n}\\ &\leq& \P(X_1^n \in T)\frac{H(p)+\eps}{\log_2 D}+\P(X_1^n \in S)\frac{\log_2 |E|}{\log_2 D}+o(1), \end{eqnarray*} qui tend vers $\frac{H(p)+\eps}{\log_2 D}$ quand $n$ tend vers l'infini. \end{pf} \subsection{Equirépartition asymptotique pour les processus stationnaires} On va étendre aux processus aléatoire stationnaires le théorème d'équirépartition asymptotique. On n'ira pas jusqu'au bout de la preuve, assez difficile, mais on établira la traduction du problème dans le langage des systèmes dynamiques. Cela nous conduira naturellement à deux pierres angulaires de cette théorie, la notion d'ergodicité et le Théorème Ergodique de Birkhoff. Comme au paragraphe \ref{iid}, étant donné un processus aléatoire $\Xi$, on s'intéresse à la probabilité de sortie d'une suite $(x_1 ,\ldots,x_n)\in E^n$, $p_{1}^{n}(x_1 ,\ldots,x_n)$, vue comme variable aléatoire. Autrement dit, $p_1^n$ est une fonction sur $E^n$, et on considère la variable aléatoire $p_{1}^{n}(X_1 ,\ldots,X_n)$, qu'on peut noter $p_1^n (X_1^n)$. On vise le théorème suivant. \begin{theo}[Shannon, McMillan, Breiman]\label{smb} Soit $\Xi=(X_n)_{n\in\Z}$ un processus stationnaire d'entropie par symbole $H(\Xi)$. Alors \begin{eqnarray*} \lim_{n\to\infty}-\frac{1}{n}\log_2 p_{1}^{n}(X_1^n)=H(\Xi) \quad \textrm{presque sûrement}. \end{eqnarray*} \end{theo} On renvoie au Chapitre 16.8 du livre de Cover et Thomas. On va présenter quelques ingrédients de la preuve. \subsection{Schéma de la preuve} L'espérance de la variable $-\log_2 p_{1}^{n}(X_1^n)$ est l'entropie jointe $H(X_1^n)$. Il s'agit donc de montrer qu'une variable aléatoire se concentre autour de son espérance. Comme dans la preuve de l'équirépartition asymptotique pour les suites iid, on voudrait utiliser la loi des grands nombres. Pour faire apparaître une moyenne de variables, on introduit les lois conditionnelles \begin{eqnarray*} p(x_i |x_1^{i-1})=\P(X_i =x_i |X_{i-1}=x_{i-1},\ldots,X_{1}=x_{1}), \end{eqnarray*} (vue ici comme une simple fonction sur $E^{i+1}$) et on écrit que \begin{eqnarray*} p_1^n (x_1^n)=p(x_i)\prod_{i=2}^{n}p(x_i |x_1^{i-1}), \end{eqnarray*} d'où \begin{eqnarray*} p_1^n (X_1^n)=p(X_i)\prod_{i=2}^{n}p(X_i |X_1^{i-1}), \end{eqnarray*} Les variables $-\log_2 p(X_i |X_1^{i-1})$ n'étant pas indépendantes, la loi des grands nombres ordinaire (Proposition \ref{lgn}) ne s'applique pas. La forme la plus générale de la loi des grands nombres, c'est le Théorème Ergodique de Birkhoff. Il se formule en termes de transformation préservant une mesure de probabilité. On va maintenant expliquer le lien entre processus stationnaires et transformations préservant une mesure de probabilité. \finducours7 \subsection{Processus stationnaires et transformations préservant une mesure de probabilité} \label{produit} \begin{prop} Soit $\Xi=((X_n)_{n\in\Z})$ un processus aléatoire stationnaire à valeurs dans un ensemble fini $E$. Sur l'ensemble $E^{\Z}$ des suites bi-infinies d'éléments de $E$, muni de la tribu $\mathcal{B}$ engendrée par les cylindres, il existe une unique mesure de probabilité $\mu$ possédant les propriétés suivantes. \begin{itemize} \item $\mu$ est invariante par le \emph{décalage} $T:(x_n)_{n\in\Z}\mapsto (y_{n})_{n\in\Z}$, où $y_n =x_{n+1}$. \item Le processus $\Upsilon$ formé par les fonctions coordonnées $Y_m ((x_n)_{n\in\Z})=x_m$ a les mêmes lois jointes que $\Xi$. \end{itemize} Réciproquement, \end{prop} Autrement dit, on peut supposer que $X_n$ est la $n$-ème fonction coordonnée sur $E^{\Z}$, ce qu'on fera dans la suite. \begin{pf} Etant donnés $m\leq n\in\Z$ et $z_m^n \in E^{n-m+1}$, on appelle cylindre l'ensemble \begin{eqnarray*} C_{z_m^n}=\{(x_n)_{n\in\Z}\,;\, x_m =z_m ,\ldots,x_n =z_n\}. \end{eqnarray*} La mesure $\mu$ doit satisfaire \begin{eqnarray*} \mu(C_{z_m^n})=\P(X_m =z_m ,\ldots,\,X_n =z_n). \end{eqnarray*} Comme les cylindres engendrent la tribu $\mathcal{B}$, $\mu$ est uniquement déterminée par ces conditions. Réciproquement, ces conditions définissent une fonction $T$-invariante sur l'ensemble des cylindres. Le fait que cette fonction se prolonge en une mesure résulte d'un principe général dû à Kolmogorov. \end{pf} \begin{ex} Soient $X_n$, $n\in\Z$, des variables indépendantes et de même loi $p$. Alors $\mu=p_{\Z}$ est la mesure produit. \end{ex} \begin{ex} Soit $X_n$, $n\in\Z$, une chaîne de Markov stationnaire, de loi $p$ et de matrice de probabilités de transition. Alors $\mu$ est caractérisée par \begin{eqnarray*} \mu(C_{z_m^n})=p(z_m)P_{z_m z_{m+1}}\cdots P_{z_{n-1}z_n}. \end{eqnarray*} \end{ex} \sugg24 \subsection{Le Théorème Ergodique de Birkhoff} Voici le substitut annoncé de la loi des grands nombres. \begin{theo}[Birkhoff 1931]\label{birk} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $T:\Omega\to \Omega$ une bijection qui préserve la mesure. Soit $f:\Omega\to\R$ une fonction intégrable. Alors la limite \begin{eqnarray*} \bar{f}(x)=\lim_{n\to+\infty}\frac{1}{n}\left(f(x)+f(T(x))+\cdots+f(T^{n-1}(x))\right) \end{eqnarray*} existe $\mu$-presque partout. La fonction $\bar{f}$ est intégrable, son espérance est égale à celle de $f$. Enfin, $\bar{f}\circ T=\bar{f}$ presque partout. \end{theo} \begin{pf} Voir le livre de Petersen, pages 27 à 33. \end{pf} Lorsque $\Omega=E^{\Z}$, $\mathcal{B}$ est la tribu produit et $\mu=p^{\Z}$ est la mesure produit, les coordonnées $X_n$ sont des variables aléatoires indépendantes et de même loi, le Théorème \ref{birk} affirme que les sommes $\frac{1}{n}\sum_{i=1}^{n}f(X_i)$ convergent presque sûrement vers une fonction $T$-invariante $\bar{f}$. Il faudrait encore montrer que $\bar{f}$ est presque partout constante. C'est vrai pour les suites de variables indépendantes, mais pas pour tous les processus stationnaires, comme on va le voir. \subsection{Ergodicité} \begin{defi} On dit qu'une transformation préservant la mesure $T:\Omega\to \Omega$ est \emph{ergodique} si, pour tout ensemble mesurable $A\in\mathcal{B}$, \begin{eqnarray*} T(A)=A \quad\Rightarrow\quad \mu(A)(1-\mu(A))=0. \end{eqnarray*} \end{defi} En particulier, une fonction invariante coïncide avec son espérance presque partout. Cela entraîne que les sommes de Birkhoff convergent presque partout vers l'espérance de $f$. \begin{prop}[Ergodicité des chaînes de Markov]\label{markoverg} Soit $\Xi$ une chaîne de Markov stationnaire et irréductible. Alors le décalage $T:E^{\Z}\to E^{\Z}$ est ergodique pour la mesure $\mu$. La réciproque est vraie : l'ergodicité de $T$ entraîne que la chaîne est irréductible, pourvu que la mesure stationnaire charge tous les points de $E$. \end{prop} \begin{pf} Soit, pour $x\in E$, $f_x$ la fonction caractéristique de l'ensemble $C_x$ des suites $(x_n)_{n\in\Z}$ telle $x_0 =x$. Le théorème ergodique de Birkhoff affirme que la suite de fonctions $\frac{1}{n}\sum_{i=1}^{n}f_x \circ T^i$ converge presque partout. Par convergence dominée, pour tous $x$, $y\in E$, la limite \begin{eqnarray*} q_{yx}=\frac{1}{\E(f_y)}\lim_{n\to+\infty}\E(\frac{1}{n}\sum_{i=1}^{n}(f_x \circ T^i)f_y) \end{eqnarray*} existe. Or \begin{eqnarray*} \frac{1}{\E(f_y)}\E((f_x \circ T^i)f_y)&=&\frac{1}{p(y)}\P(X_0 =y\textrm{ et }X_i =x)\\ &=&\P(X_i =x|X_0 =y)=P^{i}_{yx}, \end{eqnarray*} (ici, $P^i$ désigne la puissance $i$-ème de la matrice des probabilités de transition $P$), donc \begin{eqnarray*} q_{xy}&=&\lim_{n\to+\infty}\frac{1}{n}\sum_{i=1}^{n}\E((f_x \circ T^i)f_y)\\ &=&\lim_{n\to+\infty}\frac{1}{n}\sum_{i=1}^{n}P^{i}_{yx}. \end{eqnarray*} Autrement dit, la limite \begin{eqnarray*} Q=\lim_{n\to+\infty}\frac{1}{n}\sum_{i=1}^{n}P^{i} \end{eqnarray*} existe (on pourrait aussi le démontrer directement par l'algèbre linéaire). Chaque ligne $q$ de $Q$ est une distribution de probabilité et satisfait $qP=q$. Par unicité de la distribution stationnaire, $q=p$, donc \begin{eqnarray*} \lim_{n\to+\infty}\frac{1}{n}\sum_{i=1}^{n}\E((f_x \circ T^i)f_y)=\E(f_x)\E(f_y). \end{eqnarray*} Plus généralement, soit $f_{z_{r}^{r+\ell}}$ la fonction caractéristique de l'ensemble $C_{z_{r}^{r+\ell}}$ des suites $(x_n)_{n\in\Z}$ telles $x_r =z_r ,\ldots,x_{r+\ell}=z_{r+\ell}$. Alors, dès que $i+r>s+m$, \begin{eqnarray*} \E((f_{z_{r}^{r+\ell}} \circ T^i)f_{z_{s}^{s+m}})&=&\P(X_{s}^{s+m}=z_{s}^{s+m}\textrm{ et }X_{r+i}^{r+i+\ell}=z_{r+i}^{r+i+\ell})\\ &=&p(z_s)P_{z_s z_{s+1}}\cdots P_{z_{m-1}z_{m}}P_{z_{m}z_{r+i}}^{i-m}P_{z_{r+i}z_{r+i+1}}\cdots P_{z_{r+i+\ell-1}z_{r+i+\ell}}. \end{eqnarray*} donc \begin{eqnarray*} \lim_{n\to+\infty}\frac{1}{n}\sum_{i=s+m+1}^{n}\E((f_{z_{r}^{r+\ell}} \circ T^i)f_{z_{s}^{s+m}}) &=&p(z_s)P_{z_s z_{s+1}}\cdots P_{z_{z+m-1}z_{m}}\\ &&Q_{z_{m}z_{r+i}}P_{z_{r+i}z_{r+i+1}}\cdots P_{z_{r+i+\ell-1}z_{r+i+\ell}}\\ &=&\P(X_{s}^{s+m}=z_{s}^{s+m})p(z_{r})P_{z_{r+i}z_{r+i+1}}\cdots P_{z_{r+i+\ell-1}z_{r+i+\ell}}\\ &=&\P(X_{s}^{s+m}=z_{s}^{s+m})\P(X_{r}^{r+\ell}=z_{r}^{r+\ell})\\ &=&\E(f_{z_{r}^{r+\ell}})\E(f_{z_{s}^{s+m}}). \end{eqnarray*} Ajouter le terme $\sum_{i=1}^{s+m}\E((f_{z_{r}^{r+\ell}} \circ T^i)f_{z_{s}^{s+m}})$ ne change pas la limite. L'espace vectoriel engendré par la famille de fonctions $f_{z_{s}^{s+m}}$ étant dense dans $L^2 (E^{\Z},\mu)$, on en déduit que pour toutes les fonctions $f$ et $g\in L^2 (E^{\Z},\mu)$, \begin{eqnarray*} \lim_{n\to+\infty}\frac{1}{n}\sum_{i=1}^{n}\E((f \circ T^i)g)=\E(f)\E(g). \end{eqnarray*} On peut appliquer ceci à la fonction caractéristique $f=g=1_A$ d'un ensemble invariant $A$. Il vient $\mu(A)=\E(1_A^2)=\E(1_A)\E(1_A)=\mu(A)^2$, d'où $\mu(A)=0$ ou $1$. On conclut que $T$ est ergodique. \end{pf} \begin{ex} Soit $\Xi$ un processus indépendant du temps, i.e. pour tout $n\in\Z$, $X_n =X_1$. Alors $\Xi$ est une chaîne de Markov dont la matrice des probabilités de transition est l'identité. Si $X_1$ n'est pas presque partout constante, la transformation correspondante sur $E^{\Z}$ n'est pas ergodique. \end{ex} En effet, la mesure $\mu$ ne charge que les suites constantes. Si $X_1$ n'est pas presque partout constante, il existe $x\in E$ tel que $0<\P(X_1 =x)<1$. La suite constante $(\ldots,x,x,\ldots)$ est un ensemble invariant qui a pour mesure $\P(X_1=x)$. \sugg34 \sugg44 \subsection{Preuve du Théorème \ref{smb}, cas des chaînes de Markov stationnaires irréductibles} Dans ce cas, $-\log_2 p(x_i |x_1^{i-1})=-\log_2 p(x_i |x_{i-1})=f\circ T^{i-1}((x_n)_{n\in\Z})$ où la fonction $f:E^{\Z}\to\R$ est définie par \begin{eqnarray*} f((x_n)_{n\in\Z})=-\log_2 p(x_1|x_0). \end{eqnarray*} Par conséquent, la quantité qui nous intéresse est une somme de Birkhoff de $f$, à un terme tendant vers 0 près, \begin{eqnarray*} -\frac{1}{n}\log_2 p_{1}^{n}(x_1^n)=\frac{1}{n}\sum_{i=1}^{n-1}f\circ T^{i}((x_n)_{n\in\Z})+\frac{1}{n}\log_2 p_{1}(x_1). \end{eqnarray*} Le Théorème ergodique de Birkhoff affirme que $-\frac{1}{n}\log_2 p_{1}^{n}(x_1^n)$ converge presque sûrement. Si la transformation $T$ est ergodique, la limite est l'espérance $H(\Xi)$. Ceci achève la démonstration, dans le cas particulier des chaînes de Markov stationnaires ergodiques. Or, d'après la Proposition \ref{markoverg}, elles le sont si elles sont irréductibles. \finducours8 \subsection{Cas général} \textcolor{blue}{Dans le cas d'un processus stationnaire général, la quantité qui nous intéresse n'est pas exactement une somme de Birkhoff. On l'encadre par deux variantes qui sont des sommes de Birkhoff. On pose \begin{eqnarray*} f_k ((x_n)_{n\in\Z})=-\log_2 p(x_0 |x_{-1},x_{-2},\ldots,x_{-k}),\quad f_\infty ((x_n)_{n\in\Z})=-\log_2 p(x_0 |x_{-1},x_{-2},\ldots,x_{-k},\ldots). \end{eqnarray*} Alors \begin{eqnarray*} \frac{1}{n}\sum_{i=0}^{n-1}f_{\infty}\circ T^i &=&-\frac{1}{n}\log_2 \prod_{i=0}^{n-1}p(x_i |x_{i-1},x_{i-2},\ldots)\\ &=& -\frac{1}{n}\log_2 p(x_0^{n-1}|x_{-\infty}^{-1}). \end{eqnarray*} Le Théorème ergodique de Birkhoff affirme donc que $-\frac{1}{n}\log_2 p(X_0^{n-1}|X_{-\infty}^{-1})$ converge presque sûrement vers $\E(f_{\infty})$. Par analogie, on note \begin{eqnarray*} p^{k}(x_{0}^{n-1})=p(x_{0}^{k-1})\prod_{i=k}^{n-1}p(x_i |x_{i-k}^{i-1}), \end{eqnarray*} de sorte que $-\frac{1}{n}\log_2 p^{k}(X_{0}^{n-1})$ converge presque sûrement vers $\E(f_k)$ quand $n$ tend vers $+\infty$.} \textcolor{blue}{D'après le Théorème \ref{statentr}, \begin{eqnarray*} \E(f_k)&=&\E(-\log_2 p(X_0|X_{-1},\ldots,X_{-k}))\\ &=&\E(-\log_2 p(X_k|X_{k-1},\ldots,X_{0}))\\ &=&H(X_k|X_{k-1},\ldots,X_{0}) \end{eqnarray*} tend vers $H(\Xi)$ quand $k$ tend vers $+\infty$. Comme $f_{\infty}=\lim_{k\to+\infty}f_{k}$ (cela résulte du théorème de convergence des martingales), le théorème de convergence dominée entraîne que $\E(f_{\infty})=H(\Xi)$. Donc les deux quantités ci-dessus ont la même limite presque sûre.} \textcolor{blue}{On montre enfin que pour tout $k$, \begin{eqnarray*} p^k (x_{0}^{n-1})\leq p(x_0^{n-1})\leq p(x_0^{n-1}|x_{-\infty}^{-1}), \end{eqnarray*} à des termes tendant vers 0 près. En faisant tendre en plus $k$ vers $+\infty$, on conclut que $-\frac{1}{n}\log_2 p(X_0^{n-1})$ converge presque sûrement vers $H(\Xi)$.} \subsection{Appendice : preuve d'une forme faible de la loi des grands nombres} \label{interlude} \begin{prop}\label{lgn} Soit $\Xi=(X_n)_{n\in\N}$ une suite de variables aléatoires indépendantes, de même loi, bornées. Alors la suite $S_n =\frac{1}{n}\sum_{i=1}^{n}X_i$ converge presque sûrement vers la constante $\E(X_0)$. \end{prop} \begin{pf} Quitte à retrancher à $X_n$ son espérance, on peut supposer que $\E(X_n)=0$. Comme les $X_i$ sont bornées, $|X_i|\leq M$, on peut étudier l'espérance de produits comme $\E(X_{i_{1}}X_{i_{2}}X_{i_{3}}X_{i_{4}})$. Si l'un des indices, disons $i_1$, n'apparaît qu'une fois, alors, par indépendance, \begin{eqnarray*} \E(X_{i_{1}}X_{i_{2}}X_{i_{3}}X_{i_{4}})=\E(X_{i_{1}})\E(X_{i_{2}}X_{i_{3}}X_{i_{4}})=0. \end{eqnarray*} On développe \begin{eqnarray*} \E(|S_n|^4)&=&\frac{1}{n^4}\sum_{i_1 ,i_2 ,i_3 ,i_4}\E(X_{i_{1}}X_{i_{2}}X_{i_{3}}X_{i_{4}})\\ &=&\frac{1}{n^4}(\sum_{i}\E(X_i^2)+3\sum_{i_1 0$, la probabilité $\P(|X_n|>\eps)$ tend vers $0$ quand $n$ tend vers $+\infty$. \end{prop} \begin{pf} Soit $Y_n=\min\{|X_n|,1\}$. Cette suite de fonctions converge presque partout vers $0$. Elle est majorée par la constante $1$, qui est intégrable. Par convergence dominée, $\E(Y_n)$ tend vers $0$. Par l'inégalité de Bienaymé-Tchebycheff, $\P(|X_n|>\eps)=\P(|Y_n|>\eps)\leq\frac{1}{\eps}\E(Y_n)$ tend vers $0$ pour tout $\eps>0$. \end{pf} \subsection{A retenir} \begin{itemize} \item L'équipartition asymptotique, et l'interprétation de l'entropie et de l'information mutuelle en termes de suites typiques. \item Le lien entre processus stationnaires et systèmes dynamiques. \item Le Théorème ergodique de Birkhoff, substitut à la loi des grands nombres. \item La notion d'ergodicité. \end{itemize} Il s'agit d'un chapitre théorique, où on passe progressivement de considérations élémentaires sur des probabilités finies à un niveau d'abstraction plus élevé, avec des espaces non discrets, des tribus, et des théorèmes de convergence délicats. \section{Capacité d'un canal de transmission} \label{transmission} On cherche à faire passer des textes au travers d'un canal de transmission imparfait : pour chaque lettre envoyée, il y a une probabilité non nulle que la lettre reçue soit différente. Par un codage judicieux, on peut diminuer cette probabilité d'erreur. Par exemple, en répétant chaque lettre 3 fois, la probabilité d'erreur est élevée au carré, elle devient négligeable. Le prix à payer est un allongement du message, ce que l'on souhaite éviter. Quel est le meilleur compromis entre risque d'erreur et longueur de la transmission ? \subsection{Modélisation d'un canal de transmission} Le canal prend des caractères pris dans un ensemble fini $E_X$ et retourne des caractères pris dans un autre ensemble $E_Y$. On se limite aux canaux {\em sans mémoire}, i.e. tels que la probabilité d'observer un caractère $y$ en sortie ne dépend que du caractère $x$ arrivé en entrée. Le canal est donc entièrement décrit par la matrice de probabilités de transition $P_{xy}=p(y|x)$. Si $X$ est une variable aléatoire à valeurs dans $E_X$, le canal produit à partir de $X$ mis en entrée une variable aléatoire $Y$ à valeurs dans $E_Y$. La loi du couple $(X,Y)$ est donnée par \begin{eqnarray*} \P(Y=y\textrm{ et }X=x)=\P(Y=y|X=x)P(X=x)=P_{xy}p_X (x). \end{eqnarray*} \begin{defi} La {\em capacité} $\kappa$ d'un canal est la borne supérieure des informations mutuelles $I(X;Y)$ sur toutes les variables d'entrée $X$. \end{defi} \begin{ex} Canal binaire symétrique : il reçoit et renvoie des bits, chaque bit est renversé avec probabilité $\alpha$. Alors $\kappa=1-h(\alpha)$. \end{ex} En effet, la matrice des probabilités de transition est $\begin{pmatrix} 1-\alpha & \alpha\\ \alpha & 1-\alpha \end{pmatrix}$. Pour toute variable $X$, \begin{eqnarray*} H(Y|X)=\sum_{x\in E_X}p_X (x)H(Y|X=x)=h(\alpha), \end{eqnarray*} d'où \begin{eqnarray*} I(X;Y)=H(Y)-H(Y|X)=H(Y)-h(\alpha)\leq 1-h(\alpha), \end{eqnarray*} car $Y$ ne prend que deux valeurs, et l'égalité a lieu si la loi de $X$ est uniforme. \sugg15 \finducours9 \begin{ex} Canal effaceur : il reçoit des bits et renvoie des bits ou bien la mention ``illisible''. Chaque bit est rendu illisible avec probabilité $\alpha$. Alors $\kappa=1-\alpha$. \end{ex} En effet, la matrice des probabilités de transition est $\begin{pmatrix} 1-\alpha & 0& \alpha\\ 0 & 1-\alpha & \alpha \end{pmatrix}$. A nouveau, pour toute variable $X$, $H(Y|X)=h(\alpha)$, d'où $I(X;Y)\leq \log_2 3-h(\alpha)$, mais le cas d'égalité n'est jamais réalisé. Il faut trouver une meilleure majoration de $H(Y)$. Soit $Z$ la variable aléatoire qui vaut $1$ quand $Y$ est illisible, $0$ sinon. Alors $Z$ est une fonction de $Y$ donc \begin{eqnarray*} H(Y)&=&H(Y)+H(Z|Y)=H(Y,Z)=H(Z)+H(Y|Z)\\ &=&h(\alpha)+\P(Z=1)H(Y|Z=1)+\P(Z=0)H(Y|Z=0)\\ &=&h(\alpha)+(1-\alpha)H(X)\leq h(\alpha)+1-\alpha, \end{eqnarray*} avec égalité si la loi de $X$ est uniforme. Il vient \begin{eqnarray*} I(X;Y)=H(Y)-H(Y|X)\leq 1-\alpha, \end{eqnarray*} atteint pour $X$ uniformément distribué, et $\kappa=1-\alpha$. \begin{rem} Dans cet exemple, il est intuitivement clair qu'une fraction $\alpha$ de l'information est irrémédiablement perdue. \end{rem} \begin{ex} Machine à écrire défectueuse : quand on frappe sur une touche, la lettre imprimée est ou bien celle voulue ou bien la suivante dans l'ordre alphabétique (cyclique), avec égale probabilité. Alors $\kappa=\log_2 13$. \end{ex} La matrice des probabilités de transition a des $1/2$ sur la diagonale et sur la diagonale qui se trouve juste en dessous. L'entropie relative $H(Y|X)=h(\frac{1}{2})=1$. Par conséquent, $I(X;Y)=H(Y)-H(Y|X)\leq \log_2 (26)-1=\log_2 (13)$, atteint lorsque la loi de $X$ est uniforme. \sugg25 \sugg35 \subsection{Modélisation du codage et du décodage} En amont du canal, il y a un dispositif déterministe qui code le texte original, écrit dans un alphabet $A$, de sorte qu'il puisse être digéré par le canal. Chaque lettre $a\in A$ est codée par une chaîne de $n$ caractères $C(a)\in E_X^{n}$. En aval, il y a un dispositif déterministe qui reconstitue des lettres $g(y_1 ,\ldots,y_n)\in A$ à partir de ce qui sort du canal. L'entier $n$ est appelé la \emph{longueur des blocs}. Ce qui nous intéresse, c'est la {\em probabilité maximale d'erreur} $\max_{a\in A}\lambda_a$, où $\lambda_a$ est la probabilité conditionnelle d'erreur sur la lettre $a$, \begin{eqnarray*} \lambda_a =\P(g(\textrm{sortie})\not=a|\textrm{entrée}=C(a)). \end{eqnarray*} Elle dépend à la fois du canal, du codeur et du décodeur. L'efficacité d'un codeur/décodeur se mesure à son {\em taux} $\frac{\log_2 |A|}{n}$. L'unité est le bit par transmission. \begin{ex} On transmet des bits au travers d'un canal binaire symétrique de probabilité d'erreur $\alpha$. On considère le dispositif qui, en amont du canal, répète chaque bit 3 fois et en aval, choisit dans chaque suite de 3 bits celui qui a la majorité. Son taux vaut $\frac{1}{3}$ bits par transmission. Sa probabilité maximale d'erreur vaut $3\alpha^2 -2\alpha^3$. \end{ex} En effet, il y a erreur lorsque le canal a changé au moins deux des trois bits identiques qui constituent le codage d'une lettre. Ceci se produit avec probabilité $3\alpha^2 (1-\alpha) +\alpha^3 =3\alpha^2 -2\alpha^3$. \begin{defi} On dit qu'un canal autorise un taux de transmission $\tau$ s'il existe une suite de codeurs/décodeurs de taux tendant vers $\tau$ et dont la probabilité maximale d'erreur tend vers 0. \end{defi} \begin{ex} Machine à écrire défectueuse : Il est aisé de voir qu'on peut transmettre 13 lettres sans aucune erreur (il suffit de ne transmettre que les lettres de numéros impairs : A, C, E,...), ce qui donne un taux de transmission au moins égal à $\log_2 (13)$ bits par transmission. \end{ex} Ici, $A$ est l'ensemble des 13 lettres de numéros impairs, et la longueur des bloc vaut 1. Le codage est l'injection de $A$ dans l'alphabet à 26 lettres. Le décodage consiste à remplacer toute lettre lue en sortie par la lettre de numéro impair immédiatement inférieure. La probabilité maximale d'erreur vaut 0. Le taux vaut $\log_2 (13)$. \subsection{Le théorème du codage de canal} Dans l'exemple précédent, le dispositif de codage/décodage est optimal : il réalise le taux de transmission maximal, en vertu du théorème suivant. \begin{theo}[Shannon, 1948]\label{canal} Le taux de transmission maximal autorisé par un canal sans mémoire est égal à sa capacité $\kappa$. Autrement dit, \begin{enumerate} \item Pour toute suite de codeurs/décodeurs dont la probabilité maximale d'erreur tend vers 0, la limite supérieure des taux est $\leq \kappa$. \item Il existe une suite de codeurs/décodeurs dont le taux tend vers $\kappa$ et dont la probabilité maximale d'erreur tend vers 0. \end{enumerate} \end{theo} \textbf{Idée de la preuve}. Soit un dispositif codeur/décodeur utilisant des blocs de longueur $n$ assez grande. Notons $X_1^n$ la variable mise en entrée du canal, après codage d'une variable uniforme, et $Y_1^n$ la variable lue en sortie. Supposons, pour simplifier, que la probabilité maximale d'erreur est nulle. Alors $\log_2 |A|=H(X_1^n)=H(X_1^n|Y_1^n)+I(X_1^n ;Y_1^n)=I(X_1^n ;Y_1^n)\leq nI(X;Y)\leq n\kappa$, car dans ce cas, $X_1^n$ est une fonction de $Y_1^n$. L'argument s'étend au cas général (prise en compte d'une faible probabilité d'erreur). Réciproquement, on montre que par un codage judicieux, on peut forcer le canal, ou plutôt, son extension aux blocs de longueur $n$, à se comporter comme la machine à écrire défectueuse, où il y a un grand sous-ensemble de blocs de longueur $n$ dont les images possibles en sortie constituent des sous-ensembles presque disjoints de $E_Y^n$. Ces blocs, ce sont les suites typiques. D'après la propriété d'équirépartition asymptotique, pour chaque bloc de $E_X^n$, il y a environ $2^{nH(Y|X)}$ suites typiques dans $E_Y^n$, d'égale probabilité. Or le nombre total de suites typiques dans $E_Y^n$ est $2^{nH(Y)}$. Donc le nombre de blocs de $E_X^n$ qui donnent des ensembles disjoints en sortie est au plus $2^{n(H(Y)-H(Y|X))}=2^{nI(X;Y)}$. Cette borne est atteinte par un codage tiré au hasard. Autrement dit, on peut transmettre $2^{nI(X;Y)}$ blocs distincts, ce qui correspond à un taux de transmission $\geq I(X;Y)$ bits par transmission, lorsqu'à l'entrée arrive un texte tiré selon $X$. \finducours{10} \subsection{Deux inégalités} D'abord, quand un canal doit transmettre des blocs de longueur $n$, sa capacité est au pire multipliée par $n$, i.e., sa capacité ``par symbole'' n'augmente pas. \begin{lemme}\label{manytimes} Soient $E_X$ et $E_Y$ les alphabets d'entrée et de sortie d'un canal sans mémoire de capacité $\kappa$. Soit $X_1^n$ une variable aléatoire à valeurs dans $E_X^n$. On fait passer successivement les composantes de $X_1^n$ à travers le canal et on obtient une variable $Y_1^n$ à valeurs dans $E_Y^n$. Alors \begin{eqnarray*} I(X_1^n ;Y_1^n)\leq \sum_{i=1}^{n}I(X_i ;Y_i)\leq n\kappa. \end{eqnarray*} \end{lemme} \begin{pf} \begin{eqnarray*} I(X_1^n ;Y_1^n)&=&H(Y_1^n)-H(Y_1^n |X_1^n)\\ &=&H(Y_1^n)-H(Y_1 |X_1^n)-\sum_{i=2}^{n}H(Y_i |Y_1 ,\ldots,Y_{i-1},X_1^n)\\ &=&H(Y_1^n)-\sum_{i=1}^{n}H(Y_i |X_i), \end{eqnarray*} car $Y_i$ ne dépend que de $X_i$ et, conditionnellement à $X_1^n$, $Y_i$ est indépendant des $Y_j$, $j\not=i$. Il vient \begin{eqnarray*} I(X_1^n ;Y_1^n)&\leq&\sum_{i=1}^{n}H(Y_i)-\sum_{i=1}^{n}H(Y_i |X_i)\\ &=&\sum_{i=1}^{n}H(Y_i)-H(Y_i |X_i)=\sum_{i=1}^{n}I(Y_i ;X_i)\leq n\kappa \end{eqnarray*} par définition de la capacité. \end{pf} Ensuite, une propriété des chaînes de Markov. \begin{lemme}\label{dataprocessing} Soient $X$, $Y$ et $Z$ des variables aléatoires. On suppose que le processus $(X,Y,Z)$ est une chaîne de Markov. Alors \begin{eqnarray*} I(X;Z)\leq I(Y;Z)\quad\textrm{et}\quad I(X;Z)\leq I(X;Y). \end{eqnarray*} \end{lemme} \begin{pf} D'après la propriété de Markov, $X$ est conditionnellement indépendant de $Z$ sachant $Y$, i.e. \begin{eqnarray*} \P(X=x|Y=y,Z=z)=\P(X=x|Y=y). \end{eqnarray*} Autrement dit, \begin{eqnarray*} \frac{p_{(X,Y,Z)}(x,y,z)}{p_{(Y,Z)}(y,z)}=\frac{p_{(X,Y)(x,y)}}{p_{Y}(y)}, \end{eqnarray*} ce qui, par définition de l'information mutuelle conditionnelle, entraîne que $I(X;Z|Y)=0$. D'après la Proposition \ref{infmutchain}, \begin{eqnarray*} I(X;Y,Z)=I(X;Y)+I(X;Z|Y)=I(X;Y), \end{eqnarray*} d'où, en appliquant une seconde fois la Proposition \ref{infmutchain}, \begin{eqnarray*} I(X;Y)=I(X;Y,Z)=I(X;Z)+I(X;Y|Z))\geq I(X;Z). \end{eqnarray*} Comme $I(Z;X|Y)=I(X;Z|Y)=0$, on peut échanger $X$ et $Z$, et conclure que $I(Z;Y)\geq I(X;Z)$. \end{pf} \sugg45 \subsection{Inégalité de Fano} Pour prendre en compte une probabilité d'erreur non nulle mais faible, on utilise une majoration de l'entropie conditionnelle entre une variable et une valeur approchée de cette variable en fonction de la probabilité d'erreur. Il s'agit de l'inégalité de Fano. \begin{prop}[Fano, 1952]\label{fano} Soient $W$ et $\hat{W}$ deux variables aléatoires à valeurs dans un ensemble fini $E_W$. Soit $p_e =\P(W\not=\hat{W})$. Alors \begin{eqnarray*} H(W|\hat{W})\leq h(p_e)+p_e \log_2 |E_W|. \end{eqnarray*} \end{prop} \begin{pf} Soit $Z$ la variable aléatoire qui vaut 1 si $W\not=\hat{W}$ et 0 sinon. $Z$ est une fonction de $(W,\hat{W})$, donc $H(Z|W,\hat{W})=0$. En appliquant de deux façons différentes le Corollaire \ref{entrcondcond}, il vient \begin{eqnarray*} H(W|\hat{W})&=&H(W|\hat{W})+H(Z|W,\hat{W})\\ &=&H(Z,W|\hat{W})\\ &=&H(Z|\hat{W})+H(W|Z,\hat{W}). \end{eqnarray*} D'après le principe ``conditionner diminue l'entropie'' (Proposition \ref{conddiminentr}), $H(Z|\hat{W})\leq H(Z)=h(p_e)$. Sachant que $Z=0$, $W=\hat{W}$, donc $H(W|\hat{W},Z=0)=0$. Sachant que $Z=1$, $H(W|\hat{W},Z=1)\leq H(W)\leq \log_2 |E_W|$. Par définition de l'entropie conditionnelle, \begin{eqnarray*} H(W|Z,\hat{W})=\P(Z=0)H(W|\hat{W},Z=0)+\P(Z=1)H(W|\hat{W},Z=1)\leq p_e \log_2 |E_W|. \end{eqnarray*} On conclut que $H(W|\hat{W})\leq h(p_e)+p_e \log_2 |E_W|$. \end{pf} \subsection{Preuve du Théorème \ref{canal}, sens direct} Supposons donné un canal de capacité $\kappa$ et un dispositif de codage $C:A\to E_X^n$ et de décodage $g:E_Y^n \to A$, de taux $\tau$, utilisant des blocs de taille $n$, pour ce canal. Soit $p_e$ sa probabilité maximale d'erreur. Soit $W$ une variable aléatoire de loi uniforme dans $A$. Soit $X_1^n =C(W)$ la variable mise en entrée du canal, soit $Y_1^n$ la variable observée en sortie, soit $\hat{W}=g(W)$ le résultat du décodage. Alors \begin{eqnarray*} \P(W\not=\hat{W})&=&\sum_{a\in A}\P(W=a)\P(\hat{W}\not=a|W=a)\\ &=&\sum_{a\in A}\P(W=a)\P(g(Y_1^n)\not=a|X_1^n =C(a))\\ &=&\sum_{a\in A}\P(W=a)\lambda_a \\ &\leq&\max_{a\in A}\lambda_a =p_e. \end{eqnarray*} Le processus $(W,X_1^n ,Y_1^n ,\hat{W})$ est une chaîne de Markov. En effet, $X_1^n$ dépend de façon déterministe de $W$, $Y_1^n$ dépend de façon markovienne de $X_1^n$ (car le canal est sans mémoire), et $\hat{W}$ dépend de façon déterministe de $Y_1^n$. D'après le Lemme \ref{dataprocessing}, \begin{eqnarray*} I(W;\hat{W})\leq I(W;Y_1^n)\leq I(X_1^n ;Y_1^n). \end{eqnarray*} D'après le Lemme \ref{manytimes}, \begin{eqnarray*} I(X_1^n ;Y_1^n)\leq n\kappa. \end{eqnarray*} L'inégalité de Fano donne \begin{eqnarray*} H(W|\hat{W})\leq h(p_e)+p_e \log_2 |A|. \end{eqnarray*} \begin{eqnarray*} H(W)&=&H(W|\hat{W})+I(W;\hat{W})\\ &\leq& h(p_e)+p_e \log_2 |A|+I(X_1^n ;Y_1^n)\\ &\leq& 1+p_e \log_2 |A|+n\kappa. \end{eqnarray*} En choisissant $W$ uniformément réparti dans $A$, on trouve \begin{eqnarray*} \tau\leq \kappa+\frac{1}{n}+p_e\tau. \end{eqnarray*} Lorsque la taille des blocs tend vers l'infini et la probabilité maximale d'erreur tend vers 0, on trouve asymptotiquement $\tau\leq \kappa$. \finducours{11} \subsection{Schéma de la preuve du Théorème \ref{canal}, sens réciproque} On montre que si $\tau<\kappa$, il existe un codeur/décodeur de taux de transmission $>\tau$. Le décodage est fondé sur la notion de suite conjointement typique. Soit $C:A\to E_X^n$ le codeur. Avec forte probabilité, le dispositif codeur/canal produit des suites conjointement typiques pour le couple $(X,Y)$. Si on observe $y_1^n$ en sortie, l'entrée $x_1^n$ doit être telle que le couple $(x_1^n,y_1^n)$ est conjointement typique. Le décodage $g(y_1^n)$ doit être un $a\in A$ tel que $(C(a),x_1^n)$ est une suite conjointement typique. Si $|A|<2^{n\tau}$, avec forte probabilité, cet élément $a$ existe et est unique. Le codeur est tiré au hasard. On montre que l'espérance, parmi les choix aléatoires de $C$, de la probabilité maximale d'erreur du dispositif codeur/décodeur, est faible. Il existe donc un codeur dont la probabilité maximale d'erreur est faible. C'est une illustration de ce qu'on appelle parfois la méthode probabiliste en combinatoire. \subsection{Majoration de la probabilité d'erreur} Par hypothèse, il existe une distribution $p_X$ sur $E_X$ (et donc une variable aléatoire $X$ et la variable de sortie $Y$ correspondante) telle que $I(X;Y)>\tau$. Soit $A$ un ensemble à $2^{n\tau}$ éléments. On interprète le fait de tirer indépendamment $2^{n\tau}$ éléments de $E_X^n$ selon la loi produit $p_{X}^{\otimes n}$ comme une application aléatoire $C:A\to E_X^n$. Autrement dit, chaque lettre de $C(a)$, $a\in A$, est tirée indépendamment selon $p_X$, ce qu'on note \begin{eqnarray*} \P_{C}(C(a)=x_1^n)=p_X(x_1)\cdots p_X(x_n), \end{eqnarray*} car l'aléa provient du choix de l'application $C$. De plus les différentes variables $C(a)$, $a\in A$, sont indépendantes. Le procédé de décodage retenu repose sur la notion de suite conjointement typique pour le couple $(X,Y)$. On fixe $\eps<\frac{1}{4}(I(X;Y)-\tau)$. Soit $W$ une variable uniformément répartie dans $A$, soit $\tilde{X}_{1}^{n}=C(W)$ le signal mis en entrée du canal, et $\tilde{Y}_{1}^{n}$ la variable observée en sortie. Le décodage $a=g(\tilde{Y}_1^n)$ est l'élément $a\in A$ tel que $(C(a),\tilde{Y}_{1}^{n})\in T$. Il y a deux sources d'erreurs de décodage. \begin{enumerate} \item Il n'existe aucun $a\in A$ tel que $(C(a),\tilde{Y}_{1}^{n})$ est conjointement typique. Même $a=W$ ne convient pas. Donc la probabilité de cet évènement est majorée par celle de $\mathcal{E}=\{(\tilde{X}_{1}^{n},\tilde{Y}_{1}^{n})\notin T)\}$. \item Il existe plusieurs $a\in A$ tels que $(C(a),\tilde{Y}_{1}^{n})\in T$. Notons cet évènement $\mathcal{F}$. \end{enumerate} Fixons $a_0 \in A$ et raisonnons conditionnellement à l'évènement $\{W=a_0 \}$. L'aléa restant provient du tirage au hasard du codeur $C$. Alors les composantes de $\tilde{X}_1^n$ sont (conditionnellement) indépendantes, de loi $p_X$, et, comme le canal est sans mémoire, les composantes de $\tilde{Y}_1^n$ sont (conditionnellement) indépendantes, de loi $p_Y$. Chacun des couples $(\tilde{X}_i ,\tilde{Y}_i)$ a même loi que $(X,Y)$. D'après la Proposition \ref{jointtypique}, point 1, \begin{eqnarray*} \P_{C}(\mathcal{E}|W=a_0)=\P((X,Y)_1^n \notin T)\end{eqnarray*} tend vers $0$, donc est $<\eps$ pour $n$ assez grand. Pour $a\not=a_0$, les variables conditionnées $\tilde{X}_1^n|W=a$ et $\tilde{X}_1^n|W=a_0$ sont indépendantes. Comme le canal est sans mémoire, il en est de même de $\tilde{Y}_1^n|W=a$ et $\tilde{X}_1^n|W=a_0$. Donc pour tout $a\not=a_0$, la Proposition \ref{jointtypique}, point 3, donne \begin{eqnarray*} \P_{C}((\tilde{X}|W=a,\tilde{Y}|W=a_0)_1^n \in T)\leq 2^{-n(I(X;Y)-3\eps)}\leq 2^{-n(\tau+\eps)}. \end{eqnarray*} En sommant sur les $a\not=a_0$, \begin{eqnarray*} \P(\mathcal{F}|W=a_0)\leq 2^{n\tau}\P((\tilde{X},\tilde{Y})_1^n \in T)\leq 2^{-n(I(X;Y)-\tau-3\eps)}\leq 2^{-n\eps}<\eps \end{eqnarray*} pour $n$ assez grand. En faisant la moyenne sur les tirages $a_0 \in A$ de $W$, il vient \begin{eqnarray*} \E_W (\P_{C}(\mathcal{E}\cup\mathcal{F}))<2\eps \end{eqnarray*} pour $n$ assez grand. On écrit cela $\E_W (\E_{C}(1_{\mathcal{E}\cup\mathcal{F}}))<2\eps$, ou, avec Fubini, $\E_C (\E_{W}(1_{\mathcal{E}\cup\mathcal{F}}))<2\eps$ Il existe donc un codage $C$ qui rend la probabilité moyenne d'erreur $\E_{W}(1_{\mathcal{E}\cup\mathcal{F)}})<2\eps$. On fixe un tel $C$ désormais. Remarquer que \begin{eqnarray*} \E(\lambda_W)=2^{-n\tau}\sum_{a\in A}\lambda_a =\E_{W}(\P(\mathcal{E}\cup\mathcal{F}))<2\eps. \end{eqnarray*} On ordonne les éléments de $A$ par probabilité d'erreur $\lambda_a$ croissante, et on note $A'\subset A$ la première moitié de $A$ pour cette ordre. Alors \begin{eqnarray*} p_e =\max_{a\in A'}\lambda_a < 4\eps. \end{eqnarray*} En effet, $p_e \leq\min_{a\notin A'}\lambda_a$, d'où \begin{eqnarray*} |A|\E(\lambda_W)=\sum_{a\in A'}\lambda_a +\sum_{a\notin A'}\lambda_a \geq|A\setminus A'|p_e =\frac{1}{2}|A|p_e .\end{eqnarray*} On modifie le codage $C$ choisi en remplaçant $A$ par $A'$ et $C$ par sa restriction $C'$ à $A'$. Pour le codage $C'$, la probabilité maximale d'erreur est $p_e <4\eps$. D'autre part, le taux de transmission de $C'$ est $\frac{\log|A'|}{n}=\tau-\frac{1}{n}$. On faisant tendre $n$ vers l'infini, on conclut que $\tau$ constitue un taux de transmission autorisé par le canal. Ceci achève la preuve du Théorème \ref{canal}. \subsection{Postérité} Le Théorème du codage de canal contient tous les ingrédients pour attirer l'attention : \begin{itemize} \item Un problème concret, d'intérêt industriel. \item Une modélisation simple, un résultat d'impossibilité théorique qui, pour une fois, est réaliste. \item Une preuve lumineuse, basée sur des idées heuristiques simples, mais un peu délicate à mettre au point. \item Une preuve probabiliste d'existence, qui ne fournit aucune piste pour construire des codeurs/décodeurs réels, et constitue donc un défi. \end{itemize} Le théorème est à l'origine d'innombrables travaux qui ont produit des codeurs/décodeurs de plus en plus performants. Il ne suffit pas que le taux de transmission soit élevé. Il faut aussi des algorithmes peu coûteux de codage et de décodage. L'algèbre sur les corps finis a été mis à contribution. Les turbo-codes, inventés par des ingénieurs de l'Ecole Nationale Supérieure des Télécommunications, à Lannion, se sont imposés comme solution technologique. Ils équipent aussi bien les missions spatiales de la NASA et de l'Agence Spatiale Européenne que les lecteurs de DVD. Ils constituent aussi une excellente solution théorique : ils réalisent presque la borne du Théorème du codage de canal sur le taux de transmission autorisé pour de vastes classes de canaux. \subsection{A retenir} \begin{itemize} \item L'interprétation de l'information mutuelle comme borne sur le taux de transmission autorisé par un canal. \item Le calcul de la capacité dans quelques exemples. \end{itemize} Il s'agit d'un chapitre pratique, où on utilise les outils du chapitre précédent dans un cas simple (indépendance) pour résoudre un problème concret. \section{Entropie métrique} Un processus stationnaire à valeurs dans un ensemble fini n'est qu'un exemple de transformation préservant une mesure de probabilité. L'entropie par symbole, définie pour l'instant seulement pour les processus stationnaires à valeurs dans des ensembles finis, s'étend à cette situation plus vaste. Reprenons nos deux exemples favoris de processus stationnaires, et traduisons les en termes de dynamique sur un espace probabilisé. \begin{ex}[Décalage de Bernoulli] Soit $p$ une distribution de probabilité sur un ensemble fini $E$. Le décalage sur $E^{\Z}$ muni de la tribu produit et de la mesure produit $\mu=p^{\otimes\Z}$ est appelé \emph{décalage de Bernoulli} $\mathcal{B}(p)$ (\texttt{Bernoulli shift} en anglais). \end{ex} La tribu produit est engendrée par les cylindres de la forme \begin{eqnarray*} C_{z_m^n}=\{\textrm{suites }(x_n)_{n\in\N}\textrm{ telles que }x_m =z_m,\ldots,x_n =z_n\}. \end{eqnarray*} La mesure produit donne au cylindre $C_{z_m^n}$ la mesure $\mu(C_{z_m^n})=p(z_m)\cdots p(z_n)$. \begin{ex}[Décalages de Markov] Soit $p$ une distribution de probabilité sur un ensemble fini $E$. Soit $P$ une matrice stochastique pour laquelle $p$ est stationnaire, i.e. $pP=p$. Le \emph{décalage de Markov} $\mathcal{M}(p,P)$ (\texttt{Markov shift} en anglais) est le décalage sur $E^{\Z}$ muni de la tribu produit et de la mesure $\mu$ telle que \begin{eqnarray*} \mu(C_{z_m^n})=p(z_m)P_{z_{m}z_{m+1}}\cdots P_{z_{n-1}z_{n}}. \end{eqnarray*} \end{ex} Evidemment, le décalage de Bernoulli est un cas particulier de décalage de Markov. \subsection{Entropie d'une transformation préservant la mesure} Voici la démarche qui conduit à la généralisation. A une transformation $T$ préservant une mesure de probabilité $\mu$ sur un espace $\Omega$ sont associés des processus stationnaires à valeurs dans des ensembles finis. Il suffit pour cela de choisir une partition finie $\alpha=(A_x)_{x\in E_{\alpha}}$ de $\Omega$, et de poser \begin{eqnarray*} X_n (\omega)=x\textrm{ si }T^n (\omega)\in A_x . \end{eqnarray*} C'est bien un processus stationnaire : pour tous $k\in\N$ et $n\in\Z$, la loi jointe satisfait \begin{eqnarray*} \P(X_{n}^{n+k} =x_{0}^{k})&=&\P(T^{n}(\omega)\in A_{x_0},\ldots,T^{n+k}(\omega)\in A_{x_{k}})\\ &=&\mu(T^{-n}(A_{x_0})\cap\cdots\cap T^{-n-k}A_{x_{k}})\\ &=&\mu(T^{-n}\left(A_{x_0}\cap\cdots\cap T^{-k}A_{x_{k}}\right))\\ &=&\mu\left(A_{x_0}\cap\cdots\cap T^{-k}A_{x_{k}}\right)\\ &=&\P(\omega\in A_{x_0},\ldots,T^{k}(\omega)\in A_{x_{k}})\\ &=&\P(X_{0}^{k} =x_{0}^{k}). \end{eqnarray*} On note $\Xi_{\alpha}$ ce processus. Il correspond à ce qu'on peut extraire de $T$ à l'aide d'un appareil de mesure, qui ne possède forcément qu'un nombre fini de graduations. Pour affiner la mesure, il faut des appareils de plus en plus précis, donc des partitions de plus en plus fines. Cela conduit à la définition suivante. \begin{defi} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $T:\Omega\to\Omega$ une application qui préserve la mesure. Etant donné une partition mesurable finie $\alpha=(A_x)_{x\in E_{\alpha}}$ de $\Omega$, on note $\Xi_{\alpha}$ le processus stationnaire correspondant. On appelle \emph{entropie métrique} de $T$ la borne supérieure \begin{eqnarray*} h_{\mu}(T)=\sup_{\alpha}H(\Xi_{\alpha}), \end{eqnarray*} prise sur toutes les partitions mesurables finies de $\Omega$. \end{defi} On abrégera souvent entropie métrique en entropie, quand le contexte exclut toute confusion. \subsection{Entropie des partitions} On peut s'affranchir de la notion de processus stationnaire dans la définition de l'entropie métrique. En effet, les lois jointes ne sont autres que les probabilités d'évènements engendrés par la transformation $T$ à partir de la partition $\alpha$. \begin{defi} Soient $\alpha=(A_x)_{x\in E_{\alpha}}$ et $\beta=(B_y)_{y\in E_{\beta}}$ deux partitions finies d'un espace probabilisé $\Omega$, et $T:\Omega\to\Omega$ une application qui préserve la mesure. \begin{itemize} \item On note $T\alpha$ la partition dont les pièces sont les $(T^{-1}A_x)_{x\in E_{\alpha}}$. \item On dit que $\beta$ \emph{raffine} $\alpha$, et on note $\alpha\preceq\beta$, si chaque pièce de $\beta$ est contenue dans une pièce de $\alpha$. \item On note $\alpha\vee\beta$ la partition dont les pièces sont les $(A_x \cap B_y)_{(x,y)\in E_{\alpha}\times E_{\beta}}$. Cette opération est commutative et associative. \item On appelle entropie de la partition $\alpha$ le nombre $H(\alpha)=-\sum_{x\in E}\mu(A_x)\log_2 (\mu(A_x))$. \item On appelle entropie conditionnelle des partitions $\alpha$ et $\beta$ le nombre \begin{eqnarray*} H(\alpha|\beta)=-\sum_{(x,y)\in E_{\beta}}\mu(A_x \cap B_y)\log_2 \frac{\mu(A_x \cap B_y)}{\mu(B_y)}. \end{eqnarray*} \end{itemize} \end{defi} \begin{lemme} L'entropie des partitions a les propriétés suivantes. \begin{itemize} \item $0\leq H(\alpha|\beta)\leq H(\alpha)$. \item $H(\alpha\vee\beta)=H(\beta)+H(\alpha|\beta)$. \item $H(\alpha\vee\beta)\leq H(\alpha)+H(\beta)$. \item $\alpha\preceq\alpha'$ $\Rightarrow$ $H(\alpha)\leq H(\alpha')$ et $H(\alpha|\beta)\leq H(\alpha'|\beta)$. \item Si $T:\Omega\to\Omega$ préserve la mesure, $T(\alpha\vee\beta)=T(\alpha)\vee T(\beta)$, $H(\alpha|\beta)=H(T\alpha|T\beta)$. \end{itemize} \end{lemme} \begin{pf} $H(\alpha)=H(f_{\alpha})$ où la variable aléatoire $f_{\alpha}:\Omega\to E_{\alpha}$ vaut $x$ sur $A_x$. \end{pf} \sugg16 \begin{prop} Soit $T:\Omega\to\Omega$ une application qui préserve la mesure. Pour toute partition mesurable finie $\alpha$, \begin{eqnarray*} H(\Xi_{\alpha})=\lim_{n\to\infty}\frac{1}{n}H(\alpha\vee T\alpha\vee\cdots\vee T^{n-1}\alpha). \end{eqnarray*} \end{prop} \begin{pf} Par construction, la variable $X_{\alpha,n}$ du processus stationnaire $\Xi_{\alpha}$ est $f_{T^{n}\alpha}$. Par conséquent, l'entropie de la $n$-ème partition engendrée par $T$ est égale à l'entropie jointe, \begin{eqnarray*} H(\alpha\vee T\alpha\vee\cdots\vee T^{n-1}\alpha)=H(X_{\alpha,1},\ldots,X_{\alpha,n}). \end{eqnarray*} \end{pf} \begin{ex}[Décalage de Bernoulli] Soit $T=\mathcal{B}(p)$ un décalage de Bernoulli sur $E^{\Z}$. Soit $\alpha$ la partition telle que $A_x =\{$suites $(x_n)_{n\in\Z}$ telles que $x_0 =x\}$, i.e. la partition induite par la projection sur un facteur. Le processus $\Xi_{\alpha}$ est une suite de variables indépendantes de loi $p$, donc $H(\Xi_{\alpha})=H(p)$. \end{ex} \begin{ex}[Décalage de Markov] Soit $T=\mathcal{M}(p,P)$ un décalage de Markov sur $E^{\Z}$. Soit $\alpha$ la partition induite par la projection sur un facteur. Le processus $\Xi_{\alpha}$ est une chaîne de Markov stationnaire de matrice de probabilités de transition $P$ et de distribution stationnaire $p$, donc $H(\Xi_{\alpha})=-\sum_{x,\,y\in E}p(x)P_{xy}\log_2 (P_{xy})$. \end{ex} \subsection{Partitions génératrices} La définition de l'entropie métrique par une borne supérieure est une belle construction théorique, qui paraît parfaitement incalculable. Il n'en est rien. Il se trouve que les ``bonnes'' partitions $\alpha$ donnent toutes la même valeur de $H(\Xi_{\alpha})$. \begin{nota} Soit $\alpha$ une partition finie d'un ensemble $\Omega$. On note $\alpha_{m}^{n}=T^{m}\alpha\vee\cdots\vee T^{n}\alpha$. On note $\alpha_{-\infty}^{n}$ la tribu engendrée par les pièces des partitions $\alpha_{m}^{n}$, $m\leq n$. Et de même, $\alpha_{-\infty}^{\infty}$ est la tribu engendrée par les pièces de toutes les partitions $\alpha_{m}^{n}$, $m$, $n\in\Z$. \end{nota} \sugg26 \sugg36 \begin{ex}[Tribu produit] Soit $E$ un ensemble fini, $\Omega=E^{\Z}$, $T=$ décalage, $\alpha$ la partition $A_x =\{$suites $(x_n)_{n\in\Z}$ telles que $x_0 =x\}$ induite par la projection sur un facteur. La tribu produit sur $\Omega$ coïncide avec $\alpha_{-\infty}^{\infty}$. \end{ex} En effet, pour tout $(z_m,\ldots,z_n)\in E^{n-m+1}$, \begin{eqnarray*} C_{z_1^n}=T^{-m}A_{z_m}\cap\cdots\cap T^{-n}A_{z_n}, \end{eqnarray*} donc $\alpha_{m}^n$ coïncide avec l'ensemble des cylindres sur les coordonnées $m$ à $n$. On conclut par définition de la tribu produit. \begin{defi} \label{defgeneratrice} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $T:\Omega\to\Omega$ une application qui préserve la mesure. On dit qu'une partition mesurable finie $\alpha$ de $\Omega$ est {\em génératrice} pour $T$ si $\mathcal{B}=\alpha_{-\infty}^{\infty}$ aux ensembles de mesure nulle près. \end{defi} \begin{ex} Pour un décalage de Bernoulli ou, plus généralement, de Markov, la partition induite par la projection sur un facteur est génératrice. \end{ex} \finducours{12} Le lemme suivant aide à comprendre ce que signifie $\alpha_{-\infty}^{\infty}$, et par conséquent, la notion de partition génératrice. \begin{lemme}\label{tribu} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $\beta_0 \preceq \cdots\preceq\beta_n \preceq$ une suite de partitions mesurables finies de $\Omega$, de plus en plus fines. Soit $\beta_{\infty}$, la tribu engendrée par toutes les $\beta_n$, $n\in\N$. Si $C\in\beta_{\infty}$, alors pour tout $\delta>0$, il existe $n$ et un élément $B$ de la tribu engendrée par $\beta_n$ tel que $\mu(B\Delta C)<\delta$. \end{lemme} \begin{pf} Notons $\beta_{\to}$ la famille de toutes les intersections $B_{1}\cap\cdots B_{n}\cap\cdots$ où $B_i$ appartient à la tribu engendrée par $\beta_i$. Soit $\mathcal{T}$ l'ensemble des réunions dénombrables d'éléments de $\beta_{\to}$. On montre d'abord que $\beta_{\infty}=\mathcal{T}$. Par construction, $T$ est stable par réunion dénombrable. Si $A\in\beta_{\to}$, le complémentaire $A^c$ est une réunion dénombrable de complémentaires $B_i^c$. Chaque $B_i^c$ appartient à la tribu engendrée par $\beta_i$, donc à $\beta_{\to}$. Par conséquent, $A^c \in\mathcal{T}$, i.e. $\mathcal{T}$ est stable par complémentaire. Cela prouve que $\mathcal{T}$ est une tribu. Pour tout $i$, elle contient la tribu engendrée par $\beta_i$, donc $\mathcal{T}$ contient $\beta_{\infty}$. Réciproquement, comme $\beta_{\infty}$ est stable par intersection dénombrable, $\beta_{\to}\subset\beta_{\infty}$, et comme $\beta_{\infty}$ est stable par réunion dénombrable, $\mathcal{T}\subset\beta_{\infty}$. On conclut que $\mathcal{T}=\beta_{\infty}$. Soit $C\in \beta_{\infty}$. On vient de montrer que $C=\bigcup_{k\in\N}I_k$ où $I_k$ est une intersection $I_k =\bigcap_{i\in\N}B_{k,i}$ d'ensembles $B_{k,i}$ appartenant à la tribu engendrée par $\beta_i$. Il existe $\ell$ tel que $\mu(\bigcup_{k\geq\ell}I_k)<\frac{\delta}{2}$. Pour chaque $k<\ell$, il existe $i(k)$ tel que $\mu(\bigcap_{i\leq i(k)}B_{k,i}\setminus I_k)<\frac{\delta}{2\ell}$. Soit $B=\bigcup_{k<\ell}\bigcap_{i\leq i(k)}B_{k,i}$. Alors $\mu(B\Delta C)<\delta$ et $B$ appartient à la tribu engendrée par $\beta_n$, pour $n=\max_{k<\ell}i(k)$. \end{pf} \subsection{Calcul de l'entropie métrique} \begin{theo}[Kolmogorov, Sinai 1958]\label{KS} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $T:\Omega\to\Omega$ une application qui préserve la mesure. Soit $\alpha$ une partition mesurable finie qui est génératrice pour $T$. Alors \begin{eqnarray*} h_{\mu}(T)=H(\Xi_{\alpha}). \end{eqnarray*} \end{theo} \begin{pf} La preuve que voici, dûe à Yakov Sinai, procède en trois étapes. \begin{enumerate} \item Soit $\Phi$ l'ensemble des partitions mesurables finies de $\Omega$ modulo ensembles de mesure nulle. Muni de la distance de l'entropie conditionnelle, $\Phi$ est un espace métrique sur lequel la fonction $\beta\mapsto H(\Xi_{\beta})$ est continue. \item Soit $\Psi\subset\Phi$ le sous-ensemble défini par \begin{eqnarray*} \Psi=\{\beta\in\Phi\,;\,\exists k \textrm{ tel que }\beta\preceq\alpha_{-k}^{k}\}. \end{eqnarray*} On montre que pour tout $\beta\in\Psi$, $H(\Xi_{\beta})\leq H(\Xi_{\alpha})$. \item Sous l'hypothèse que $\alpha$ est génératrice, on montre que $\Psi$ est dense dans $\Phi$. \end{enumerate} 1. Pour l'étape 1, on renvoie à l'Exercice 3 du TD6. 2. Soit $\beta$ une partition mesurable finie. Supposons là moins fine que la partition $\alpha_{-k}^{k}$, i.e. $\beta\preceq\alpha_{-k}^{k}$. Alors \begin{eqnarray*} \beta_{-n}^{n}\preceq(\alpha_{-k}^{k})_{-n}^{n}=\alpha_{-n-k}^{n+k}, \end{eqnarray*} (comparer à l'exercice 2 du TD6), d'où \begin{eqnarray*} \frac{1}{2n+1}H(\beta_{1}^{2n+1})&=&\frac{1}{2n+1}H(\beta_{-n}^{n})\\ &\leq&\frac{1}{2n+1}H(\alpha_{-n-k}^{n+k})=\frac{2n+2k+1}{2n+1}\frac{1}{2n+2k+1}H(\alpha_{1}^{2n+2k+1}), \end{eqnarray*} et, en faisant tendre $n$ vers l'infini, $H(\Xi_{\beta})\leq H(\Xi_{\alpha})$. 3. Soit $\gamma\in\Phi$ une partition finie dont toutes les pièces ont une mesure non nulle. Par hypothèse, chaque pièce $C_z$, $z\in E_{\gamma}$ de $\gamma$ appartient à la tribu engendrée par les pièces de tous les $\alpha_{-n}^{n}$, à un ensemble de mesure nulle près. D'après le Lemme \ref{tribu}, cela entraîne que pour tout $\delta>0$, il existe $n$ et pour tout $z$, il existe un élément $C'_z$ de la tribu engendrée par $\alpha_{-n}^{n}$ tel que $\mu(C_z \Delta C'_z)<\delta$. Soit $\beta$ la partition engendrée par les $C'_z$, $z\in E_{\gamma}$. Les pièces sont toutes les intersections de $C'_z$. Pour chaque $z$, il y a une grosse pièce, $B_z =C'_z \setminus\bigcup_{z'\not=z'}C'_{z'}$, et de petites pièces de mesure $<\delta$, donc $E_{\gamma}\subset E_{\beta}$. Les variables aléatoires $f_{\gamma}$ et $f_{\beta}$ ne diffèrent que sur un ensemble de probabilité $p_e <|E_{\gamma}|\delta$. L'inégalité de Fano \ref{fano} entraîne que \begin{eqnarray*} \rho(\beta,\gamma)=H(\gamma|\beta)+H(\beta|\gamma)\leq 2h(p_e)+2p_e \log_2 |E_\gamma|. \end{eqnarray*} On conclut qu'en choisissant $\delta$ assez petit, on peut rendre $\rho(\beta,\gamma)$ arbitrairement petit. Par construction, $\beta\preceq\alpha_{-n}^{n}$ donc $\beta\in\Psi$. Cela prouve la densité de $\Psi$ dans $\Phi$, et permet d'étendre par continuité l'inégalité $H(\Xi_{\beta})\leq H(\Xi_{\alpha})$ prouvée pour $\beta\in\Psi$ à $\Phi$ tout entier. On conclut que $h_{\mu}(T)=\max_{\beta\in\Phi}H(\Xi_{\beta})=H(\Xi_{\alpha})$. \end{pf} \begin{cor} L'entropie du décalage de Bernoulli $\mathcal{B}(p)$ vaut $H(p)$. L'entropie du décalage de Markov $\mathcal{M}(p,P)$ vaut $-\sum_{x,\,y\in E}p(x)P_{xy}\log_2 (P_{xy})$. \end{cor} \subsection{Rotations du cercle} Il existe des transformations d'entropie nulle. \begin{prop} Soit $T:x\mapsto x+\theta$ une rotation d'angle irrationnel de $\R/\Z$, et $\lambda$ la mesure de Lebesgue. Alors $h_{\lambda}(T)=0$. \end{prop} \begin{pf} On montre que la partition en 2 morceaux $\alpha=\{[0,\frac{1}{2}[,[\frac{1}{2},1[\}$ est génératrice. On utilise la densité des orbites (Exercice 6 du TD 4). Pour tout intervalle $[a,b]$ et tout $\epsilon>0$, il existe des entiers $n$ et $m$ tels que $-n\theta\in]a-\eps,a[$, $-m\theta\in]b,b+\eps[$. Alors l'intersection des intervalles $T^{-n}[0,\frac{1}{2}[\cap T^{-m}[\frac{1}{2},1[=[-n\theta,-m\theta[$ est $[a,b]$. Ceci prouve que $[a,b]\in\alpha_{-\infty}^{\infty}$. Comme la tribu engendrée par les intervalles est la tribu borélienne $\mathcal{B}$, $\alpha_{-\infty}^{\infty}=\mathcal{B}$, et $\alpha$ est génératrice. Le nombre de pièces dans la partition $\alpha_1^n$ est $2n$. En effet, couper une partition selon deux points opposés ne divise que deux pièces de la partition, donc $|\alpha_1^{n+1}|=|\alpha_1^n|+2$. Par conséquent, $H(\alpha_1^n)\leq \log_2 |\alpha_1^n|=\log_2 (2n)=o(n)$, donc $H(\Xi_{\alpha})=0$, et, avec le théorème \ref{KS}, $h_{\lambda}(T)=0$. \end{pf} \subsection{Invariance de l'entropie} \begin{defi} Soient $(\Omega,\mathcal{B},\mu)$ et $(\Omega',\mathcal{B}',\mu')$ des espaces probabilisés. On dit que deux transformations préservant la mesure $T:\Omega\to\Omega$ et $\Omega'\to\Omega'$ sont {\em isomorphes} ou {\em conjuguées} s'il existe une transformation préservant la mesure $\phi:\Omega\to\Omega'$ telle que $T'\circ\phi=\phi\circ T$ presque partout. \end{defi} \begin{ex}\label{boulanger} Soit $\phi:\{0,1\}^{\Z}\to[0,2]\times[0,1]$, définie pour $z=(z_n)_{n\in\Z}$ par \begin{eqnarray*} \phi(x)=(\sum_{n=0}^{\infty}z_{n}2^{-n},\sum_{n=-\infty}^{-1}z_{n}2^{n}). \end{eqnarray*} Alors $\phi$ conjugue le décalage à la transformation $T':[0,2]\times[0,1]\to[0,2]\times[0,1]$, définie pour $x\in[0,2]$ et $y\in[0,1]$, par \begin{eqnarray*} T'(x,y)=\begin{cases} (2x,\frac{1}{2}y) & \text{ si }x\leq 1, \\ (2x-2,\frac{1}{2}(1+y)) & \text{ si }x>1. \end{cases} \end{eqnarray*} \end{ex} Soit $w=T(z)$, i.e. $w_{n}=z_{n+1}$. Soit $(x,y)=\phi(z)$. Si $z_0 =0$, alors $x\leq 1$. Si $z_0 =1$, alors $x\geq 1$. \begin{eqnarray*} \phi(T(z))&=&(\sum_{n=0}^{\infty}z_{n+1}2^{-n},\sum_{n=-\infty}^{-1}z_{n+1}2^{n})\\ &=&(\sum_{m=1}^{\infty}z_{m}2^{-(m-1)},\sum_{m=-\infty}^{0}z_{m}2^{m-1})\\ &=&(-2z_0+2\sum_{m=0}^{\infty}z_{m}2^{-m},\frac{z_0}{2}+\frac{1}{2}\sum_{m=-\infty}^{-1}z_{m}2^{m})\\ &=&(-2z_0+2x,\frac{z_0}{2}+\frac{1}{2}y)\\ &=&T'(x,y)=T'(\phi(z)), \end{eqnarray*} sauf peut-être lorsque $x=1$. Enfin, soit $\mu$ la mesure produit $p^{\otimes\Z}$ où $p$ est la distribution uniforme sur $\{0,1\}$. Alors $\phi_*\mu=\frac{1}{2}\lambda$ où $\lambda$ désigne la mesure de Lebesgue sur $[0,2]\times[0,1]$. En effet, étant donnés $m\leq 0\leq n\in\Z$ et $z_{m},\ldots,z_{n}\in\{0,1\}$, prolongeons $z$ à $\Z$ par $0$ et posons $(x_m,y_n)=\phi(z)$. Le cylindre $C_{z_{m},\ldots,z_{n}}$, de mesure $2^{-n+m-1}$, est envoyé sur le rectangle $[x_m,x_m +2^{m}]\times[y_n,y_n+2^{-n}]$, de mesure de Lebesgue $2^{-n+m}$. $T'$ est parfois désignée sous le nom de {\em transformation du boulanger}, car elle rappelle le geste de l'artisan qui partage une boule de pâte en deux parts, en pose une sur l'autre et presse pour obtenir à nouveau une boule. \begin{prop} Si deux transformations sont isomorphes, et si l'une est ergodique, il en est de même de l'autre. \end{prop} \begin{prop} Deux transformations isomorphes ont même entropie. \end{prop} En effet, un isomorphisme envoie classes de partitions modulo ensembles de mesure nulle sur classes de partitions modulo ensembles de mesure nulle, et, par naturalité, $H(\Xi_{\phi(\alpha)})=H(\Xi_{\alpha})$, donc $h_{\mu'}(T')=h_{\mu}(T)$. \begin{cor} Deux décalages de Bernoulli, ou, plus généralement, de Markov, d'entropies dif\-fé\-rentes ne sont pas isomorphes. \end{cor} \begin{ex} La transformation du boulanger, définie dans l'exemple \ref{boulanger}, est ergodique et son entropie vaut $1$. \end{ex} Nous ne démontrerons pas le théorème, assez difficile, suivant. \begin{theo}[D. Ornstein 1970] Deux décalages de Bernoulli qui ont la même entropie sont isomorphes. \end{theo} On dit que l'entropie est un {\em invariant d'isomorphisme complet} pour les décalages de Bernoulli. L'intérêt de cette classe est que de nombreux systèmes dynamiques d'intérêt courant sont isomorphes, du point de vue mesurable, à des décalages de Bernoulli. \begin{theo}[Y. Katznelson, 1971] Soit $A\in Gl(n,\Z)$ une matrice entière inversible. On suppose que les valeurs propres de $A$ ne sont pas des racines de l'unité. Alors la transformation $T_A$ induite sur le tore est conjuguée à un décalage de Bernoulli. \end{theo} En revanche, une rotation du cercle n'est pas conjuguée à un décalage de Bernoulli, puisque son entropie est nulle. \subsection{Automorphismes du tore} Le tore, c'est l'espace quotient $\R^n/\Z^n$. C'est un groupe. On admet que ses automorphismes continus proviennent d'homomorphismes continus du groupe $\R^n$ dans lui-même. Ceux-ci coïncident avec les applications linéaires de $\R^n$ (cette étape n'est pas difficile). Une bijection linéaire $A:\R^n \to\R^n$ passe au quotient si et seulement si $A\Z^n \subset\Z^n$, i.e. si la matrice de $A$ est à coefficients entiers. C'est une bijection du quotient si et seulement si $A^{-1}$ est aussi à coefficients entiers, ce qui signifie que le déterminant de $A$ vaut $1$ ou $-1$. Le groupe des matrices $n\times n$ entières de déterminant $\pm 1$ est noté $Gl(n,\Z)$. La formule de changement de variable montre que les bijections linéaires associées à ces matrices préservent la mesure de Lebesgue de $\R^n$. Elles induisent des bijections de $\R^n/\Z^n$ qui préserve la mesure de probabilité naturelle sur le quotient, identifié au cube unité de $\R^n$. \begin{prop} \label{ergodtore} Soit $T$ l'automorphisme de $X=\R^n/\Z^n$ associé à la matrice $A\in Gl(n,\Z)$. Alors $T$ est ergodique si et seulement si aucune des valeurs propres de $A$ n'est une racine de l'unité. \end{prop} \begin{pf} On utilise le développement en série de Fourier des fonctions sur $\R^n/\Z^n$. Si $f\in L^2(\R^n/\Z^n)$, alors $f$ est la somme de la série \begin{eqnarray*} f=\sum_{\xi\in\Z^n}\hat{f}_{\xi}e_{\xi} \end{eqnarray*} où la famille de fonctions $e_{\xi}(x)=e^{2i\pi\xi\cdot x}$ est orthonormée pour le produit scalaire (hermitien) $L^2$. On remarque que $e_{\xi}\circ T=e_{A^{\top}\xi}$. Si l'une des valeurs propres de $A$ est une racine $k$-ème de l'unité, alors $1$ est valeur propre de $A^k$. Le système linéaire à coefficients entiers $(A^k)^{\top}\xi=\xi$ possède une solution non nulle rationnelle, donc une solution non nulle entière $\xi$. Alors la fonction $e_{\xi}$ est $T^k$-invariante. La fonction \begin{eqnarray*} f:X\to\C,\quad f=\sum_{j=1}^{k}e_{\xi}\circ T^j , \end{eqnarray*} est $T$-invariante mais n'est pas presque partout constante (elle a des coefficients de Fourier non nuls). Cela prouve que $T$ n'est pas ergodique. Réciproquement, supposons qu'aucune valeur propre de $A$ n'est une racine de l'unité. Alors pour tous vecteurs entiers non nuls $\xi$ et $\xi'$, et tout $k$ assez grand, $(A^{\top})^k \xi\not=\xi'$. En effet, sinon, il existe $k\not=k'$ tels que $(A^{\top})^k \xi=\xi'=(A^{\top})^{k'} \xi$. Alors $(A^{\top})^{k'-k} \xi=\xi$, $1$ est valeur propre d'une puissance de $A^{\top}$, donc $A$ a une valeur propre qui est une racine de l'unité, contradiction. Par conséquent, pour tout $\xi$, $\xi'$ et $k$ assez grand, le produit scalaire $\langle e_{(A^{\top})^k \xi},e_{\xi'}\rangle=0$. En particulier, \begin{eqnarray*} \lim_{k\to\infty}\langle e_{\xi}\circ T^k ,e_{\xi'}\rangle=0. \end{eqnarray*} C'est évidemment encore vrai pour des combinaisons linéaires finies de fonctions $e_\xi$. D'après la décomposition de Fourier, ce sous-espace vectoriel est dense dans $L^2(\R^n/\Z^n)$. Comme dans la preuve de la Proposition \ref{markoverg}, on en déduit que pour tous $f$, $g\in L^2(\R^n/\Z^n)$, \begin{eqnarray*} \lim_{k\to\infty}\langle f\circ T^k , g \rangle=0, \end{eqnarray*} et l'ergodicité de $T$ en résulte. \end{pf} \begin{theo}[Ya. Sinai, 1959] Soit $A\in Gl(n,\Z)$ une matrice entière inversible. On suppose que les valeurs propres de $A$ ne sont pas des racines de l'unité. Soient $|\lambda_{1}|\geq\cdots\geq|\lambda_{n}|$ les modules des valeurs propres de $A$. Soient $|\lambda_{1}|\geq\cdots\geq|\lambda_{k}|$ ceux de ces nombres qui sont $>1$. L'entropie métrique de la transformation $T_A$ correspondante vaut \begin{eqnarray*} h(T_A)=\sum_{i=1}^{k}\log_2 |\lambda_{k}|. \end{eqnarray*} \end{theo} \finducours{13} \begin{pf} On donne la preuve lorsque $n=2$. Dans ce cas, $T_A$ est ergodique si et seulement si ses valeurs propres sont réelles et distinctes (en effet, si elles sont non réelles, les valeurs propres sont conjuguées, de module 1 et de partie réelle entière ou demi-entière, donc des racines cubiques ou quatrièmes de l'unité). Les valeurs propres $\lambda_1 > \lambda_2 =1/\lambda_1$ sont irrationnelles. On construit une partition finie $\alpha$. Chaque pièce est l'image dans $\R^2/\Z^2$ d'un parallélogramme dont les côtés sont parallèles aux deux espaces propres de $A$. Pour la construire on part de deux longs segments de droites propres issus de l'origine dans $\R^2$. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(1).pdf} \end{center} \vskip-2cm Leurs images $\gamma_1$ et $\gamma_2$ dans le tore ont une extrémité commune, à l'origine. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(2).pdf} \end{center} \vskip-2cm Si l'autre extrémité de $\gamma_1$ n'est pas sur $\gamma_2$, on prolonge $\gamma_1$ jusqu'à ce qu'elle le soit. On fait de même avec $\gamma_2$. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(3).pdf} \end{center} \vskip-2cm L'image réciproque du réseau de lignes obtenu divise le plan en polygones qui ont un sommet rentrant aux points entiers. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(4).pdf} \end{center} \vskip-2cm Pour y remédier, on prolonge $\gamma_1$ dans la direction opposée, au-delà de l'origine, jusqu'à ce que son extrémité soit sur $\gamma_2$, et on fait de même pour $\gamma_2$. De la sorte, on obtient un réseau de lignes sur le tore, qui définit une partition $\alpha$ (à ensembles de mesure nulle près). \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(7).pdf} \end{center} \vskip-2cm Cette fois, l'image réciproque du réseau dans le plan divise le plan en polygones localement convexes (donc convexes) à côtés parallèles aux droites propres, ce sont des parallélogrammes. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(6).pdf} \end{center} \vskip-2cm L'image réciproque par $A^n$ d'un parallélogramme à côtés parallèles aux droites propres est un parallélogram\-me à côtés parallèles aux droites propres, mais $\lambda_1^{-n}$ fois plus court dans la direction de $\gamma_1$ et $\lambda_2^{-n}$ fois plus long dans la direction de $\gamma_2$. Soit $L_i$ (resp. $\ell_i$) la plus grande (resp. plus petite) longueur des côtés parallèles à $\gamma_i$ des pièces de $\alpha$. Alors les longueurs correspondantes dans la partition $T_{A^n} \alpha$ sont comprises entre $\ell_i \lambda_i^{-n}$ et $L_i \lambda_i^{-n}$. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(9).pdf}\hskip-2cm \includegraphics[width=2in]{parallelogrammes(12).pdf} \vskip-2cm Les partitions $T_A \alpha$ et $\alpha\vee T_A \alpha$. \end{center} Notons $\beta_i$ la réunion des lignes parallèles à $\gamma_i$ (son image réciproque dans le plan est la réunion des images de $\gamma_1$ par les translations entières). Comme $\gamma_1 \subset A^{-1}(\gamma_1)$ et $A^{-1}(\gamma_2)\subset \gamma_2$, $\beta_1 \subset A^{-1}(\beta_1)$ et $A^{-1}(\beta_2)\subset \beta_2$. Par conséquent, dans la partition $\alpha\vee T_A \alpha$, chaque parallélogramme est divisé en parallélogrammes de même longueur (dans la direction de $\gamma_1$), mais de largeur (dans la direction de $\gamma_2$) divisée par un facteur de l'ordre de $\lambda_1$. De même, dans la partition $\alpha\vee T_A \alpha\vee \cdots \vee (T_A)^{n-1}\alpha$, les pièces sont des parallélogrammes de longueurs (dans la direction de $\gamma_1$) comprises entre $\ell_1$ et $L_1$ et de largeurs (dans la direction de $\gamma_2$) comprises entre $\ell_2 \lambda_2^{-n}$ et $L_2 \lambda_2^{-n}$. Il en résulte que leurs aires sont comprises entre $\ell_1\ell_2 \lambda_1^{-n}$ et $L_1 L_2 \lambda_1^{-n}$. L'entropie satisfait \begin{eqnarray*} H(\alpha\vee T_A \alpha\vee \cdots \vee (T_A)^{n-1}\alpha)&=& \sum_{B}-\mu(B)\log2\mu(B)\\ &\geq &\sum_{B}-\mu(B)\log2(L_1 L_2 \lambda_1^{-n})\\ &\geq&n\log_2(\lambda_1)-\log_2(L_1L_2). \end{eqnarray*} De même, \begin{eqnarray*} H(\alpha\vee T_A \alpha\vee \cdots \vee (T_A)^{n-1}\alpha)&=& \sum_{B}-\mu(B)\log2\mu(B)\\ &\leq &\sum_{B}-\mu(B)\log2(\ell_1 \ell_2 \lambda_1^{-n})\\ &\leq&n\log_2(\lambda_1)-\log_2(\ell_1\ell_2). \end{eqnarray*} On conclut que \begin{eqnarray*} H(\Xi_{\alpha,T_A})=\lim_{n\to\infty}\frac{1}{n}H(\alpha\vee T_A \alpha\vee \cdots \vee (T_A)^{n-1}\alpha)=\log_2(\lambda_1). \end{eqnarray*} Les pièces de la partition $T^{-n}\alpha$ sont des parallélogrammes dont les côtés parallèles à $\gamma_1$ ont des longueurs de l'ordre de $\lambda_2^n$. Par conséquent, les pièces de la partition $T^{-n}\alpha\vee T^{n}\alpha$ ont un diamètre qui tend vers $0$. \begin{center} \vskip-2cm \includegraphics[width=2in]{parallelogrammes(14).pdf} \vskip-2cm La partition $T^{-1}_A \alpha\vee T_A \alpha$. \end{center} Soit $\eps>0$, soit $R$ un rectangle du tore. Pour $n$ assez grand, il existe une réunion $U$ de pièces de $T^{-n}\alpha\vee T^{n}\alpha$ telle que $\mu(R\Delta U)<\eps$. Cela prouve que la tribu $\alpha_{-\infty}^{\infty}$ contient $R$. Comme les rectangles engendrent la tribu borélienne du tore, $\alpha$ est génératrice. D'après le Théorème \ref{KS}, \begin{eqnarray*} h_{\mu}(T_A)=H(\Xi_{\alpha,T_A})=\log_2(\lambda_1). \end{eqnarray*} \end{pf} \subsection{Chaos} Ce terme n'a pas de définition mathématique précise. Il évoque la sensibilité aux conditions initiales : \emph{Un système dynamique est chaotique si deux points très voisins peuvent néanmoins avoir des trajectoires qui s'éloignent}. Les automorphismes ergodiques du tore ont cette propriété. D'une certaine façon, l'entropie quantifie ce phénomène : étant donnée une partition $\alpha$ arbitrairement fine, la transformation en fait des partitions qui recoupent $\alpha$ suivant une multitude de pièces. Entropie $h$ positive signifie qu'il y a en gros $2^{nh}$ pièces de mesures à peu près égales. \subsection{A retenir} \begin{itemize} \item Le lien entre processus stationnaires et systèmes dynamiques. \item La notion de conjugaison dans la catégorie des espaces probabilisés. \item La notion d'entropie métrique, invariant de conjugaison dans cete catégorie. \item Le lien entre entropie et chaos. \end{itemize} Il s'agit d'un chapitre théorique, où une nouvelle notion a été introduite, dans un autre champ des mathématiques, les systèmes dynamiques. Elle s'applique à certains des exemples les plus fascinants de systèmes dynamiques. Il y a un théorème dont la preuve est difficile, car elle s'appuie sur des manipulations de tribus auxquelles on est peu familier en M1. %\section{Entropie topologique} %\subsection{Entropie d'une application continue} \end{document}