\documentclass[10pt,a4paper]{amsart}
\usepackage[ansinew]{inputenc}
%\usepackage[latin1]{inputenc}
%\usepackage[T1]{fontenc}
%\usepackage{amscd}
\usepackage{amsmath}
%\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{aclmac}
%\usepackage{setspace}
%\usepackage[francais]{babel}
\usepackage{comment}

%\paperheight=29.7cm
%\paperwidth=21cm

\setlength\textwidth{16cm}
\hoffset=-1in
\setlength\marginparsep{0cm}
\setlength\marginparwidth{0cm}
\setlength\marginparpush{0cm}
\setlength\evensidemargin{2.5cm}
\setlength\oddsidemargin{2.5cm}

\setlength\topmargin{2cm} \setlength\headheight{1cm}
\setlength\headsep{1cm} \voffset=-1in \setlength\textheight{21cm}

\newcounter{exolistec}
\newenvironment{exoliste}
   {\setcounter{exolistec}{0}
    \begin{list}{}
      {\setlength{\topsep}{0.05cm}%
       \setlength{\parsep}{0.1cm}%
       \setlength{\leftmargin}{0.8cm}%
       \setlength{\itemsep}{0.05cm}%
       \setlength{\parskip}{\parsep}%
       \setlength{\labelwidth}{0.6cm}%
       \setlength{\labelsep}{0cm}%
       \setlength{\listparindent}{0cm}%
       \renewcommand{\makelabel}
          {\addtocounter{exolistec}{1}\arabic{exolistec}-- \hfil}}}
    {\end{list}}

\newcommand{\nosol}{\excludecomment{sol}}

\pagestyle{myheadings}
\newcounter{Exo}\setcounter{Exo}{0}\def\theExo{\arabic{Exo}}
\newenvironment{exercice}[1]%
{\refstepcounter{Exo}\bigskip\par\noindent
        {\sf \theExo.\ #1\quad\hrulefill}\par}%

\newenvironment{exerciceF}[1]%
{\refstepcounter{Exo}\bigskip\par\noindent
        {\sf \theExo. \ #1\quad\hrulefill} \quad F \par}%

\newenvironment{exerciceD}[1]%
{\refstepcounter{Exo}\bigskip\par\noindent
        {\sf \theExo.\ #1\quad\hrulefill}\quad D \par}%

\newenvironment{sol}%
{\bigskip\par\noindent
        {\sf {\bf Solution :}}\par}%

\newtheorem{thm}{Th\'eor\`eme}
\newtheorem{lem}[thm]{Lemme}
\newtheorem{defn}[thm]{D\'efinition}

\theoremstyle{definition}
%\newtheorem*{sol}{Solution}
\newtheorem*{rmq}{Remarque}

\setlength{\parindent}{0mm} \setlength{\parskip}{1.5mm}

\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\transposee}[1]{{\vphantom{#1}}^{\mathit t}{#1}}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\DeclareMathOperator{\Card}{Card}

\usepackage[pdftex]{graphicx}

\pagestyle{myheadings} \markboth{\hfill Master MFA}{2011/2012 \hfill }





\begin{document}
\thispagestyle{empty}
Master MFA première année \hfill 2011-2012

\vskip 1cm

\begin{center}
{\large \bf Module D4MA1C20, Compléments magistère}

{\Large \bf Feuille de TD n$^0$1}

\end{center}

\vskip 1cm

\nosol

\begin{exercice}{Battage de cartes}

On bat un jeu de $n$ cartes comme suit. On tire une carte au hasard du paquet, et on la replace dans le paquet au hasard (on a le droit de la remettre en-dessous ou au-dessus du paquet). On obtient ainsi une variable aléatoire $X$ à valeurs dans l'ensemble des permutations de $n$ cartes.

\begin{exoliste}

\item Calculer la distribution de $X$.

\item Quelle est l'entropie de $X$ ?

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Il y a $n$ choix équiprobables possibles $T$ pour la carte tirée, et $n$ positions équiprobables possibles $R$ lors du replacement de la carte. On numérote les positions de replacement comme suit : 1 désigne le dessus du tas, 2 en dessous de la première carte,..., $n$ désigne le dessous du tas.
Les variables $T$ et $R$, à valeurs dans $\{1,\ldots,n\}$, sont indépendantes. Il y a trois cas de figures particuliers.
\begin{itemize}
  \item Si $R=T$, on remet la carte à l'endroit où on l'a prise, la permutation résultante est l'identité.
  \item Si $R=T-1$, la permutation résultante est la transposition qui échange les cartes $T-1$ et $T$.
  \item Si $R=T+1$, la permutation résultante est la transposition qui échange les cartes $T$ et $T+1$.
\end{itemize}
Dans les autres cas, on peut retrouver quelle carte a été déplacée en examinant le paquet : c'est celle qui n'est pas à sa place. On obtient des permutations deux à deux distinctes. La distribution de $X$ vaut donc 
\begin{itemize}
  \item $\PP(X=id)=\sum_{i=1}^n \PP(T=i$ et $R=i)=n\frac{1}{n}\frac{1}{n}=\frac{1}{n}$.
  \item Pour chaque transposition $\tau_i$ échangeant $i$ et $i+1$ ($i=1,\ldots,n-1$), $\PP(X=\tau_i)=\PP(T=i$ et $R=i+1)+\PP(T=i+1$ et $R=i)=\frac{2}{n^2}$.
  \item Pour les $n^2 -n-2(n-1)$ autres permutations $\sigma$ obtenues, $\PP(X=\sigma)=\frac{1}{n^2}$.
\end{itemize}

\item On calcule
\begin{eqnarray*}
H(X)=-\frac{1}{n}\log_2(\frac{1}{n})-(n-1)\frac{2}{n^2}\log_2 (\frac{2}{n^2})-(n^2 -3n+2)\log_2 (\frac{1}{n^2})\sim\log_2 (n^2).
\end{eqnarray*}

\end{exoliste}
\end{sol}

\begin{exercice}{Loi géométrique}

On joue à pile ou face. Soit $X$ la variable aléatoire ``premier instant où on tire face''. $X$ est à valeurs dans $\N\setminus\{0\}$.

\begin{exoliste}

\item Calculer la loi de la variable $X$.

\item Calculer l'entropie de $X$.

\item Trouver une suite de sous-ensembles $S_i \subset\N\setminus\{0\}$ de sorte qu'en posant la suite de questions ``$X\in S_i$~?'', on trouve le plus vite possible la valeur de $X$, en moyenne.

\end{exoliste}
\end{exercice}


\begin{sol}
\begin{exoliste}

\item Notons $Y_i \in\{P,F\}$ le résultat du $i$-ème tirage. Clairement, $X> k\Leftrightarrow Y_1 =\cdots=Y_k =P$, donc $\PP(X>k)=2^{-k}$, $p_X (k)=\PP(X>k-1)-\PP(X>k)=2^{-k+1}-2^{-k}=2^{-k}$.

\item Par définition, $H(X)=\sum_{k=1}^{\infty}-2^{-k}\log_2 (2^{-k})=\sum_{k=1}^{\infty}2^{-k}k$. Posons 
\begin{eqnarray*}
F(z)=\sum_{k=1}^{\infty}z^{k}2^{-k}=\frac{1}{1-\frac{z}{2}}-1=\frac{z}{2-z}.
\end{eqnarray*}
On calcule $F'(z)=\frac{2}{(2-z)^2}$. Mais aussi $F'(z)=\sum_{k=1}^{\infty}kz^{k-1}2^{-k}$, donc $H(X)=F'(1)=2$.

\item On pose $S_i =\{i\}$. Alors le nombre de questions nécessaire est exactement $X$. En moyenne, il vaut $\E(X)=\sum_{k=1}^{\infty}kp_X (k)=2$. 

Cette stratégie est optimale. C'est un théorème du chapitre 2.

\end{exoliste}
\end{sol}

\begin{exercice}{Permis de conduire}

Soient $X$, $Y$ et $Z$ les variables booléennes suivantes. $X$ indique ma réussite au permis de conduire, $Y$ ma réussite à l'épreuve théorique (code) et $Z$ ma réussite à l'épreuve pratique (conduite). $Y$ et $Z$ sont indépendantes, de loi $\mathcal{B}(\frac{1}{2})$. 

\begin{exoliste}

\item Exprimer $X$ en fonction de $Y$ et $Z$. Calculer la loi du couple $(X,Y)$. 

\item Calculer les entropies du couple $(X,Y)$, de $X$ et de $Y$. En déduire l'entropie conditionnelle $H(X|Y)$.

\item Calculer la loi conditionnelle de $X$ sachant que $Y=1$. Vérifier que son entropie $H(X|Y=1)>H(X)$.

\item Calculer la loi conditionnelle de $X$ sachant que $Y=0$. Vérifier en revenant à la définition que $H(X|Y)\leq H(X)$.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item $X=YZ$, d'où le tableau
\begin{eqnarray*}
p_{(X,Y)}(0,0)=\frac{1}{2},\quad
p_{(X,Y)}(1,0)=0,\quad
p_{(X,Y)}(0,1)=p_Y (0)=\frac{1}{4},\quad
p_{(X,Y)}(1,1)=p_Y (0)=\frac{1}{4}.
\end{eqnarray*}

\item On calcule la loi marginale $p_X (0)=\frac{3}{4}$, $p_X (1)=\frac{1}{4}$.
\begin{eqnarray*}
H(X)&=&-\frac{3}{4}\log_2(\frac{3}{4})-\frac{1}{4}\log_2 (\frac{1}{4})=0.8113,\\
H(Y)&=&-\frac{1}{2}\log_2(\frac{1}{2})-\frac{1}{2}\log_2 (\frac{1}{2})=1,\\
H(X,Y)&=&-\frac{1}{2}\log_2(\frac{1}{2})-\frac{1}{4}\log_2(\frac{1}{4})-\frac{1}{4}\log_2(\frac{1}{4})=\frac{3}{2}.
\end{eqnarray*}
On en déduit $H(X|Y)=H(X,Y)-H(Y)=\frac{3}{2}-1=\frac{1}{2}$.

\item On calcule la loi conditionnelle $p_{X|Y=1}(0)=p_{X|Y=1}(1)=\frac{1}{2}$, d'où
\begin{eqnarray*}
H(X|Y=1)=-\frac{1}{2}\log_2(\frac{1}{2})-\frac{1}{2}\log_2(\frac{1}{2})=1>H(X).
\end{eqnarray*}
Autrement dit, le fait d'avoir réussi au code augmente l'incertitude sur la réussite au permis.

\item Lorsque $Y=0$, $X=0$, donc $H(X|Y=0)=0$ : échouer au code réduit à $0$ l'incertitude sur la réussite au permis. Cela compense le fait que $H(X|Y=1)>H(X)$. D'ailleurs, la moyenne
\begin{eqnarray*}
H(X|Y)=p(Y=0)H(X|Y=0)+p(Y=1)H(X|Y=1)=\frac{1}{2}\times 0 +\frac{1}{2}\times 1=\frac{1}{2}
\end{eqnarray*}
est bien égale à $H(X,Y)-H(Y)\leq H(X)$.

\end{exoliste}
\end{sol}

\begin{exercice}{Lancer de dés}

Soit $X$ le résultat du lancer d'un dé non pipé, i.e. le chiffre lu sur la face supérieure. Soit $Y$ le chiffre lu sur la face latérale tournée vers le joueur.
\begin{exoliste}

\item Calculer l'entropie conditionnelle $H(X|Y)$.

\item En déduire l'information mutuelle $I(X;Y)$.

\item Calculer directement l'information mutuelle.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Pour tout résultat $y\in\{1,\ldots,6\}$, la loi conditionnelle $p_{X|Y=y}$ est uniformément répartie sur un ensemble à 4 éléments. Par conséquent, son entropie $H(X|Y=y)=\log_2 (4)=2$, et la moyenne $H(X|Y)$ vaut $2$.

\item $X$ est uniformément répartie sur un ensemble à 6 éléments. Par conséquent, son entropie $H(X)=\log_2 (6)$. Il vient $I(X;Y)=H(X)-H(X|Y)=\log_2 (6)-2=\log_2 (\frac{3}{2})$.

\item La loi du couple $(X,Y)$ est uniformément répartie sur les 24 couples de chiffres qu'on peut observer sur deux faces contigües d'un dé. Par conséquent, l'information mutuelle vaut
\begin{eqnarray*}
I(X;Y)=\sum_{(x,y)}p_{(X,Y)}(x,y)\log_2 (\frac{p_{(X,Y)}(x,y)}{p_{X}(x)p_Y (y)})=\log_2(\frac{1/24}{1/6 \cdot 1/6})=\log_2 (\frac{3}{2}).
\end{eqnarray*}

\end{exoliste}
\end{sol}

\begin{exercice}{Information contenue dans la réponse à une question}

Soit $X$ une variable aléatoire à valeurs dans un ensemble $E$. On pose une question au sujet de $X$, et on se demande de combien l'incertitude sur $X$ a diminué. Autrement dit, on se donne un sous-ensemble $S\subset E$, on note $Y=1_{\{X\in S\}}$ la réponse à la question ``$X$ tombe-t-elle dans $S$ ou non~?''

\begin{exoliste}

\item Exprimer la diminution d'entropie $H(X)-H(X|Y)$ en fonction de $q=\PP(X\in S)$.

\item En déduire que l'entropie diminue d'au plus $1$ bit.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Lorsque $X$ est connu, $Y$ l'est aussi, donc l'entropie conditionnelle $H(Y|X)=0$. On utilise la formule
\begin{eqnarray*}
H(X)-H(X|Y)=I(X;Y)=H(Y)-H(Y|X)=H(Y)=-q\log_2 (q)-(1-q)\log_2 (1-q).
\end{eqnarray*}

\item On sait que $H(\mathcal{B}(q))$ atteint son maximum $1$ en $q=\frac{1}{2}$, donc $H(X|Y)\geq H(X)-1$.

\end{exoliste}
\end{sol}


\begin{exercice}{Entropie des fonctions de $X$}

Soit $X$ une variable aléatoire à valeurs dans $E_X$, et $f:E_X \to\R$ une fonction. 

\begin{exoliste}

\item Montrer que $H(f(X))\leq H(X)$, avec égalité si et seulement si $f$ est injective sur le support de la loi de $X$.

\item Redémontrer l'inégalité $H(f(X))\leq H(X)$ en calculant $H(X,f(X))$ de deux manières différentes.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Par définition,
\begin{eqnarray*}
H(f(X))&=&-\sum_{y\in f(E_X)}\PP(f(X)=y)\log_2 (\PP(f(X)=y))\\
&=&-\sum_{y\in f(E_X)}(\sum_{x\in f^{-1}(y)}p_X (x))\log_2 (\sum_{x\in f^{-1}(y)}p_X (x))\\
&\leq&-\sum_{y\in f(E_X)}\sum_{x\in f^{-1}(y)}p_X (x)\log_2 (p_X (x))\\
&=&H(X).
\end{eqnarray*}
L'égalité entraîne que, pour chaque $y\in f(E_X)$, un seul élément de $f^{-1}(x)$ à une probabilité non nulle. Autrement dit, que $f$ est injective sur le support de la loi de $X$.

\item On écrit $H(X,f(X))=H(X)+H(f(X)|X)$. Mais quand $X$ est connu, $f(X)$ l'est aussi, donc $H(f(X)|X)=0$. D'où
\begin{eqnarray*}
H(X)=H(X,f(X))=H(f(X),X)=H(f(X))+H(X|f(X))\geq H(f(X)),
\end{eqnarray*}
car une entropie, même conditionnelle, est toujours positive ou nulle. 

\end{exoliste}
\end{sol}

\begin{exercice}{Distance associée à l'entropie conditionnelle}

Soient $X$ et $Y$ deux variables aléatoires. On pose $\rho(X,Y)=H(X|Y)+H(Y|X)$.

\begin{exoliste}

\item Vérifier que $\rho$ est positive ou nulle. Montrer que
\begin{eqnarray*}
\rho(X,Y)=2H(X,Y)-H(X)-H(Y).
\end{eqnarray*}

\item Montrer que $\rho(X,Y)=0$ si et seulement si il existe une bijection $f$ du support de la loi de $X$ sur le support de la loi de $Y$ telle que $Y=f(X)$ presque partout.

\item Soient $X$, $Y$ et $Z$ trois variables aléatoires. En majorant $H(X,Z)$ par $H(X,Y,Z)$ (pourquoi peut on le faire ?), montrer que 
\begin{eqnarray*}
H(X|Z)\leq H(X|Y)+H(Y|Z).
\end{eqnarray*}

\item En déduire que $\rho$ est une distance sur l'ensemble des variables aléatoires à valeurs dans $E$, modulo permutation de $E$.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item $\rho$ est une somme d'entropies donc est positive ou nulle. Par définition,
\begin{eqnarray*}
\rho(X,Y)=H(X|Y)+H(Y|X)=H(X,Y)-H(Y)+H(X,Y)-H(X)=2H(X,Y)-H(X)-H(Y).
\end{eqnarray*}

\item $H(X|Y)$ est la moyenne des entropies des lois conditionnelles $p_{X|Y=y}$, qui sont toutes positives ou nulles. Si $H(X|Y)=0$, alors pour tout $y\in E_Y$ de probabilité positive, $H(p_{X|Y=y})=0$, donc $p_{X|Y=y}$ est concentrée sur une seule valeur qu'on note $f(y)$. Autrement dit, $X=f(Y)$ presque sûrement. Si $\rho(X,Y)=0$, alors $X=f(Y)$ presque sûrement et $Y=g(X)$ presque sûrement, donc $g\circ f=id$ sur le support de $p_Y$, $f\circ g=id$ sur le support de $p_X$, donc $f$ est une bijection sur le support de $p_Y$.

\item On vérifie que $H(X,Z)=H(X,Y,Z)-H(Y|X,Z)\leq H(X,Y,Z)$, et on en déduit que
\begin{eqnarray*}
H(X|Z)&=&H(X,Z)-H(Z)\\
&\leq&H(X,Y,Z)-H(Z)\\
&=&H(X,Y,Z)-H(Y,Z)+H(Y,Z)-H(Z)\\
&=&H(X|Y,Z)+H(Y|Z)\\
&\leq&H(X|Y)+H(Y|Z).
\end{eqnarray*}
A la dernière ligne, on a utilisé le principe ``conditionner diminue l'entropie''.

\item En symétrisant le résultat de la question précédente, on obtient l'inégalité triangulaire. Pour deux variables aléatoires $X$ et $Y$ à valeurs dans $E$, on a prouvé que $\rho(X,Y)=0$ si et seulement si il existe une bijection $\phi:supp(p_X)\to supp(p_Y)$ telle que $Y=\phi(X)$. Comme $E\setminus supp(p_X)$ et $E\setminus supp(p_Y)$ ont même nombre d'éléments, il existe une bijection $\phi'$ entre ces ensembles. $\phi$ et $\phi'$ mises bout à bout donnent une permutation $\sigma$ de $E$ telle que $\sigma(X)=Y$. On conclut que
 \begin{eqnarray*}
\rho(X,Y)=0\quad\Leftrightarrow\quad\exists \sigma\in \mathfrak{S}_{E}\textrm{ telle que }Y=\sigma(X).
\end{eqnarray*}

\end{exoliste}
\end{sol}

\begin{exercice}{Concavité de l'entropie ?}

Donner un exemple de couple de variables aléatoires $(X,Y)$ tel que
$H(\frac{X+Y}{2})<\frac{H(X)+H(Y)}{2}$.

\end{exercice}

\begin{sol}

Prendre une variable aléatoire $X$ non p.s. constante (par exemple, $\mathcal{B}(\frac{1}{2})$. Poser $Y=-X$. Alors $\frac{X+Y}{2}=0$ est d'entropie nulle, alors que $H(Y)=H(X)>0$.

Moralité : concavité de l'entropie ne veut pas dire comme fonction de la variable, mais comme fonction de sa loi.

\end{sol}

\end{document}

\begin{exercice}{}
\begin{exoliste}

\item 

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item 

\end{exoliste}
\end{sol}

