\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{\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 1cm \begin{center} {\large \bf Module D4MA1C20, Compléments magistère} {\Large \bf Feuille de TD n$^0$3} \end{center} \vskip 1cm \nosol \begin{exercice}{Distribution stationnaire d'une marche au hasard} Pour la marche aléatoire sur le graphe pondéré $G=(E,w)$, vérifier que la distribution de probabilité suivante \begin{eqnarray*} \mu(x)=\frac{\sum_{z\not=x}w(x,z)}{\sum_{z\in E}\sum_{z'\not=z}w(z,z')}, \end{eqnarray*} est stationnaire. \end{exercice} \begin{sol} Si $X_0$ suit la loi $\mu$, alors $\PP(X_1 =y)$ vaut \begin{eqnarray*} \sum_{x\in E}P_{xy}\mu(x) &=&\sum_{x\not=y}\frac{w(x,y)}{\sum_{z\not=x}w(x,z)}\frac{\sum_{z\not=x}w(x,z)}{\sum_{z\in E}\sum_{z'\not=z}w(z,z')}\\ &=&\frac{\sum_{x\not=y}w(x,y)}{\sum_{z\in E}\sum_{z'\not=z}w(z,z')}\\ &=&\mu(y), \end{eqnarray*} donc $X_1$ suit aussi la loi $\mu$. \end{sol} \begin{exercice}{Distribution stationnaire uniforme} \begin{exoliste} \item Montrer qu'une chaîne de Markov possède une distribution stationnaire uniforme si et seulement si sa matrice de probabilités de transition $P$ est {\em doublement stochastique}, i.e. non seulement les sommes par lignes valent $1$, mais les sommes par colonnes valent aussi $1$. \item On considère la marche au hasard sur un graphe pondéré. Donner une condition suffisante pour que la distribution uniforme soit stationnaire. Est-elle nécessaire ? \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item Soit $u$ la distribution uniforme, i.e. le vecteur ligne dont les composantes valent $\frac{1}{|E|}$. Alors $(uP)_i =\frac{1}{|E|}\sum_{j}P_{ij}$. Par conséquent, $uP=u$ si et seulement si pour tout $i$, $\sum_{j}P_{ij}=1$, i.e. $P$ est doublement stochastique. \item Soit $G=(E,w)$ un graphe pondéré. Pour $x\in E$, on note $W(x)=\sum_{z\not=x}w(x,z)$. Si la fonction $W$ est constante, alors, d'après l'exercice précédent, la distribution uniforme est stationnaire. Réciproquement, supposons que la distribution uniforme est stationnaire. S'il n'y a qu'une distribution stationnaire (cas irréductible et apériodique), la distribution de l'exercice précédent est uniforme, donc $W$ est constante. Dans ce cas, la condition $W$ constante est nécessaire et suffisante. Elle n'est pas nécessaire en général. Dans le cas non irréductible, le graphe n'est pas connexe, on peut le voir comme la réunion de deux graphes qui se comportent de façons indépendantes. $W$ constante sur chacun des deux graphes est une condition suffisante pour que la distribution uniforme soit stationnaire dans ce cas. \end{exoliste} \end{sol} \begin{exercice}{Chaînes de Markov à entropie décroissante} Soit $X_0 ,X_1 ,\ldots$ une chaîne de Markov dont la distribution stationnaire n'est pas uniforme. Montrer que si $X_0$ est uniforme, alors la suite $H(X_n)$ n'est pas décroissante. \end{exercice} \begin{sol} Si $X_0$ suit la loi uniforme, alors $H(X_0)=\frac{1}{|E|}$. Si la distribution stationnaire $\mu$ n'est pas uniforme, alors $H(\mu)<\frac{1}{|E|}$. Or, quand $n$ tend vers $+\infty$, $X_n$ converge en loi vers $\mu$, donc $H(X_n)$ tend vers $H(\mu)$. La suite $H(X_n)$ ne peut pas être croissante. \end{sol} \begin{exercice}{Convergence de l'entropie relative} Soit $X_0 ,X_1 ,\ldots$ une chaîne de Markov. Soit $\mu$ une distribution stationnaire. Montrer que $D(p_{X_n}||\mu)$ converge. La limite est-elle $0$ ? \end{exercice} \begin{sol} Le théorème de décroissance de l'entropie relative s'applique aux suites $\mu_n =\mu$ et $\mu'_n =p_{X_n}$. La suite $D(p_{X_n}||\mu)$, décroissante et positive, converge. S'il existe au moins deux distributions stationnaires $\mu\not=\mu'$, soit $X_n$ la chaîne telle que $p_{X_0}=\mu'$. Alors $D(p_{X_n}||\mu)=D(\mu'||\mu)$ est constante non nulle, donc la limite n'est pas nulle. Dans le cas irréductible et apériodique, il existe une unique distribution stationnaire $\mu$, son support est tout l'ensemble $E$ (donc $p\mapsto D(p||\mu)$ est continue en $\mu$), $p_{X_n}$ converge vers $\mu$, donc la limite est nulle. \end{sol} \begin{exercice}{Croissance de l'entropie conditionnelle} Soit $X_0 ,X_1 ,\ldots$ une chaîne de Markov stationnaire. \begin{exoliste} \item Montrer que pour tout $n$, $H(X_{n+1}|X_1)=H(X_{n}|X_0)$. \item En utilisant le fait que le conditionnement diminue l'entropie, montrer que l'entropie conditionnelle $H(X_n |X_0)$ augmente. \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item $H(X_{n}|X_0)$ dépend seulement de la loi de $X_0$ et des lois conditionnelles $p_{X_n |X_0 =x_0}$ de $X_n$ sachant $X_0 =x_0$, qui s'expriment en fonction de la loi jointe de $(X_0 ,\ldots,X_n)$. Comme $(X_1 ,\ldots,X_{n+1})$ a même loi, $H(X_{n+1}|X_1)=H(X_{n}|X_0)$. \item Pour comparer $H(X_{n+1}|X_1)$ à $H(X_{n+1}|X_0)$ on utilise la décroissance de l'entropie par conditionnement : $H(X_{n+1}|X_1)\geq H(X_{n+1}|X_1 ,X_0)$, puis la propriété de Markov : pour tout état $x_0$, la loi conditionnelle de $X_{n+1}$ sachant que $X_{1}=x_0$ et $X_1=x_1$ coïncide avec la loi conditionnelle de $X_{n+1}$ sachant que $X_1=x_1$, donc $H(X_{n+1}|X_1 =x_1,\,X_0 =x_0)=H(X_{n+1}|X_1 =x_1)$, et en prenant la moyenne sur $(x_0 ,x_1)$, $H(X_{n+1}|X_1 ,X_0)=H(X_{n+1}|X_1)$. On conclut que $H(X_{n+1}|X_0)\geq H(X_{n+1}|X_1)$ et, avec la question 1, que $H(X_{n+1}|X_0)\geq H(X_{n}|X_0)$. \end{exoliste} \end{sol} \begin{exercice}{Distribution de Boltzmann-Gibbs} Un système physique isolé est décrit par une distribution de probabilité $p$ sur un ensemble fini $E$. L'énergie (microscopique) $e(x)$ d'une molécule ne dépend que de l'état $x\in E$ qu'elle occupe. Elle est positive. L'énergie totale du système est $\mathcal{E}(p)=\E_{p}(e)=\sum_{x\in E}p(x)e(x)$. \begin{exoliste} \item Montrer qu'il existe une distribution $q$ qui maximise l'entropie $H$ à énergie totale fixée. \item Montrer que $q$ est unique. \item Montrer que pour tout $x\in E$, $q(x)>0$. \item En appliquant le théorème des extrema liés, déterminer $q$. Montrer que le multiplicateur de Lagrange est uniquement déterminé par la valeur de l'énergie totale souhaitée. \item En utilisant la positivité de l'entropie relative, redémontrer le fait que pour toute distribution de probabilité $p$ d'énergie $\mathcal{E}$, $H(p)\leq H(q)$. \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item L'inconnue est le vecteur $p\in\R^E$. Il est astreint à se déplacer dans le polyèdre convexe $\mathcal{P}$ défini par les inégalités $p(x)\geq 0$ et les deux équations $\sum_{x}p(x)=1$, $\sum_{x}p(x)e(x)=\mathcal{E}$. La fonction à maximiser est l'entropie $H(p)$, elle est continue, donc son maximum est atteint en un point $q\in\mathcal{P}$. \item Elle est strictement concave, donc $q$ est unique (sinon, $H$ serait constante le long d'un segment). \item Soit $S\subset E$ le support de $q$. On calcule les dérivées partielles de $H$. Pour $x\in S$, \begin{eqnarray*} \frac{\partial H}{\partial p_x}(q)=-\log_2 q(x)-1. \end{eqnarray*} Pour $x\notin S$, la dérivée partielle $\frac{\partial H}{\partial p_x}(p)$ tend vers $+\infty$ lorsque $p$ tend vers $q$ avec $p(x)>0$, donc $H(p)>H(q)$, contradiction. On en déduit que $S=E$. \item Si la fonction $e:E\to\R$ est constante, alors $q$ est uniforme. Sinon, les deux équations définissant $\mathcal{P}$ sont linéairement indépendantes. D'après le théorème des extrema liés, il existe $\alpha$, $\beta\in\R$ tels que, pour tout $x\in S$, \begin{eqnarray*} -\log_2 q(x)-1=\lambda+\beta e(x),\quad \emph{i.e.}\quad q(x)=2^{-(1+\lambda)}2^{-\beta e(x)}. \end{eqnarray*} Avec la condition $\sum_{x}q(x)=1$, il vient \begin{eqnarray*} q(x)=\frac{2^{-\beta e(x)}}{Q}\quad \textrm{où}\quad Q=\sum_{z\in E}2^{-\beta e(z)}. \end{eqnarray*} La constante $\beta$ est déterminée par l'énergie totale $\mathcal{E}$. En effet, à $\mathcal{E}$ fixé, on sait qu'il y a une unique solution $q$. On peut le voir différemment. L'énergie $\E_q (e)$ est une fonction dérivable de $\beta$, comprise entre $m=\min_{x\in E}e(x)$ et $M=\max_{x\in E}e(x)$, et qui tend vers $m$ (resp. vers $M$) lorsque $\beta$ tend vers $+\infty$ (resp. vers $-\infty$). On calcule les dérivées à un facteur $\ell n(2)$ près, \begin{eqnarray*} \frac{\partial Q}{\partial\beta}=-\sum_{x\in E}e(x)2^{-\beta e(x)},\quad \frac{1}{Q}\frac{\partial Q}{\partial\beta}=-\E_q(e),\quad Q\frac{\partial \frac{1}{Q}}{\partial\beta}=\E_q(e), \end{eqnarray*} puis \begin{eqnarray*} \frac{\partial \E_q(e)}{\partial\beta}=\sum_{x\in E}-e(x)\frac{2^{-\beta e(x)}}{Q}e(x)+\frac{1}{Q}\E_q(e)2^{-\beta e(x)}e(x)=-\E_q(e^2)+\E_q(e)^2=-Var_q(e)<0, \end{eqnarray*} car $e$ n'est pas constante. Donc $\beta\mapsto\E_q (e)$ est strictement décroissante, elle prend exactement une fois toutes valeurs dans l'intervalle $]m,M[$. \item Soit $p$ une distribution de probabilité de même énergie totale $\mathcal{E}$ que $q$. Alors \begin{eqnarray*} 0&\leq& D(p||q)\\ &=&\sum_{x\in E}p(x)\log_2\frac{p(x)Q}{2^{-\beta e(x)}}\\ &=&\log_2 Q -H(p)+\beta\sum_{x\in E}p(x)e(x)\\ &=&\log_2 Q -H(p)+\beta\mathcal{E}, \end{eqnarray*} avec égalité lorsque $p=q$, donc $H(p)\leq H(q)$. La distribution qui maximise l'entropie à énergie fixée (ou, plus généralement, qui maximise la différence entropie moins énergie), est sensée correspondre à l'équilibre thermodynamique. \end{exoliste} \end{sol} \begin{exercice}{Entropie par pas pour une marche aléatoire sur un graphe fini} Soit $G=(E,w)$ un graphe pondéré fini. On pose, pour $x\in E$, $W(x)=\sum_{y\not=x}w(x,y)$ et $W=\sum_{x\in E}W(x)$. On introduit deux distributions de probabilité, $p(x,y)=\frac{w(x,y)}{W}$ sur $E\times E$ et $\mu(x)=\frac{W(x)}{W}$ sur $E$. \begin{exoliste} \item Soit $\Xi$ une marche aléatoire sur $G$. On suppose qu'elle est irréductible et apériodique. Montrer que $H(\Xi)=H(p)-H(\mu)$. \item Que vaut l'entropie par pas pour la marche aléatoire d'un roi (resp. d'une tour, d'un fou, d'une reine) sur un échiquier $3\time 3$ ? \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item On se rappelle que $P_{xy}=\frac{w(x,y)}{W(x)}$. D'après l'exercice 1 de la feuille 3, $\mu$ est la mesure stationnaire. Sous les hypothèses d'irréductibilité et d'apériodicité, la loi de $X_n$ converge vers $\mu$, donc \begin{eqnarray*} H(\Xi)&=&-\sum_{x,\,y\in E}\mu(x)P_{xy}\log_2 P_{xy}\\ &=&-\sum_{x,\,y\in E}\mu(x)\frac{w(x,y)}{W(x)}\log_2 \frac{w(x,y)}{W(x)}\\ &=&-\sum_{x,\,y\in E}\frac{w(x,y)}{W}\log_2 \frac{p(x,y)}{\mu(x)}\\ &=&-\sum_{x,\,y\in E}p(x,y)\log_2 p(x,y)+\sum_{x,\,y\in E}\frac{w(x,y)}{W}\log_2 \mu(x)\\ &=&H(p)-H(\mu). \end{eqnarray*} \item Dans tous les cas, les poids $w(x,y)$ valent $1$ (ou $0$). Par conséquent $H(p)=\log_2 (W)$ et $H(\Xi)=\frac{1}{W}\sum_{i}n_i w_i \log_2(w_i)$ où $n_i$ est le nombre de sommets $x$ où $W(x)=w_i$. Cas du roi. Il y a 4 positions où $W(x)=3$, 4 où $W(x)=5$ et une ou $W(x)=8$. $W=40$, d'où $H(\Xi)=\frac{1}{40}(4.3.\log_2(3)+4.5.\log_2(5)+8.\log_2 (8))=2.2364$. Cas de la tour. Partout, $W(x)=4$, $W=36$, d'où $H(\Xi)=-\frac{1}{36}9.4.\log_2 (4)=2$. Cas du fou. Il y a 8 positions où $W(x)=2$ et une où $W(x)=4$, $W=20$, d'où $H(\Xi)=\frac{1}{20}(8.2.\log_2 (2)+1.4.\log_2 (4))=\frac{6}{5}=1.2$. Cas de la dame. Il y a 8 positions où $W(x)=6$ et une où $W(x)=8$, $W=56$, d'où $H(\Xi)=\frac{1}{56}(8.6.\log_2 (6)+1.8.\log_2 (8))=\frac{3}{7}(2\log_2 (6)+1)=2.3936$. Clairement, l'entropie par pas mesure la liberté de mouvement. \end{exoliste} \end{sol} \end{document} \begin{exercice}{} \begin{exoliste} \item \end{exoliste} \end{exercice} \begin{sol} \begin{exoliste} \item \end{exoliste} \end{sol}