\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} \def\eps{\epsilon} \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 .5cm \begin{center} {\large \bf Module D4MA1C20, Compléments magistère} {\Large \bf Feuille de TD n$^0$6} \end{center} \vskip .5cm \nosol \begin{exercice}{Propriétés élémentaires de l'entropie des partitions} Soient $\alpha=(A_x)_{x\in E_{\alpha}}$ et $\beta=(B_y)_{y\in E_{\beta}}$ deux partitions mesurables finies d'un espace probabilisé $(\Omega,\mathcal{B},\mu)$. On note $f_{\alpha}:\Omega\to E_{\alpha}$ l'application qui vaut $x$ sur $A_x$. Inversement, étant donnée une application mesurable $f:\Omega\to E$ fini, on note $\alpha_{f}=(f^{-1}(x))_{x\in E}$ la partition induite. Soit $T:\Omega\to\Omega$ une application préservant la mesure. \begin{exoliste} \item Vérifier que $f\mapsto \alpha_{f}$ et $\alpha\mapsto f_{\alpha}$ sont deux opérations inverses l'une de l'autre. Vérifier que $\alpha\vee\beta=\alpha_{g}$ où $g=(f_{\alpha},f_{\beta}):\Omega\to E_{\alpha}\times E_{\beta}$. \item Vérifier que $H(\alpha)=H(f_{\alpha})$ est l'entropie de la variable aléatoire $f_{\alpha}$. Vérifier que $H(\alpha|\beta)=H(f_{\alpha}|f_{\beta})$ est l'entropie conditionnelle des variables aléatoires $f_{\alpha}$ et $f_{\beta}$. \item Vérifier que $0\leq H(\alpha|\beta)\leq H(\alpha)$. Vérifier que $H(\alpha\vee\beta)=H(\beta)+H(\alpha|\beta)$. En déduire que $H(\alpha\vee\beta)\leq H(\alpha)+H(\beta)$. \item Vérifier que $\alpha\preceq\alpha'$ si et seulement si il existe une application $g:E_{\alpha'}\to E_{\alpha}$ telle que $f_{\alpha}=g\circ f_{\alpha'}$. Vérifier que dans ce cas, $H(\alpha)\leq H(\alpha')$ et $H(\alpha|\beta)\leq H(\alpha'|\beta)$. \item Vérifier que $f_{T\alpha}=f_{\alpha}\circ T$. En déduire que $T(\alpha\vee\beta)=T(\alpha)\vee T(\beta)$, $H(\alpha|\beta)=H(T\alpha|T\beta)$. \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item C'est immédiat. \item Toutes les autres propriétés se déduisent des propriétés correspondantes de l'entropie des variables aléatoires. \end{exoliste} \end{sol} \begin{exercice}{Entropie d'un itéré} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé et $T:\Omega\to\Omega$ une transformation préservant la mesure. Soit $\alpha$ une partition mesurables finie de $\Omega$. On note $\alpha_{m}^{n}=T^{m}\alpha\vee\cdots\vee T^{n}\alpha$. \begin{exoliste} \item Montrer que $h_{\mu}(T^{-1})=h_{\mu}(T)$. \item Montrer que pour tous $m\leq n$, $H(\Xi_{\alpha_n^m})=H(\Xi_{\alpha})$. \item En déduire que pour tout $\ell$, $h_{\mu}(T^\ell)=|\ell|h_{\mu}(T)$. \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item On met un $\tilde{\hskip1em}$ sur les quantités relatives à $T^{-1}$. Pour toute partition finie $\alpha$, $\tilde{\alpha}_1^n=T^{-1}\alpha\vee\cdots\vee T^{-n}\alpha=T^{-n-1}(T\alpha\vee\cdots\vee T^{n}\alpha)$, donc $\frac{1}{n}H(T^{-1}\alpha\vee\cdots\vee T^{-n}\alpha)=\frac{1}{n}H(T\alpha\vee\cdots\vee T^{n}\alpha)$. Les deux termes ont la même limite, $H(\widetilde{\Xi_{\alpha}})=H(\Xi_{\alpha})$. En prenant le sup sur les partition finies, il vient $h_{\mu}(T^{-1})=h_{\mu}(T)$. \item Par définition, $H(\Xi_{\alpha})=\lim_{k\to+\infty}\frac{1}{k}H(\alpha_1^k)$. Or \begin{eqnarray*} (\alpha_m^n)_1^2 &=&\alpha_{m+1}^{n+1} \vee\alpha_{m+2}^{n+2}=\alpha_{m+1}^{n+2},\\ (\alpha_{m}^{n})_1^3 &=& \alpha_{m+1}^{n+1} \vee\alpha_{m+2}^{n+2} \vee\alpha_{m+3}^{n+3}=\alpha_{m+1}^{n+3},\\ &\vdots&\\ (\alpha_{m}^{n})_1^k &=& \alpha_{m+1}^{n+k}, \end{eqnarray*} donc $\frac{1}{k}H((\alpha_{m}^{n})_1^k)=\frac{1}{k}H(\alpha_{m+1}^{n+k})$ et $\frac{1}{n+k-m}H(\alpha_{m+1}^{n+k})$ tendent vers la même limite $H(\Xi_{\alpha_n^m})=H(\Xi_{\alpha})$. \item Soit $\alpha$ une partition mesurable finie. On note $\tilde{\alpha}_m^n$, etc.. les quantités relatives à la transformation itérée $T^{\ell}$. Alors \begin{eqnarray*} \widetilde{(\alpha_1^\ell)}_{1}^{k}=\alpha_1^\ell \vee \alpha_{\ell+1}^{2\ell}\vee\cdots\vee \alpha_{(k-1)\ell+1}^{k\ell}=\alpha_1^{k\ell}, \end{eqnarray*} donc $\frac{1}{k}H(\widetilde{(\alpha_1^\ell)}_{1}^{k})=\ell\frac{1}{k\ell}H(\alpha_1^{k\ell})$ tend à la fois vers $\ell H(\Xi_{\alpha})$ et vers $H(\widetilde{\Xi_{\alpha_1^{\ell}}})=H(\widetilde{\Xi_{\alpha}})$. En prenant le sup sur $\alpha$, il vient $h_{\mu}(T^k)=|\ell|h_{\mu}(T)$ pour $\ell\geq 1$. \end{exoliste} \end{sol} \begin{exercice}{Distance sur l'espace des partitions} Soit $(\Omega,\mathcal{B},\mu)$ un espace probabilisé. Soit $T:\Omega\to\Omega$ une application qui préserve la mesure. Soit $\Phi$ l'ensemble des partitions mesurables finies de $\Omega$ modulo ensembles de mesure nulle. Autrement dit, les éléments de $\Phi$ sont les classes d'équivalence de partitions, où on identifie $\alpha=(A_x)_{x\in E_{\alpha}}$ et $\beta=(B_y)_{y\in E_{\beta}}$ si pour tout $x\in E_{\alpha}$, il existe $y\in E_{\beta}$ tel que $\mu(A_x \Delta B_y)=0$. \begin{exoliste} \item Pour $\alpha$, $\beta\in\Phi$, on pose $\rho(\alpha,\beta)=H(\alpha|\beta)+H(\beta|\alpha)$. Montrer que $\rho$ est une distance sur $\Phi$. \item Montrer que pour tout $\alpha$, $\beta\in\Phi$, $|H(\alpha)-H(\beta)|\leq \rho(\alpha,\beta)$. \item Montrer que pour tout $\alpha$, $\beta$ et $\gamma\in\Phi$, $H(\beta\vee\gamma|\alpha)\leq H(\beta|\alpha)+H(\gamma|\alpha)$. \item Montrer que pour tout $n$, $H(\beta_1^n|\alpha_1^n)\leq nH(\beta|\alpha)$. \item Conclure que pour tout $\alpha$, $\beta\in\Phi$, $|H(\Xi_{\alpha})-H(\Xi_{\beta})|\leq \rho(\alpha,\beta)$. \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item On remarque d'abord que l'entropie et l'entropie conditionnelle ne changent pas si on modifie les pièces des partitions par des ensembles de mesure nulle. Par conséquent, $\rho$ est bien définie sur l'espace quotient $\Phi$. En suite, ou bien on renvoie à l'exercice 7 du TD1, où il est vérifié que $\rho$ satisfait l'inégalité triangulaire, ou bien on le redémontre directement. Soient $\alpha$, $\beta$, $\gamma\in\Phi$. Comme $\alpha\vee\gamma\preceq \alpha\vee\beta\vee\gamma$, \begin{eqnarray*} H(\alpha|\gamma)&=& H(\alpha\vee\gamma)-H(\gamma)\\ &\leq& H(\alpha\vee\beta\vee\gamma)-H(\beta\vee\gamma)+H(\beta\vee\gamma)-H(\gamma)\\ &=&H(\alpha|\beta\vee\gamma)+H(\beta|\gamma)\\ &\leq&H(\alpha|\beta)+H(\beta|\gamma), \end{eqnarray*} en vertu du principe ``conditionner diminue l'entropie''. Par définition, $\rho\geq0$. Soient $\alpha$, $\beta\in\Phi$, représentés par des partitions dont aucune pièce n'est de mesure nulle. L'égalité $\rho(\alpha,\beta)=0$ entraîne que $H(\alpha|\beta)=H(\beta|\alpha)=0$. $H(\alpha|\beta)=0$ entraîne que pour tout $y\in E_{\beta}$, la variable aléatoire conditionnée $f_{\alpha|f_{\beta}=y}$ a une entropie nulle, donc est presque partout constante, i.e. qu'il existe $x\in E_{\alpha}$ tel que $B_y \subset A_x$ à un ensemble de mesure nulle près. Réciproquement, $H(\beta|\alpha)=0$ entraîne qu'il existe $z\in E_{\beta}$ tel que $A_x \subset B_z$. Comme $B_y \subset B_z$ à un ensemble de mesure nulle près, on conclut que $y=z$ et $\mu(A_x \Delta B_y)=0$. Cela prouve que $\alpha=\beta$ dans l'espace quotient $\Phi$. Enfin, par définition, $\rho$ est symétrique, donc $\rho$ est une distance sur $\Phi$. \item On écrit \begin{eqnarray*} H(\beta)-H(\alpha) &=&H(\beta\vee\alpha)-H(\alpha|\beta)-(H(\alpha\vee\beta)-H(\beta|\alpha))\\ &=&H(\beta|\alpha)-H(\alpha|\beta), \end{eqnarray*} d'où \begin{eqnarray*} |H(\beta)-H(\alpha)|\leq H\beta|\alpha)+H(\alpha|\beta)=\rho(\alpha,\beta). \end{eqnarray*} \item On peut utiliser la formule donnée en cours $H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$ pour des variables aléatoires $X$, $Y$ et $Z$, ou bien raisonner directement avec des partitions. \begin{eqnarray*} H(\beta\vee\gamma|\alpha) &=&H(\beta\vee\gamma\vee\alpha)-H(\alpha)\\ &=&H(\beta\vee\gamma\vee\alpha)-H(\beta\vee\alpha)+H(\beta\vee\alpha)-H(\alpha)\\ &=&H(\gamma|\beta\vee\alpha)+H(\beta|\alpha)\\ &\leq&H(\gamma|\alpha)+H(\beta|\alpha), \end{eqnarray*} où on a appliqué le principe ``conditionner diminue l'entropie''. \item Avec le principe ``conditionner diminue l'entropie'', \begin{eqnarray*} H(\beta_1^n|\alpha_1^n) &\leq&\sum_{i=1}^n H(T^i \beta|\alpha_1^n)\\ &\leq&\sum_{i=1}^n H(T^i \beta|T^i \alpha)\\ &=&nH(\beta|\alpha) \end{eqnarray*} \item Il vient $\rho(\alpha_1^n|\beta_1^n)\leq n\rho(\alpha,\beta)$, d'où \begin{eqnarray*} |\frac{1}{n}H(\beta_1^n)-\frac{1}{n}H(\alpha_1^n)|\leq\rho(\alpha,\beta), \end{eqnarray*} et, en passant à la limite, $|H(\Xi_{\alpha})-H(\Xi_{\beta})|\leq \rho(\alpha,\beta)$. \end{exoliste} \end{sol} \begin{exercice}{Entropie d'une transformation périodique} Soit $T$ une transformation préservant la mesure d'un espace probabilisé $(\Omega,\mathcal{B},\mu)$. On suppose qu'il existe $k$ tel que $T^\ell =id_{\Omega}$. Que peut on dire de l'entropie métrique de $T$ ? \end{exercice} \begin{sol} On remarque que l'entropie de l'identité vaut $0$. On peut utiliser la formule $2h_{\mu}(id_{\Omega})=h_{\mu}(id_{\Omega}^2)=h_{\mu}(id_{\Omega})$, qui entraîne que $h_{\mu}(id_{\Omega})=0$. Puis la même formule donne $|\ell|h_{\mu}(T)=h_{\mu}(T^{\ell})=h_{\mu}(id_{\Omega})=0$. On peut aussi remarquer que pour toute partition $\alpha$, $\alpha_{1}^{n\ell}=\alpha_{1}^{\ell}$, donc $H(\Xi_{\alpha})=\lim_{n\to\infty}\frac{1}{n\ell}H(\alpha_{1}^{\ell})=0$. \end{sol} \end{document} \begin{exercice}{} \begin{exoliste} \item \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item \end{exoliste} \end{sol}