\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} \usepackage{fig4tex} %\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{\eps}{\epsilon} \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 2cm \begin{center} {\large \bf Module D4MA1C20, Compléments magistère} {\Large \bf Devoir n$^0$2} {\Large \bf A rendre le 4 mai 2012} \end{center} \vskip 1cm \nosol \begin{exercice}{La tour rase t'elle les murs ?} On s'intéresse à la marche au hasard stationnaire $\Xi=(X_n)_{n\in\Z}$ de la tour sur un jeu d'échecs $8\times 8$. On se demande quelle proportion du temps la marche passe sur le pourtour du jeu. \begin{exoliste} \item Soit $\Upsilon=(Y_n)_{n\in\Z}$ une chaîne de Markov irréductible et stationnaire, à valeurs dans un ensemble fini $E$. Soit $f:E\to\R$ une fonction. Montrer que la suite de variables aléatoires $\sum_{k=1}^{n}f(Y_k)$ converge presque sûrement. Quelle et sa limite ? \item Montrer que la marche au hasard $\Xi$ est irréductible et apériodique. Quelle est la mesure stationnaire~? \item Montrer que la proportion du temps, entre les temps $1$ et $n$, que la marche passe sur le pourtour converge presque sûrement. Quelle est sa limite ? \item Qu'en est il si on remplace la tour par le roi ? \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item Soit $\mu$ la mesure sur $E^{\Z}$ invariante par le décalage $T$ associée à la chaîne. Soit $g:E^{\Z}\to\R$ la fonction définie par $g((x_n)_{n\in\Z})=x_0$. Alors $g$ est mesurable pour la tribu produit. En effet, $g$ ne prend qu'un nombre fini de valeurs, et les ensembles $g^{-1}(t)=\bigcup_{f(x)=t}\{x_0=x\}$ sont des réunions finies de cylindres. Elle est bornée donc intégrable. Par hypothèse, $\Upsilon$ est irréductible, donc $\mu$ est ergodique pour $T$. D'après le Théorème Ergodique de Birkhoff, la suite de fonctions \begin{eqnarray*} g_n=\frac{1}{n}\sum_{k=1}^{n}g\circ T^k \end{eqnarray*} converge presque partout vers $\E(g)$. Par conséquent, $\frac{1}{n}\sum_{k=1}^{n}f(Y_n)$ converge presque sûrement vers $\E(Y_0)$. \item La tour peut aller de toute position vers toute autre position en 2 pas, donc sa marche est irréductible. Elle peut revenir à son point de départ en 3 pas, donc elle est apériodique. La distribution stationnaire est unique. Le graphe de la marche possède 64 sommets et 64$\times$14/2=448 arêtes, toutes ayant le même poids. La matrice des probabilités de transitions est symétrique, et donc bi-stochastique. La distribution stationnaire est uniforme. \item On applique le résultat de la question 1. à la fonction caractéristique $f$ des cases du pourtour (il y en a $28$). La proportion du temps passé sur le pourtour vaut $\frac{1}{n}\sum_{k=1}^{n}f(X_n)$, elle converge presque sûrement vers la moyenne de $f$ pour la distribution stationnaire, qui vaut $28/64=7/16$. La tour passe donc un peu moins de la moitié de son temps sur le pourtour de l'échiquier. \item La marche du roi est aussi irréductible et apériodique, elle se déroule sur un graphe dont 4 sommets ont 3 arêtes, 24 ont 5 arêtes et 36 ont 8 arêtes. La distribution stationnaire donne un poids de $3/420$ aux angles, $5/420$ aux aux cases du pourtour, et $8/420$ aux cases intérieures. L'espérance, relativement à cette distribution, de la fonction $f$ est $4\times 3/420+24\times 5/420=132/420=0.31...$. On conclut que le roi passe bien moins de temps sur le pourtour du jeu que la tour. \end{exoliste} \end{sol} \begin{exercice}{Capacité du canal radio-shadok} Radio-shadok émet au moyen d'un poste alimenté par la génératrice d'un vélo. La qualité du signal est assez mauvaise. Quand on l'écoute, on prend souvent un mot pour un autre, suivant la matrice de probabilités de transition suivante. \begin{center} \begin{tabular}{|c|cccc|} \hline &ga&bu&zo&meu \\ \hline ga&3/4&1/8&1/16&1/16 \\ bu&1/8&3/4&1/16&1/16 \\ zo&1/8&1/8&1/2&1/4\\ meu&1/8&1/8&1/4&1/2\\ \hline \end{tabular} \end{center} On se demande comment calculer la capacité de ce canal. \begin{exoliste} \item Soit $P$ la matrice des probabilités de transition d'un canal. Montrer que le calcul de la capacité $\kappa(P)$ revient à chercher la distribution de probabilité (matrice ligne $p$) qui maximise $H(pP)-ph(P)$, où $h(P)$ est le vecteur colonne dont les composantes sont les entropies des lignes de $P$. \item On suppose $P$ carrée et inversible. Montrer que $\kappa(P)= \sup_q I$ où $I(q)=H(q)-qe$, pour un vecteur colonne $e$ que l'on précisera. \item Montrer que $I$ est concave, qu'elle atteint son maximum en une distribution $q_0$ qui charge tous les points. En utilisant le théorème des extrema liés, donner une expression pour $q_0$ qui s'apparente à la distribution de Maxwell-Boltzmann. \item En déduire une formule exacte pour $\kappa(P)$. Application numérique : calculer la capacité de radio-shadok (une valeur approchée suffit). \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item Soit $X$ une variable aléatoire de loi $p$. Si on met $X$ en entrée du canal, la variable aléatoire $Y$ lue en sortie a pour loi $q$ donnée par \begin{eqnarray*} q(y)=\sum_{x\in E_X}p_X(x)P_{xy}, \end{eqnarray*} soit $q=pP$. Pour chaque $x\in E_X$, la variable conditionnée $Y|X=x$ a pour loi \begin{eqnarray*} p_{Y|X=x}(y)=\PP(Y=y|X=x)=P_{xy}, \end{eqnarray*} donc $H(Y|X=x)=h(P)(x)$ est l'entropie de la $x$-ème ligne, et \begin{eqnarray*} H(Y|X)=\sum_{x\in X}p_X(x)h(P)(x)=ph(P). \end{eqnarray*} Il vient \begin{eqnarray*} I(X;Y)=H(Y)-H(Y|X)=H(pP)-ph(P). \end{eqnarray*} C'est cette quantité qu'il faut maximiser sur l'ensemble $\mathcal{P}(E_X)$ des distributions de probabilité sur $E_X$. \item Si $P$ est inversible, $q=pP$ détermine $p=qP^{-1}$. Maximiser $H(pP)-ph(P)$ sur $\mathcal{P}(E_X)$ équivaut à maximiser $H(q)-qP^{-1}h(P)$ sur $\mathcal{P}(E_Y)$. On pose $e=P^{-1}h(P)$ et $\mathcal{E}(q)=qe$. Il vient \begin{eqnarray*} \kappa(P)=\sup_{q\in\mathcal{P}(E_Y)}H(q)-\mathcal{E}(q). \end{eqnarray*} \item $I$ est la différence d'une entropie (qui est concave) et d'une forme linéaire, c'est donc une fonction strictement concave. Elle est continue sur le compact $\mathcal{P}(E_Y)$ donc elle atteint son maximum. Par stricte concavité, le maximum est atteint en un point $q_0$ qui est unique et appartient à l'intérieur de $\mathcal{P}(E_Y)$. Au voisinage de ce point, la fonction $I$ est différentiable. L'ensemble $\mathcal{P}(E_Y)$ est contenu dans l'espace vectoriel des fonctions réelles sur $E_Y$. C'est un polyèdre convexe de l'hyperplan d'équation $\phi=0$, où $\phi(q)=\sum_{y\in E_Y}q(y)$. D'après le Théorème des extrema liés, en $q_0$, les formes linéaires $dI=\sum_{y\in E_Y}(-\log_2 (q_0(y))-1-e(y))dq(y)$ et $d\phi=\sum_{y\in E_Y}dq(y)$ sont proportionnelles. Il existe un réel $\lambda$ tel que pour tout $y\in E_Y$, \begin{eqnarray*} -\log_2 (q_0(y))-1-e(y)=\lambda. \end{eqnarray*} Cela donne $q_0 (y)=2^{-\lambda-1-e(y)}$, et $\lambda$ est déterminé par la condition \begin{eqnarray*} \sum_{y\in E_Y}2^{-\lambda-1-e(y)}=1. \end{eqnarray*} Il vient $\lambda=-1+\log_2(\sum_{y\in E_Y}2^{-e(y)})$ et \begin{eqnarray*} q_0 (y)=\frac{2^{-e(y)}}{\sum_{y\in E_Y}2^{-e(y)}}. \end{eqnarray*} \item On calcule \begin{eqnarray*} I(q_0)&=&H(q_0)-q_0 e\\ &=&\sum_{y\in E_Y}(\lambda+1+e(y))q_0 (y)-q_0(y)e(y)\\ &=&\sum_{y\in E_Y}(\lambda+1)q_0 (y)\\ &=&\lambda+1=\log_2(\sum_{y\in E_Y}2^{-e(y)}). \end{eqnarray*} Application numérique : \begin{eqnarray*} P^{-1}=\frac{1}{10}\begin{pmatrix} 14&-2&-1&-1\\ -2&-14&-1&-1\\ -2&-2&27&13\\ -2&-2&-13&27 \end{pmatrix},\quad h(P)=\begin{pmatrix} (19-6\log_2 3)/8\\ (19-6\log_2 3)/8\\ 7/4\\ 7/4 \end{pmatrix},\quad e=\begin{pmatrix} 1.0735\\ 1.0735\\ 1.9755\\ 1.9755 \end{pmatrix} \end{eqnarray*} puis \begin{eqnarray*} \sum_{y\in E_Y}2^{-e(y)}=1.4589,\quad \kappa=\log_2(1.4589)=0.5449. \end{eqnarray*} \end{exoliste} \end{sol} \end{document} \begin{exercice}{} \begin{exoliste} \item \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item \end{exoliste} \end{sol} function k=capacite(P) % en entrée, une matrice carrée stochastique inversible, % matrice des probabilités de transition d'un canal de % transmission sans mémoire. % en sortie, la capacité du canal for i=1:size(P,1) h(i)=entropie(P(i,:)); end k=log2(sum(2.^(-inv(P)*h'))); \begin{eqnarray*} \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline 0&0&0&0&0&0&0&0 \\ \hline 0&1&1&1&1&1&1&0 \\ \hline 0&1&2&2&2&2&1&0 \\ \hline 0&1&2&3&3&2&1&0 \\ \hline 0&1&2&3&3&2&1&0 \\ \hline 0&1&2&2&2&2&1&0 \\ \hline 0&1&1&1&1&1&1&0 \\ \hline 0&0&0&0&0&0&0&0 \\ \hline \end{tabular} \end{eqnarray*} \begin{exercice}{Equipartition jointe pour un couple de chaînes de Markov} Soient $\Xi=(X_n)_{n\geq 1}$ et $\Upsilon=(Y_n)_{n\geq 1}$ deux chaînes de Markov irréductibles à valeurs dans des ensembles finis $E_X$ et $E_Y$ respectivement. On considère aussi la chaîne de Markov $Z=(Z_n=(X_n,Y_n))_{n\geq 1}$ à valeurs dans $E_X \times E_Y$. On note $p_{X_1^n}$ (resp. $p_{Y_1^n}$, resp. $p_{Z_1^n}$) la loi jointe de $(X_1,\ldots,X_n)$ (resp. $(Y_1,\ldots,Y_n)$ resp. $(Z_1,\ldots,Z_n)$). Soient $n\geq 1$ 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_1^n} (x_1,\ldots,x_n))-H(\Xi)|<\eps$. \item $|-\frac{1}{n}\log_2 (p_{Y_1^n} (y_1,\ldots,y_n))-H(\Upsilon)|<\eps$. \item $|-\frac{1}{n}\log_2 (p_{Z_1^n} (x_1 ,y_1)\ldots (x_n ,y_n))-H(Z)|<\eps$. \end{enumerate} \begin{exoliste} \item Montrer que l'information mutuelle $I(X_n;Y_n)$ converge, lorsque $n$ tend vers l'infini, vers un nombre noté $I(\Xi,\Upsilon)$. \item Montrer que $\PP((Z_1,\ldots,Z_n) \in T)$ tend vers $1$ quand $n$ tend vers $+\infty$. \item Montrer que $|T|\leq 2^{n(H(Z)+\eps)}$. \item Soit $\tilde{\Xi}=(\tilde{X}_n)_{n\geq 1})$ (resp. $\tilde{\Upsilon}=(\tilde{Y}_n)_{n\geq 1})$) une chaîne de Markov stationnaire de même matrice de transition que $\Xi$ (resp. $\Upsilon$). Soit $\tilde{Z}=(\tilde{Z}_n =(\tilde{X}_n,\tilde{Y}_n))_{n\geq 1}$. On suppose $Z$ et $\tilde{Z}$ indépendantes. Montrer que pour $n$ assez grand, \begin{eqnarray*} (1-\eps)2^{-n(I(X;Y)+3\eps)}\leq\PP((\tilde{Z}_1,\ldots,\tilde{Z}_n) \in T)\leq 2^{-n(I(X;Y)-3\eps)}. \end{eqnarray*} \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item \item D'après le Théorème de Shannon-McMillan-Breiman, les variables aléatoires $-\frac{1}{n}\log_2 p_{X_1^n}(X_1,\ldots,X_n)-H(\Xi)$ et $-\frac{1}{n}\log_2 p_{Y_1^n}(Y_1,\ldots,Y_n)-H(\Upsilon)$ tendent vers $0$ presque sûrement. \end{exoliste} \end{sol}