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