\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}