

\noindent {\it Sources:} Claude E. Shannon A mathematical source of communication\\
Pierre Brémaud Introduction aux probabilités, Chapitre 5, Springer\\
 Thomas M. Cover, Joy A. Thomas, Elements of information theory (pages 194-197),\\
 Wiley, 1991.


\section{ Introduction } Ces notes, qui donnent toutes les démonstrations, parfois sous
forme d'exercice, sont basées essentiellement sur le fameux livre
de Shannon. Celui-ci a l'avantage d'être très pédagogique, ayant
été écrit pour des ingénieurs. L'exposé étant parfois légérement
elliptique du point de vue mathématique, on le complète facilement
à l'aide du Brémaud (Chapitre 5) et du Cover-Thomas (trois pages).
 Dans son livre, Shannon introduit la notion d'entropie en théorie des
transmissions (cette notion était avant lui connue en physique
statistique dans un contexte très différent).   Le livre de
Shannon contient tous les points de départ des thèmes qui seront
ensuite développés en ce qu'on appellera plus tard la "théorie de
l'information". Les nombreux livres sur la théorie de
l'information suivent, cinquante ans après,  exactement le même
plan que celui de Shannon !   Shannon commence par réduire le
problème de la transmission à celui de la transmission d'une série
de symboles émis par  une source aléatoire. La source émet des
symboles (représentant par exemple des phrases en français).
L'incertitude du récepteur concernant le symbole qui va être
transmis est grande mais pas totale, puisque certains symboles
(certaines phrases) sont plus probables que d'autres. On suppose
connue la probabilité de chaque symbole.
\newline Dans le cas du langage, Shannon montre que
l'on peut évaluer cette probabilité en modélisant l'émission d'un
texte comme la production d'une chaîne de Markov. Les probabilités
de transition (lettre à lettre, ou plutôt mot à mot) de cette
chaîne de Markov peuvent être apprises en analysant un texte de
taille suffisante. Shannon montre par une simulation numérique
très simple que si on respecte les probabilités de transition mot
à mot, on peut déja synthétiser un texte qui ressemble vraiment à
de l'anglais ! On peut donc supposer connue, ou calculable, la
probabilité de chaque symbole (phrase) possible. Alors, dans la
communication,  tout se passe comme si la source (l'émetteur)
tirait au sort un symbole et l'envoyait au récepteur. Voici
quelques exemples tirés du livre de Shannon.
\begin{enumerate}
\item Approximation d'ordre zéro (symboles indépendants et
équiprobables).
\newline XFOML RXKHRRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACIUBZLHJQD.

\item Approximation d'ordre un (symboles indépendants mais
respectant les fréquences d'un texte anglais).
\newline OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL.

\item Approximation d'ordre 2 (fréquence des couples de lettres
comme en anglais).
\newline
ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVE
TUCOOWE AT TEATSONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.

\item Approximation d'ordre 3 (fréquence des triples de lettres
correcte).
\newline IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTURES OF
THE REPTAGIN IS REGOACTIONA OF CRE.

\item Approximation d'ordre 1 en mots : plutôt que de passer aux
tétragrammes, il est plus facile de sauter aux unités en mots. La
fréquence des mots est correcte :
\newline
REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT
NATURAL HERE HE THE A CAME THE TO OF TO EXPERT GRAY COME TO
FURNISHES THE LINE MESSAGE HAD BE THESE;

\item Approximation d'ordre deux : les probabilités de transition
entre mots successifs sont correctes (et rien d'autre).

THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE
CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE
LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN
UNEXPECTED;

\end{enumerate}
Shannon remarque : "The resemblance to ordinary English text
increases quite noticeably at each of the above steps. Note that
these samples have reasonably good structure out to about twice
the range that is taken into account in their construction. Thus
in 3. the statistical process insures reasonable text for
two-letter sequences, but four-letter sequences from the sample
can usually be fitted into good sentences. In 6. sequences of four
or more words can easily be placed in sentences without unusual or
strained constructions."


\subsection{L'entropie d'une source}Shannon définit une {\it source}, comme un
ensemble $\XX$ de symboles possibles avec leurs probabilités
$p(x)$ et cherche à définir  son entropie comme une mesure de
l'incertitude laissée au récepteur.

La définition formelle est $$H(X)=-\sum_{x\in \cal X} p(x)\log
p(x)$$ où $X$ est la variable aléatoire dont la valeur est le
symbole émis. (Sauf mention contraire, on note $\log$ pour le
logarithme en base 2 et $\log_D$ pour le logarithme en base $D$).
Pour  expliquer cette définition de l'entropie de diverses
manières, Shannon a recours à des arguments tirés de la loi des
grands nombres. Aussi ne va-t-il pas considérer des symboles émis
isolément, mais bien des suites de $n$ symboles, où $n$ est grand.
Nous appellerons ces séquences des {\it messages}, et ces
séquences sont composées de $n$ symboles tous tirés de manière
aléatoire indépendante selon la distribution de probabilité
$p(x)$.

L'entropie d'une source s'interprétera alors de trois manières :
\begin{itemize}
\item l'entropie est la longueur moyenne minimale des   mots
codant tous les symboles dans un  alphabet binaire : Shannon
montre que l'on peut coder de manière optimale en associant à
chaque symbole $x$ de probabilité $p(x)$ un code binaire (nombre
fait de 0 et 1) de longueur inférieure ou égale à   $-\log p(x) +1
$.

\item l'entropie est la capacité minimale moyenne d'un canal
capable de transmetre les
 messages issus de la source

\item l'entropie est la moyenne du logarithme du nombre  de
"messages typiques" quand la source envoie un nombre $n$ assez
grand de symboles successifs indépendants. En effet, toutes les
séquences de symboles $x_1x_2\dots x_n$ sont possibles, mais elles
ne sont pas du tout équiprobables : par la loi des grands nombres,
la fréquence d'apparition dans la séquence du symbole $x$ tend
vers $p(x) $ quand $n\to \infty$. Il y donc \underline{beaucoup
moins} de messages typiques que de messages possibles. Le nombre
de messages typiques est $2^{nH}$ où $H$ est l'entropie, alors que
le nombre de messages réels est $(\Card X)^n=2^{n\log \Card (X)}.$

\end{itemize}
 Le principe du  codage optimal est très intuitif :  les messages sont codés par des
codes d'autant plus courts qu'ils sont fréquents (codages de
Elias-Fano-Shannon, ou de Huffman, voir le Brémaud, et le  T.P.
d'Agnès Desolneux).  Dans tous les cas on retombe sur la même
formule ; l'entropie est égale à $-\sum_{x\in \XX} p(x)\log p(x)$.

\subsection{Transmission dans un canal bruité} Ensuite, Shannon s'occupe de transmission  dans un "canal bruité": son
problème est de savoir si celle-ci est réalisable, et à quel prix
en termes de redondance dans l'envoi. Shannon s'inspire de ses
expériences d'enfant avec le télégraphe : il sait qu'un message
peut être corrigé par le récepteur à cause de la "redondance" du
langage. Pour l'anglais, comme il le mesurera plus tard, cette
redondance est de l'ordre de 50 pour cent: on peut
  supprimer jusqu'à la moitié des lettres, ou des mots, d'un message
   en anglais et qu'il soit
  encore reconstructible (essayer !). De plus, {\it plus le message est long et plus
  la reconstruction est facile}. Cette intuition va être transformée par Shannon en
  un théorème fondamental.
Ce résultat de Shannon, obtenu pourtant par un argument
mathématique  non constructif, suscitera l'enthousiasme des
ingénieurs. Il introduit la notion d'entropie relative, $H(Y|X)$,
où $X$ est la source de messages aléatoires et $Y$ est la sortie
du canal, également une variable aléatoire.  $H(Y|X)$ mesure
l'incertitude sur le message envoyé $X$ sachant que l'on a reçu
$Y$. C'est donc une mesure de l'incertitude produite par le canal,
une  mesure du  "bruit" dans celui-ci.

\medskip Dans son théorème fondamental, Shannon montre qu'il est possible d'
obtenir un taux d'erreur aussi bas que désiré.  La transmission
dans le bruit est donc possible et Shannon définit la capacité
abstraite d'un canal comme $\max_X H(X)-H(X|Y)$ pour toutes les
sources $X$ utilisées comme entrées. (La capacité est la
différence entre quantité d'information envoyée ($H(X)$) et
l'incertitude générée sur ce qui est envoyé, $H(X|Y)$). Il montre
ensuite que toute source d'entropie inférieure ou égale à cette
capacité est transmissible avec un taux d'erreur arbitrairement
bas.

\subsection{Plan}
 Dans ces notes, qui combinent exercices élémentaires et démonstrations,
nous allons (les numéros correspondent aux différents exercices) :
\begin{enumerate}
\item donner les formulaires de l'entropie et de l'entropie
relative \item caractériser l'entropie comme le logarithme du
nombre moyen de séquences typiques
 de messages
typiques quand la source émet une longue suite \item définir la
capacité d'un canal non bruité \item montrer que toute source
d'entropie inférieure ou égale à la capacité peut être transmise
\item compter les entrées et sorties typiques pour un canal bruité
\item définir la capacité d'un canal bruité \item prouver le
théorème fondamental de Shannon selon lequel la transmission est
possible dans un canal bruité. Ce théorème est d'une élégance
extrème. Il prouve l'existence d'un codage optimal par un argument
de moyenne sur tous les codes possibles.
\end{enumerate}
Ce dernier résultat a montré la possibilité de codes correcteurs
d'erreur avant que de tels codages ne commencent à être trouvés.
Leur théorie est loin d'être terminée.

 \section{Les étapes du codage : vocabulaire}
\begin{itemize}
\item  {\it symbole }: on peut penser comme unités significatives
minimales aux phrases. Chaque phrase possible est dans le modèle
de Shannon représentée par un symbole $x$ dans un "alphabet" $X$
qui est donc fini mais très grand.  (A comparer au langage de
Sancho Panza dans Don Quichotte, qui ne parle que par proverbes :
chaque proverbe a une fréquence et c'est une concaténation de
proverbes qui constitue un discours de Sancho Panza.)

\item Chaque phrase $x$ a une probabilité $p(x)$. Comment la
calculer ? On modélise la langue comme le résultat d'une chaîne de
Markov : on mesure pour chaque paire de mots $M$ et $N$ la
probabilité  $p(M |N)$ que $M$ suive $N$, mesurée comme le rapport
entre le nombre d'apparitions de $NM$ divisé par le nombre
d'apparitions de $N$. Il suffit pour cela de parcourir quelques
milliers de documents dans la langue concernée.  On interprète
$p(M|N)$ comme la probabilité conditionnelle de lire $M$ sachant
qu'on a lu $N$. Le stockage en machine de ces probabilités est
faisable : $10^5$ mots usuels et donc $10^{10}$ probabilités
conditionnelles. On stocke aussi les probabilités d'apparition de
chaque mot. On peut alors générer une "phrase typique de longueur
$n$", $x=M_1M_2\dots M_n$ de la langue en tirant au sort le
premier mot $M_1$ avec la distribution de probabilité $p(M)$, le
second avec la distribution de probabilité $p(M|M_1)$, etc.
Chomsky et Schützenberger ont démontré qu'un modèle markovien
était insuffisant pour rendre compte de la structure syntaxique
récursive du langage. Toutefois, le modèle markovien donne des
résultats très acceptables, comme le prouve le fait que les
phrases générées, apprises de journaux, ressemblent assez à la
production journalistique moyenne.

\item {\it message} : il s'agit d'une concaténation de symboles
tirés selon la distribution $p(x)$. Si chaque symbole représente
une phrase, alors un message est une concaténation de symboles et
représente donc un long texte. Chaque symbole est tiré
indépendamment des autres, et un message de longueur $n$ est donc
simplement une suite de variables indépendantes et identiquement
distribuées.

\item{\it variations du calcul d'entropie} : Il est clair que le
calcul de l'entropie d'un texte n'est pas le même si on utilise
comme unité le caractère, ou le mot, ou la phrase. Shannon montre
bien que plus  les unités dont on calcule la probabilité sont
longues et plus l'entropie décroît et serre de près la vraie
incertitude sur le texte.

\item {\it codage d'une source par une autre} : Soient deux
sources différentes $X_1$ et $X_2$. Les messages de longueur $n$
émis par la source $X_1$ peuvent être associés à des messages de
longueur $m$ émis par la source $X_2$,  à condition que $m$ soit
assez long. Ainsi, les caractères de l'alphabet peuvent-être codés
comme séquences de huit bits (mots composés de 0 et de 1).  On
appelle une telle application un codage.  Les codages optimaux
permettront d'adapter la longueur des symboles à leur fréquence,
les symboles fréquents étant codès par des mots très courts et les
symboles infréquents par des codes longs. Cette propriété du
codage est déja patente dans le langage courant : "oui", "non",
"et", "quoi ?", "homme", "chat", "chien"  sont courts et
fréquents, "anticonstitutionnellement" et "rhinocéros" sont longs
et rares.





\end{itemize}


\dexer {\bf Formulaire de Shannon (source : Shannon)} On définit
l'entropie d'une v.a. discrète $X$ dont les valeurs $x$ sont dans
l'alphabet fini $\XX$, et idem pour un couple de variables
aléatoires $(X,Y)$ à valeurs dans $\XX\times \YY$ :
$$H(X)=-\sum_x p(x)\log p(x),\;\; H(X,Y)=-\sum_{x,y}p(x,y)\log p(x,y).$$

\quest Montrer que l'entropie est l'espérance de $g(X)$, avec
$g(X)=\log \frac 1{p(X)}.$

\quest Exemple important : on prend pour $X$ la variable de
Bernouilli, $X=1$ avec probabité $p$, $X=0$ avec probabilité
$1-p$. Alors
$$H(X)=-p\log p-(1-p)\log(1-p),$$
que l'on notera $H(p)$. Vérifier que $H(X)=1$ bit quand $p=\frac
12$. Tracer le graphe de $H(p)$ et montrer qu'elle vaut 0 en 0 et
1 est est maximale en $p=\frac 12$. Interprétation : l'incertitude
sur $X$ est maximale quand $p=\frac 12$ et minimale quand $X$ est
déterministe. L'entropie est une mesure de l'incertitude sur la
valeur de $X$.


\begin{propf}\label{entropiejointe} L'entropie jointe de deux variables aléatoires est plus petite que la
somme des entropies. Il y a égalité si et seulement si les deux
variables aléatoires sont indépendantes
$$H(X,Y)\leq H(X)+H(Y).$$
\end{propf}
\begin{lemf} \label {comparaisondedeuxdistributionsdeproba} Soient $p$ et $q$ deux distributions de probabilité discrètes. Alors
$\sum p(x)\log \frac{p(x)}{q(x)}\geq 0.$ Il y a égalité si et
seulement si $p(x)=q(x)$ pour tout $x$.
\end{lemf}
\paragraph{Démonstration de la proposition \ref{entropiejointe}}. On applique le lemme
\ref{comparaisondedeuxdistributionsdeproba} aux distributions
$p(x,y)$   et $p(x)p(y)$.
$$\sum p(x,y)\log \frac{p(x,y)}{p(x)p(y)}\geq 0,$$
ce qui donne
$$-\sum_{x,y} p(x,y)\log p(x,y)\leq -\sum_{x,y}p(x,y)\log p(x) -\sum_{x,y}\log p(y),$$
l'égalité n'étant vérifiée que si $p(x,y)=p(x)p(y).$ Comme
$\sum_{y}p(x,y)=p(x)$ et $\sum_x p(x,y)=p(y)$, on obtient le
résultat annoncé.
\enddemo

\medskip \skipaline
\paragraph {Démonstration du lemme \ref{comparaisondedeuxdistributionsdeproba}.} On utilise la stricte
concavité du logarithme.
$$-\sum p(x)\log \frac{p(x)}{q(x)}=\sum p(x)\log \frac{q(x)}{p(x)}\leq \log(\sum
p(x)\frac{q(x)}{p(x)})=\log 1=0,$$ l'inégalité étant une égalité
si et seulement si toutes les valeurs $\frac{p(x)}{q(x)}$ sont
égales entre elles, auquel cas la valeur commune est évidemment 1.
\enddemo

\quest {\bf Entropie conditionnelle de $Y$ sachant $X$ :} c'est
"la moyenne de l'entropie de $Y$ pour chaque valeur de $X$,
pondérée par la probabilité d'avoir cette valeur particulière de
$X$". (Vérifier que la formule qui suit correspond à cette
définition !)
$$H(Y|X)=-\sum_{x,y}p(x,y)\log p(y|x).$$
"{\it This quantity measures how uncertain we are of $Y$ on the
average when we know $X$.}" En utilisant la définition de la
probabilité conditionnelle :
$$p(y|x)=\frac{p(x,y)}{\sum_yp(x,y)},$$

$$H(Y|X)=-\sum_{x,y} p(x,y)\log p(x,y)+\sum_{x,y} p(x,y)\log\sum_y
p(x,y)=H(X,Y)-H(X).$$ Donc
$$H(X,Y)=H(X)+H(Y|X).$$
"{\it The uncertainty (or entropy) of the joint event $X, Y$ is
the uncertainty of $X$ plus the uncertainty of $Y$ when $X$ is
known}". Utilisons la proposition \ref{entropiejointe} :
$$H(X)+H(Y)\geq H(X,Y)=H(X)+H(Y|X).$$
Donc $$H(Y)\geq H(Y|X).$$ "{\it The uncertainty of $Y$ is never
increased by knowledge of $X$.  It will be decreased unless $X$
and $Y$ are independent events, in which case it is not changed}".

\fexer

 \dexer{\bf Messages typiques} (énoncé et démontré dans le Brémaud page 99 : essentiel !)
 Nous gardons les notations du Brémaud. En pratique $D=2$.
  Soit $X_n$ une suite de v.a.i.i.d. à valeurs dans un ensemble fini de symboles
$\XX=\{1,\; 2, ..., \; k\}$ et telles que $P(X_n=i)=p_i$,
$i=1,\;... ,k$. Soit $\XX^n$ l'ensemble des suites (messages) de
longueur $n$ : il y en a $k^n$. On considère l'entropie de la
répartition $(p_i)_{1\leq i\leq k}$,
$$H_D(p_1,\;...,\;p_k)=-\Sigma_{i=1}^{i=k}p_i\log_D p_i.$$
 On définit l'ensemble des "messages
typiques"
$$C_n=\{(i_1,\;...,\;i_n)\in M^n,\; D^{-n(H_D+\varepsilon)}\leq
p_{i_1}...p_{i_n}\leq D^{-n (H_D-\varepsilon)}\}.$$

\quest 1) Montrer que $E(-\log_D p_{X_n})=H_D.$

\quest 2) Déduire que
$$P(\{|\frac 1n \Sigma_{l=1}^{n}(-\log_D p_{X_l})-H_D|\geq
\varepsilon\})=P((X_1,\;...,\; X_n)\in C_n^c)\leq
\frac{\Var(-\log_D p_{X_1})}{n\varepsilon^2}.$$

\quest 3) Montrer que
$$
P((X_1,\;...,\; X_n)\in C_n))\geq D^{-n(H_D+\varepsilon)}\Card
(C_n).$$ Déduire que $\Card (C_n) \leq D^{(H_D+\varepsilon)n}$.

\quest 4) Réciproque. Supposons que l'on ait pu trouver $\tilde
C_n\subset \XX^n$ tel que $\lim_{n\to +\infty} P((X_1,\;...,\;
X_n)\in \tilde C_n)=1$ et $\Card (\tilde C_n)\leq D^{Kn}.$ On va
montrer que $K\geq H_D$.

\medskip 4a)  Montrer que $\lim_{n\to
\infty}P((X_1,\;...,\;X_n)\in C_n\cap \tilde C_n)=1.$

\medskip 4b)
Montrer que $P((X_1,\;...,\;X_n)\in C_n\cap\tilde C_n)\leq
D^{-n(H_D-\varepsilon)}D^{Kn}$ et conclure.

\quest 5) On prend $D=2$, $\XX=\{0,1\}$, $p_1=p$, $p_2=(1-p)$. Si
$p_1=p_2=\frac 12$, vérifier que $H_2=1$ et que le nombre de
suites typiques est $2^n$. (Pas de compression possible).
\newline Cas général : étudier la forme de $H_2(p)=-p\log p
-(1-p)\log(1-p)$ et en déduire le comportement des suites
typiques.

\quest {\it Corrigé : Brémaud, Introduction aux probabilités,
pages 97 à 102.}

\fexer


\dexer{\bf Capacité d'un canal discret non bruité.} Cette
définition est donnée par Shannon page 37. Soit un canal
tranmettant des séquences de symboles sans erreur. On appelle
capacité du canal la quantité (mesurée en bits/seconde)
\begin{equation}\label{defcapacite}
C=\lim_{T\to \infty}\frac{\log N(T)}T
\end{equation}
 où $N(T)$ est le nombre maximal de messages distincts transmissibles pendant le
temps $T$. Remarquer que cette définition ne se préoccupe pas de
l'alphabet ou du type de codage discret ou physique dans lequel
les messages sont transmis.
 On obtient une
définition intrinsèque en considérant uniquement le nombre de
messages distincts.  Si par exemple le canal déterministe tranmet
des séquences arbitraires de 0 ou 1 au débit de un symbole par
seconde, on a $2^T$ messages possibles et on a donc bien une
transmission à un bit par seconde. Cette définition de la capacité
est aussi une hypothèse, à savoir l'existence de la limite
(\ref{defcapacite}).

\fexer

\dexer{\bf Application : transmission d'une source par  un canal
déterministe.} L'énoncé qui suit et sa démonstration suivent très
directement, et avec les mêmes notations,  la démonstration
originale de Shannon (page 59). Une deuxième démonstration
proposée ensuite par Shannon donne un codage explicite, appelé
depuis codage de Shannon-Elias-Fano. (Voir Brémaud pages 85-95).
L'intérêt de la démonstration qui suit est qu'elle s'appuie
entièrement sur l'évaluation du nombre de messages typiques grâce
à l'entropie de la source. Le problème est de savoir comment lier
la capacité d'un canal à l'entropie de la source dont on veut
transmettre la production via ce canal. Comme la définition de la
capacité est asymptotique (une limite quand des messages
arbitrairement longs sont transmis), on considère aussi des
messages arbitrairement longs émis par la source, c'est-à-dire des
séquences de $n$ symboles avec $n\to +\infty$.

\begin{deff} Soit un système de transmission formé d'une source
et d'un procédé de codage de cette source permettant son entrée
dans  un canal déterministe.   On appelle débit maximal
asymptotique du système la quantité $\lim\sup_{n\to\infty}\frac
n{T_n}$, où
 $T_n$ est le temps minimal garantissant la transmission d'une séquence de $n$ symboles.
On note aussi $E\tilde T_n$ l'espérance du temps pour transmettre
$n$ symboles, autrement dit le
 temps moyen de transmission de $n$ symboles de la source. On appelle "débit moyen" du
  système de transmission,
 mesuré en symboles par seconde, la quantité
 $$\lim\inf_{n\to \infty} \frac{n}{E\tilde T_n}.$$
\end{deff}
\begin{thf}
Soient une source d'entropie $H$ (en bits par symbole) et un canal
de capacité $C$ (en bits par seconde). Alors pour tout
$\varepsilon>0$, il est possible de coder l'{\it output} de la
source de telle sorte que la transmission dans le canal se fasse
avec un débit moyen   de $\frac C H-\varepsilon$ symboles par
seconde. Il n'est pas possible de transmettre avec un débit
maximal strictement supérieur à $\frac C  H$. En d'autres termes,
$$\lim\sup_{n\to\infty}\frac n{T_n} \leq  \frac CH \;\hbox{ et }\;
  \lim\inf \frac n{E\tilde T_n} \geq \frac CH.$$
\end{thf}

\paragraph{Démonstration} Montrons d'abord la deuxième partie  : pour $n$ grand,  le cardinal de l'ensemble
des messages de $n$ symboles   qui peuvent être émis par la source
est supérieur ou égal à $2^{n(H-\varepsilon)}$ (exercice 2). Soit
$T_n$ le temps de transmission minimal requis pour être sûrs de
transmettre l'un quelconque de ces messages.
 Par la définition de la capacité,
 $$N(T_n)\geq 2^{n(H-\varepsilon)}.$$
Comme $T_n\to \infty$, on a pour $n$ assez grand
$$\frac{\log N(T_n)}{T_n}\leq C +\varepsilon$$

 En combinant ces deux inégalités, on obtient
 $$C+\varepsilon \geq \frac{n(H-\varepsilon)}{T_n}$$
 et donc $$\frac{T_n}n \geq \frac{H-\varepsilon}{C+\varepsilon}.$$
 D'où $\lim\inf_{n\to \infty} \frac{T_n}n\geq \frac HC$ et donc
 $\lim\sup_{n\to \infty} \frac n{T_n}\leq  \frac CH$
\newline
\newline
Montrons maintenant la première partie : Pour $n$ grand, on divise
l'ensemble des messages de $n$ symboles produits par la source en
deux groupes, l'un contenant moins de $2^{n(H+\eta)}$ messages est
l'ensemble des "messages typiques". L'autre, son complémentaire,
contient moins de $2^{Rn}$ messages, où $R$ est le logarithme du
nombre de symboles différents. En effet, on a $\Card (X)$
symboles, donc $\Card(X)^n=2^{n\log \Card(X)}$ suites possibles de
$n$ symboles.
 La probabilité du second groupe (les messages non typiques) est plus
petite que $\mu$. Quand $n$ tend vers l'infini, on peut faire
tendre $\eta$ et $\mu$ vers zéro.
\newline
Par ailleurs, on peut envoyer par le canal un nombre de messages
différents de durée $T$ supérieure ou égale à $2^{(C-\theta)T}$,
où $\theta$ est arbitrairement petit quand $T$ est grand. Ceci
découle de la définition de la capacité. On choisit alors
$$T=n(\frac HC +\lambda).$$ On a donc dans ce temps la possibilité d'envoyer
$2^{n(C-\theta)(\frac HC +\lambda)}$ messages. On peut donc coder
chacun des messages typiques de la source, à condition que
$(H+\eta)\leq (C-\theta)(\frac HC+\lambda)$, soit
$$\lambda\geq \frac 1{C-\theta}(\eta+\theta\frac HC),$$
condition réalisable avec $\lambda$ arbitrairement petit pour $n$
grand. Tous les messsages typiques de longueur $n$ sont donc
transmissibles en temps $T$.  Reste à transmettre les messages non
typiques, qui sont au plus $2^{nR}$. En reprenant le raisonnement
précédent, on voit qu'on peut les transmettre en un temps
 $T_1=n(\frac RC +\varphi)$, où $\varphi$ peut être arbitrairement petit pour $n$
 assez grand.
 Les messages non typiques sont beaucoup plus nombreux que les messages typiques
 et  demandent un temps de transmission plus long. Mais ils sont rares.  On peut donc
 estimer le temps moyen de transmission d'un message de $n$ symboles issu de la
 source, l'espérance étant calculée sur l'espace produit ${\XX}^n$:
$$E\tilde T_n\leq(1-\mu)T+ \mu T_1= n[(1-\mu)(\frac HC +\lambda)+\mu(\frac RC +\varphi)
].$$ Si on divise ce temps moyen par $n$ on obtient le temps moyen
de transmission par symbole et son inverse est le nombre de
symboles transmis par unité de temps. Comme $\mu$, $\lambda$,
$\varphi$ peuvent être rendus arbitrairement petits pour $n$
grand, on obtient comme annoncé
$$\lim\inf \frac n{E\tilde T_n} \geq \frac CH.$$


\enddemo

\fexer





\dexer{\bf Messages et sorties typiques pour un canal bruité}
(Cover-Thomas 8.6 page 195) On considère une source, c'est-à-dire
une variable aléatoire $X$ discrète de loi $p(x)$, $x\in \XX$. Un
canal de transmission bruité transmet $X$ avec erreur. Le résultat
est une variable aléatoire $Y$ de loi $p(y)$. On note $p(x,y)$ la
loi jointe de $x$ et de $y$. Dans le cas d'un canal non bruité, on
aurait $p(x,x)=p(x)$ pour tout $x$, $p(x,y)=0$ pour $x\neq y$. On
note $H(X)$, $H(Y)$ et $H(X,Y)$ les entropies de $X$, de $Y$ et de
$(X,Y)$ respectivement. Cette dernière entropie s'appelle
l'entropie jointe de $X$ et $Y$. Si la source émet une séquence de
$n$ messages indépendants et équidistribués, on note $X^n$ la
variable aléatoire correspondante et $Y^n$ la sortie ({\it
output}). Les valeurs de $X^n$ se notent $x^n\in\XX^n$ et celles
de $Y^n$ se notent $y^n\in \YY^n$.

\begin{deff} \label{couplestypiques} On appelle ensemble de couples message-sortie typiques relativement à la
distribution $p(x,y)$ l'ensemble $A_\varepsilon^{n}$ des suites
$\{(x^n,y^n)\}$ qui ont leurs entropies empiriques proches à
$\varepsilon$ près des entropies réelles, à savoir que
$A_\varepsilon^{n}=B_\varepsilon^n\cap C_\varepsilon^n\cap
D_\varepsilon^n$ avec
\begin{eqnarray}
B_\varepsilon^n&=&\{(x^n,y^n)\in \XX^n\times \YY^n :
|-\frac 1n\log p(x^n)-H(X)|<\varepsilon\},\\
C_\varepsilon^n&=&\{(x^n,y^n)\in \XX^n\times \YY^n :
|-\frac 1n\log p(y^n)-H(Y)|<\varepsilon\},\\
D_\varepsilon^n&=&\{(x^n,y^n)\in \XX^n\times \YY^n : |-\frac
1n\log p(x^n,y^n)-H(X,Y)|<\varepsilon\},
\end{eqnarray}
où $p(x^n)=\Pi_{i=1}^n p(x_i)$, $ p(y^n)=\Pi_{i=1}^np(y_i),$
$p(x^n,y^n)=\Pi_{i=1}^n p(x_i,y_i)$ en raison de l'indépendance
des $n$ messages successifs.
\end{deff}
\begin{lemf} \label{suitestypiquesjointes}
Soit $(X^n, Y^n)$ une suite de longueur $n$ de v.a.i.i.d. selon la
loi $p(x^n,y^n)=\Pi_{i=1}^np^(x_i,y_i).$  Alors
\begin{enumerate}
\item $\Pro((X^n, Y^n)\in A_\varepsilon^{n})\to 1 $ quand $n\to
\infty$. \item $\Card (\{y^n,\;(x^n,y^n)\in A_\varepsilon^n\})\leq
2^{n(H(Y|X)+2\varepsilon)}$ \item $\Card (\{x^n,\;(x^n,y^n)\in
A_\varepsilon^n\})\leq 2^{n(H(X|Y)+2 \varepsilon)}$
%\item $|A_\varepsilon^{(n)}|\leq 2^{n(H(x,y)+\varepsilon)}.$
%\item Si $(\tilde X^n,\tilde Y^n)$ a pour loi $p(x^n)p(y^n)$, i.e. si $\tilde X^n$ et
%$\tilde Y^n$ sont indépendantes et avec les mêmes lois  que $X^n$ et $Y^n$, alors
%$$\Pro((\tilde X^n, \tilde Y^n)\in A_\varepsilon^{(n)})\leq 2^{-n(I(X ;
%Y)-3\varepsilon)}$$ et, pour $n$ assez grand, $$\Pro((\tilde X^n,\tilde Y^n)\in
%A_\varepsilon^{(n)})\geq (1-\varepsilon) 2^{-n(I(X,Y)+3\varepsilon)}.$$
\end{enumerate}
\end{lemf}
\paragraph{Démonstration} Montrons la première relation. Notons $p_1 : (x^n,\; y^n)\to x^n$ et $p_2 :
(x^n,\; y^n)\to y^n$ les projections sur $X^n$ et $Y^n$
respectivement. Le résultat de l'exercice 2 nous assure que quand
$n\to \infty,$

\begin{eqnarray}
& &\Pro(B_\varepsilon^n)\to 1\\
& &\Pro(p_1(C^n_\varepsilon)\times Y^n)= \Pro(p_1(C_\varepsilon^n))\to  1\\
& &\Pro(X^n \times p_2(D^n_\varepsilon
))=\Pro(p_2(D_\varepsilon^n))\to 1.
\end{eqnarray}
La  relation 1 découle alors de la remarque générale que si  des
suites d'ensembles $B^n_i$, $i=1, \dots ,k$ vérifient
$\Pro(B^n_i)\to 1$ quand $n\to \infty$, alors $\Pro(\cap_{i=1}^k
B_i^n)\to 1$ aussi. On applique cette remarque à l'intersection
des trois ensembles précédents,
$$A_n^\varepsilon
=B_\varepsilon^n \cap (p_1(C_\varepsilon)\times Y^n)\cap(X^n
\times p_2(D^n_\varepsilon )).$$ Montrons maintenant  la  relation
2. On a par hypothèse $\Pro(X^n=x^n)=p(x^n)=2^{-n(H(X)\pm
\varepsilon)}$ et
$\Pro((X^n,Y^n)=(x^n,y^n))=p(x^n,y^n)=2^{-n(H(X,Y)\pm
\varepsilon)}$. Donc
$$p(x^n)=\sum_{y^n} p(x^n,y^n)
\geq \sum_{y^n,\; (x^n,y^n)\in A_\varepsilon^n}
p(x^n,y^n)\geq\Card(\{y^n, \; (x^n,y^n)\in
A_\varepsilon^n\})\inf{(x^n,y^n)\in A^n_\varepsilon}p(x^n,y^n).$$
Donc
$$\Card(\{y^n,\; (x^n,y^n)\in
A_\varepsilon^n\})\leq2^{-n(-H(X,Y)+H(X)+2\varepsilon)}=2^{n(H(Y|X)+2
\varepsilon)}.$$

\enddemo

 \fexer

\dexer{\bf Capacité d'un canal bruité} On définit un canal discret
comme un système disposant d'un alphabet d'entrée $\XX$ et d'un
alphabet de sortie $\YY$ et d'une matrice de probabilités de
transition $p(y|x)$ donnant la probabilité d'observer le symbole
$y$ en sortie quand le symbole $x$ a été envoyé. Un tel canal est
dit  "sans mémoire" car la distribution de probabilité de la
sortie à chaque temps dépend uniquement de l'entrée et est
indépendante des entrées et sorties précédentes. Shannon page 70 :
On commence par définir le {\it rate of transmission} du canal (le
débit) pour une source $X$ et la sortie correspondante $Y$ par
$$R=I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y).$$
{\it The first defining expression has already been defined as the
amount of information sent less the uncertainty of what was sent.
The second measures the amount received less the part of this
which is due to noise. The third is the sum of the two amounts
less the joint entropy and therefore in a sense is the number of
bits per second common to the two. Thus, all three expressions
have a certain intuitive significance.}
\newline
La capacité d'un canal va être définie comme le débit maximal pour
toutes les sources possibles $X$.

\begin{deff}
On appelle capacité d'un canal discret sans mémoire la quantité
$$C=\max_{p(x)} I(X ;Y),$$
le maximum étant pris sur toutes les sources, i.e. toutes
distributions de probabilité possibles $p(x), \; x\in \cal X$ à
l'entrée.
\end{deff}

\quest{\bf Exemple 1} Si le canal transmet intégralement une
entrée binaire sans erreur, la matrice de transition est
l'identité. On a $Y=X$ et donc $I(X;X)=H(X)-H(X|X)= H(X)$. Donc la
capacité est maximisée quand l'entropie de la source binaire est
maximisée, ce qui donne comme attendu $p(0)=p(1)=\frac 12$ et
$C=H(p)=1$ bit.

\quest {\bf Exemple 2 : canal binaire symétrique} On prend
$\XX=\YY=\{0, \; 1\}$ et
$$p(y=1|x=1)=p(y=0|x=0)=1-p, \;\;\; p(y=1|x=0)=p(y=0|x=1)=p.$$
On rappelle que l'entropie d'un canal binaire (variable de
Bernouilli $(p, 1-p)$), est $H(p)=-p\log p-(1-p)\log(1-p).$  On a
$$H(Y)-H(Y|X)= H(Y)-\sum p(x)H(Y|X=x)=H(Y)-\sum p(x)H(p)=H(Y)-H(p)\leq
1-H(p).$$ On obtient l'égalité  en prenant $X$ uniforme, car alors
$Y$ l'est alors aussi et on a $H(Y)=1$. Donc $C=1-H(p).$

%\quest Le canal binaire avec pertes (binary erasure channel) : une fraction $\alpha$
%des bits est perdue, mais le récepteur sait quels bits ont été perdus. Cela veut dire
%que l'alphabet d'arrivée a trois symboles, 0, 1, et $e$, à savoir "erreur". On a
%$p(Y=0|X=0)=p(Y=1|X=1)=1-\alpha,\; p(Y=e|X=0)=p(Y=e|X=1)=\alpha$ et
%$$C=\max_{p(x)} I(X; Y)=\max_{p(x)} (H(Y)-H(Y|X))=\max_{p(x)} H(Y)-H(\alpha).$$
%TERMINER OU JETER
 \fexer

\dexer {\bf Le théorème fondamental pour un canal discret bruité}
\begin{thf} (Shannon pages 71, 72, 73)
Soit un canal discret de capacité $C$ et une source discrète
d'entropie $R$.
\newline (a) Si $R\leq C$ il existe un système de codage tel que la sortie de la source
puisse être transmise sur le canal avec une fréquence
arbitrairement petite d'erreurs.
\newline (b) Si $R>C$ il est possible de coder la source de manière que l'incertitude
sur les messages $H(X|Y)$ soit inférieure  à $R-C+\varepsilon$ où
$\varepsilon$ est arbitrairement petit.
\newline (c) Il n'y a pas de méthode de codage qui donnerait
une incertitude sur les messages $H(X|Y)$ inférieure à $R-C$.

\end{thf}
\paragraph{Démonstration} (a) Soit une source $X_0$ de débit approchant la capacité maximale $C$. On va
l'utiliser comme entrée dans le canal. Considérons toutes les
suites possibles transmises et reçues, d'une   durée assez longue
$n$. Dans toute la suite, les $\varepsilon$, $\eta$, $\theta$
désignent des réels positifs qui tendent vers zéro quand le débit
de la source $X_0$ se rapproche de la capacité maximale du canal
ou quand  la durée de transmission $n\to \infty$. Pour ne pas
alourdir les notations, on continuera à noter $\varepsilon$ pour
$C\varepsilon$ quand  $C$ est une constante indépendante de $n$.
Enfin on notera $2^{a \pm \varepsilon}$ un nombre quelconque $b$
vérifiant $2^{a-\varepsilon} \leq b\leq 2^{a+\varepsilon}$.

\medskip Nous considérons l'ensemble $A^n_\varepsilon$
 des couples typiques $(x^n,y^n)$ de couples typiques formés eux-mêmes de messages
 typiques envoyés et de messages typiques reçus
  (Définition \ref{couplestypiques}).
\begin{enumerate}
\item Les suites transmises sont dans deux groupes : les messages
typiques, dont le nombre est environ $2^{n(H(X)\pm \varepsilon)}$
et les autres, dont la probabilité totale est inférieure à $\eta$.
\item De même, les suites reçues forment  un ensemble de suites
typiques de nombre $2^{n(H(Y)\pm \varepsilon)}$ et de probabilité
totale supérieure à $1- \eta$. On note $\MM_0$ cet ensemble de
messages typiques. \item Par le lemme \ref{suitestypiquesjointes},
chaque
 sortie typique peut être produite par au plus $2^{n(H(X|Y)+
\varepsilon)}$ entrées. \item De même, chaque entrée typique peut
produire au plus $2^{n(H(Y|X)\pm \varepsilon)}$ sorties (on ne va
pas utiliser cette dernière propriété.)
\end{enumerate}

\skipaline Soit maintenant une autre source $X$ émettant avec un
débit $R<C$ (i.e. ayant une entropie inférieure à $C$.) On pose
$R=C-\theta$. Dans le temps $n$, cette source peut avoir
$2^{n(R\pm \varepsilon)}$ messages typiques. Nous noterons $\MM$
cet ensemble de messages typiques. Nous allons coder ceux-ci en
les associant  à des messages typiques de longueur $n$ de la
source $X_0$. Ces messages seront donc utilisés comme codes.
Chaque codage est donc une application $\CC$ : $\MM\to \MM_0$
obtenue en tirant au hasard pour chaque message dans $\MM$ (avec
distribution uniforme) un élément de $\MM_0$ qui devient son code.
Les autres messages, non typiques, ne sont pas codés, ce qui donne
une probabilité d'erreur plus petite que $\eta$.
 Supposons qu'on observe une
sortie $y_1$. On va maintenant évaluer la probabilité d'erreur :
quelle est la probabilité que $y_1$ ait été associée à plus d'un
message issu de $\MM$ ? Par (3), on sait que $y_1$ a pu être
produite par  au plus $2^{n(H(X|Y)+ \varepsilon)}$ messages $x_0$
appartenant à $\MM_0$. La probabilité que chaque $x_0\in \MM_0$
soit un code est   $2^{n(R-H(X)\pm \varepsilon)}$, car
 on a distribué $2^{n(R\pm\varepsilon)}$ messages uniformément dans $2^{n(H(X)\pm
\varepsilon)}$ codes. Donc la probabilité que $y_1$ soit issu d'un
message de $X$ (en dehors du message qui l'a provoqué)  est
majorée de la manière suivante
$$\Pro(\hbox{erreur sur }y_1)\leq 2^{n(R-H(X)\pm
\varepsilon)}2^{n(H(X|Y)+ 2\varepsilon)}.$$
 Mais $R=H(X)-H(X|Y)-\theta$, avec
$\theta>0$. Donc
$$\Pro(\hbox{erreur sur }y_1)\leq 2^{n(R-H(X)+
\varepsilon + H(X|Y)+2\varepsilon)} =  2^{-n(\theta -3
\varepsilon)}$$

Comme $\eta $ a été fixé (aussi petit qu'on veut)  et que l'on
peut à $\eta$ fixé prendre $\varepsilon$ aussi petit qu'on veut
pour  $n$ assez grand, on déduit que la probabilité d'erreur pour
\underline{chaque} message est arbitrairement petite, ce qui
prouve (a) pour $R<C$.

\skipaline  (b) Si $R\geq C$,  on peut encore appliquer la
construction précédente en choisissant de ne coder que
$2^{n(C-\varepsilon)}$ messages des $2^{n(R\pm\varepsilon)}$
typiques. On "jette" les autres.  Ce n'est quand même pas très
intéressant, puisque la plupart des messages typiques ne sont pas
transmis !

\skipaline (c) Supposons que l'on puisse transmettre par un canal
de capacité $C$ les messages d'une source $X$ d'entropie $R=C+a$,
avec $a>0$ et que l'incertitude sur le message vérifie
$H(Y|X)=a-\varepsilon$ avec $\varepsilon>0$. Alors
$H(X)-H(X|Y)=C+\varepsilon$ et cela contredit la définition de $C$
comme le maximum de $H(X)-H(X|Y)$ pour toutes les sources en
entrée.
 \fexer

 \skipaline
{\bf La question de la fin.} \newline Expliquer le raisonnement
suivant de Shannon, qui conclut
  la démonstration précédente : \newline\newline
   {\it Actually more has been proved than was stated in the
 theorem. If the average of a set of positive numbers is within $\varepsilon$ of
 zero, a fraction of at most $\sqrt \varepsilon$ can have values greater than $\sqrt
 \varepsilon$. Since $\varepsilon$ is arbitrarily small we can say that almost all
 the systems are arbitrarily close to the ideal.}
 \newline\newline
 En d'autres termes, presque tous
 les codes considérés précédemment sont des codes correcteurs d'erreurs : on peut
 tirer un code au hasard et il fonctionnera.
 \newline\newline Alors,
 pourquoi est-il difficile en pratique de fabriquer un code correcteur d'erreur ?


\section{ Entropie, entropie relative, information mutuelle}  

\noindent {\bf Conseils de lecture} :
\newline  Claude E. Shannon et Warren Weaver The mathematical theory of communication
University of Illinois Press 1998. (Très bon marché, commander par
Amazon.com par exemple).
\newline Thomas M. Cover et Joy A. Thomas  Elements of Information Theory, Wiley Series
Telecommunications, Chapitres 2, 5 et 8 (ces chapitres forment un
tout et peuvent être lus indépendamment du reste)
\newline Pierre Brémaud Introduction aux probabilités, Springer.\\

\dexer{\bf La définition de l'entropie, opus cit. p. 49} Soit un
ensemble fini d'événements dont les probabilités sont $p_1,\dots,
\; p_n$. On connaît les $p_i$, mais on est dans l'incertitude sur
quel événement  va se produire.  L'entropie $H(p_1,\dots ,\; p_n)$
va être définie comme une mesure de l'incertitude qui nous est
laissée.  Afin de comprendre les axiomes qui vont mener à la
définition de l'entropie, il faut réaliser qu'une présentation
d'un ensemble d'événements disjoints peut faire l'objet de
regroupements  et être donc présenté en arbre : par exemple, on
peut regrouper les $k$ premiers événements en un seul événement de
probabilité $p'_{1}$ et on obtient donc les deux suites de
probabilités $p'_1=\sum_{i=1}^k p_i, \;p_{k+1},\dots,\; p_{n}$, le
premier événement étant décomposé à son tour en $\pi_1,\dots,\;
\pi_{k}$ avec $\pi_i=\frac {p_i}{p_1+\dots +p_k}$. Dans un cas on
a $n$ événements et dans l'autre un premier tirage entre  $n-k+1$
événements disjoints, suivi d'un deuxième tirage conditionnel
entre $k$ événements. On a donc deux présentations des mêmes
événements : \newline $(p_1,\dots\; p_n)$, ou bien
\newline $((p'_1, \pi_1),\dots\; (p'_1,\pi_k), p_{k+1},\dots\; p_n)$
\newline
 On pose les axiomes intuitifs suivants.

\begin{enumerate}
\item $H$ est continue \item Supposons que les $p_i$ sont égaux,
$p_i=\frac 1n$. Alors $H$ doit être une fonction croissante de $n$
\item   Si on recompose les $n$ événements comme expliqué
ci-dessous, il est clair que l'incertitude  finale est la même. On
exige donc
$$H(p_1,\dots,\; p_n)=H(p'_1,\; p_{k+1},\;\dots\;p_n)+p'_1H(\pi_1,\dots\; \pi_k).$$
\end{enumerate}

Il s'agit de montrer que sous les axiomes 1, 2 et 3, on a  pour
une constante positive $K$,
$$H(p_1,\dots,\; p_n))=-K\sum_{i=1}^n p_i\log p_i.$$

\quest 1) On pose $H(\frac 1n,\;\dots \; \frac 1n)=A(n).$ Montrer
d'abord en utilisant l'axiome 3 que $A(s^m)=mA(s)$. Si $t$ est un
autre entier, on peut trouver pour $n$ aussi grand qu'on veut $m$
tel que $s^n\leq t^n<s^{m+1}.$ En déduire en utilisant la
monotonie (axiome 2) que $\frac mn\leq \frac{A(t)}{A(s)}\leq\frac
mn+\frac 1n$ et finalement que $A(t)=K\log t$.

\quest 2) Supposons que $p_i=\frac{n_i}{\sum_1^n n_i}$ sont des
probabilités commensurables.  Montrer en utilisant à nouveau
l'axiome 3 que
$$K \log \sum n_i=H(p_1, \dots,\; p_n)+K\sum p_i \log n_i.$$

\quest 3) Traiter ensuite le cas non commensurable en approchant
les $p_i$ par des rationnels et en utilisant l'axiome 2 de
continuité.
 \fexer



%\dexer {\bf Entropie jointe, entropie conditionnelle} Soient $X,$ $Y$  deux variables
%aléatoires discrètes sur $\XX$ et $\XX$ respectivement, de distribution jointe
%$p(x,y)$. On appelle probabilité conditionnelle de $Y$ sachant $X$ la fonction
%$p(y|x)=\frac{p(x,y)}{p(x)}$.%
%
%\quest Montrer que pour chaque $x$ fixé, la distribution $p(y|x)$ est une
%distribution de probabilité discrète sur $\XX$.

%On définit l'entropie jointe de $X$ et $Y$ par
%$$H(X,Y)=-\sum_{x\in\XX}\sum_{y\in \XX}p(x,y)\log p(x,y)=-E\log p(X,Y).$$
%On définit l'entropie conditionnelle $H(Y|X)$ par
%$$H(Y|X)=\sum_{x\in \XX}p(x)H(Y|Y=x)=-\sum_{x\in \XX}p(x)\sum_{y\in \XX}p(x|y)\log
%p(y|x).$$

%\quest Montrer que $H(Y|X)=-\E_{p(x,y)} \log p(Y|X).$


%\quest Montrer que
%\begin{equation} \label{entropierelatives'ajoute} H(X,Y)=H(X)+H(Y|X)\hbox{ et que }
%H(X)-H(X|Y)=H(Y)-H(Y|X).
%\end{equation}
%\fexer


\dexer{Entropie relative et information mutuelle}

\quest Soit deux distributions de probabilité $p(x)$ et $q(x)$. On
appelle  distance de Kullback Leibler, ou entropie relative des
deux distributions $p(x)$ et $q(x)$ la quantité
$$D(p||q)=\sum_{x\in \XX} p(x)\log \frac{p(x)}{q(x)}=\E_p \log \frac{p(X)}{q(X)}.$$

L'entropie relative est une mesure de la distance entre deux
distributions.

Soient deux variables aléatoires discrètes $X$ et $Y$ avec une
distribution jointe $p(x,y)$.  On note $p(x)= \sum_{y\in \XX}
p(x,y)$ et $p(y)=\sum_{x\in \XX} p(x,y)$ les deux distributions
marginales de $X$ et $Y$ respectivement. Alors on appelle
information mutuelle $I(X,Y)$ l'entropie relative entre la
distribution jointe $p(x,y)$ et la distribution produit
$p(x)p(y)$,
$$I(X, Y)=\sum_{x\in \XX}\sum_{y\in \XX} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}=
D(p(x,y)||p(x)p(y))=\E_{p(x,y)}\log\frac{p(X,Y)}{p(X)p(Y)}.$$

\quest Démontrer que
$$I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X),
$$
$$I(X,Y)=I(Y,X)=H(X)+H(Y)-H(X,Y),\quad I(X,X)=H(X).$$
Remarquer que $I(X,Y)=0$ si  $X$ et $Y$ sont indépendantes.

\quest Soient $X_1,$, $X_2$, ..., $X_n$ des variables aléatoires
discrètes de distribution jointe $p(x_1,\; x_2,\dots x_n)$.
Montrer en utilisant uniquement (\ref{entropierelatives'ajoute})
que

\begin{equation} \label{chaineruleentropies}
H(X_1,\; X_2,\dots X_n)=\sum_{i=1}^n H(X_i|X_{i-1},\dots , X_1).
\end{equation}

\quest Montrer en utilisant les définitions de $D$ et de la
probabilité conditionnelle que
$$D(p(x,y)||q(x,y))=D(p(x)||q(x)) +D(p(y|x)||q(y|x)).$$
\fexer

\dexer{\bf  On rappelle l'inégalité de Jensen :} Soit $f$ une
fonction convexe et $X$ une variable aléatoire discrète, alors
$$\E f(X)\geq f(\E X).$$ Si $f$ est strictement convexe, l'égalité
n'est vraie que si $X=\E X$ presque sûrement, i.e. $X$ est
constante.  Montrer cette inégalité pour une variable aléatoire
discrète.


\quest Soient $p(x)$ et $q(x)$, $x\in \XX$ deux distributions de
probabilité discrètes. En utilisant l'inégalité de Jensen
appliquée au logarithme, qui est strictement concave, montrer que
$$D(p||q)\geq 0$$
 et que l'égalité est vraie si et seulement si $p(x)=q(x)$ pour tout $x$.

 \quest En déduire que pour tout couple de variables aléatoires, $(X, Y)$, on a
 $$I(X,Y)\geq 0 $$ et égalité si et seulement si $X$ et $Y$ sont indépendantes.

 \quest En déduire aussi que $H(X)\leq \log |\XX|,$ où $|\XX|$ représente le nombre
 d'éléments dans l'image de $X$ et il y a égalité si et seulement si $X$ a une
 distribution uniforme sur $\XX$. (Exprimer que $D(p||u)\geq 0$, où $u(x)=\frac
 1{|\XX|}$ est la distribution uniforme sur $\XX$).

 \quest Déduire aussi de la positivité de l'entropie relative que $H(X|Y)\leq H(X)$.

 \quest Déduire finalement que
 $$H(X_1,\; X_2,\dots X_n)\leq \sum_{i=1}^n H(X_i),$$
  et que l'on a égalité si et seulement si les $X_i$ sont indépendantes. (Utiliser la
  question précédente et
  (\ref{chaineruleentropies})).

 \fexer
