\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 1cm

\begin{center}
{\large \bf Module D4MA1C20, Compléments magistère}

{\Large \bf Feuille de TD n$^0$4}

\end{center}

\vskip 1cm

\nosol


\begin{exercice}{Suites typiques}

On joue à pile ou face avec une pièce truquée, qui tombe sur pile 9 fois sur 10. 

\begin{exoliste}

\item Quelle est la suite $\in\{P,F\}^n$ qui a le plus de chances de sortir ? Est-elle typique ?

\item Quelles sont les $2^{n-1}$ suites $\in\{P,F\}^n$ qui ont le plus de chances de sortir ? Les suites typiques en font-elles partie ?

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item La probabilité de sortie d'une suite $(x_1 ,\ldots,x_n)$ est $(\frac{9}{10})^{N_P (x_1^n)} (\frac{1}{10})^{N_F (x_1^n)}$, où $N_P$ (resp. $N_F$) est le nombre de pile (resp. face) dans la suite. Cette probabilité est maximale pour la suite qui ne comprend que des pile. Cette suite n'est pas typique, sa probabilité de sortie est nettement supérieure à $((\frac{9}{10})^{\frac{9}{10}} (\frac{1}{10})^{\frac{1}{10}})^{n}$.

\item Dans l'ordre de probabilité de sortie décroissante, on trouve ensuite les suites avec 1 face, avec 2 face, etc... Pour avoir la moitié de l'effectif total, il faut aller jusqu'à $n/2$ face. Les suites typiques, qui ont environ 10\% de face, en font partie. Les suites typiques représentent bien moins de la moitié de l'effectif, mais totalisent presque toute la probabilité.

\end{exoliste}
\end{sol}


\begin{exercice}{Ergodicité des rotations irrationnelles}

Soit $\omega\in\R\setminus\Q$. On appelle rotation d'angle $\theta$ (il serait plus approprié d'appeler $2\pi\theta$ l'angle) l'application $T:\R/\Z\to\R/\Z$ définie par $T(x)=x+\theta$ mod $1$. On va montrer que $T$ est ergodique pour la mesure de Lebesgue $\lambda$ sur $\R/\Z$.

\begin{exoliste}

\item Montrer que les nombres $x+n\theta$ sont deux à deux distincts dans $\R/\Z$. 

\item Montrer qu'il existe une suite $m_k$ d'entiers telle que $m_k \theta$ tend vers $0$ modulo $1$.

\item Montrer que les orbites sont denses, i.e. que pour tout $x\in\R/\Z$, $\{x+n\theta\,;\,n\in\Z\}$ est dense dans $\R/\Z$.

\item Montrer que, pour tout $\delta>0$ et pour tout $x\in\R/\Z$, on peut trouver des entiers $n_1 ,\ldots,n_p$ tels que les intervalles $I_j =]x +n_j \theta-\delta,x +n_j \theta+\delta[$ recouvrent $\R/\Z$, chaque $I_j$ ne rencontre que $I_{j-1}$ et $I_{j+1}$, et $p\delta \leq 1$.

\item Soit $A\subset\R/\Z$ un ensemble mesurable, invariant par $T$, de mesure de Lebesgue $>0$. On admet que $A$ possède un \emph{point de densité} $x_0$, i.e. tel que pour tout $\epsilon>0$, il existe $\delta>0$ tel que
\begin{eqnarray*}
\frac{\lambda(A\cap]x_0 -\delta,x_0 +\delta[)}{\lambda(]x_0 -\delta,x_0 +\delta[)}>1-\epsilon.
\end{eqnarray*}  
Vérifier que pour tout $n\in \Z$, $\frac{\lambda(A\cap]x_0 +n\theta-\delta,x_0 +n\theta+\delta[)}{2\delta}>1-\epsilon$.

\item En utilisant séparément les intervalles $I_j$, $j$ pair ou impair, montrer que $\lambda(A)>1-2\epsilon$. Conclure.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Pour $n\not=m$, l'égalité $x+n\theta=x+m\theta$ mod $1$ entraîne que $(n-m)\theta$ est un entier. Comme $\theta$ est irrationnel, cela entraîne que $n=m$. Les nombres $x+n\theta$ sont donc deux à deux distincts dans $\R/\Z$. 

\item Par compacité, il existe une suite $n_k$ d'entiers telle que la suite $x+n_k \theta$ mod $1$ soit convergente. En particulier, la suite $(n_{k+1}-n_k)\theta$ mod $1$ tend vers $0$. On peut donc prendre $m_k =n_{k+1}-n_k$.

\item Etant donné $\epsilon>0$, soit $k$ tel que $|m_k \theta|<\epsilon$. Les multiples de $m_k \theta$ découpent $\R/\Z$ en intervalles de longueur $<\epsilon$. Tout point de $\R/\Z$ est donc à distance $<\epsilon$ d'un point de la forme $x+n\theta$.

\item Soit $\epsilon>0$ petit. Soit $p=1+\lfloor\frac{1+2\epsilon}{2\delta}\rfloor$ le plus petit entier $>\frac{1+2\epsilon}{2\delta}$. Par densité, on peut choisir $n_j$ tel que $|x+n_j \theta-\frac{j}{p}|<\frac{\epsilon}{p}$. Alors les intervalles $I_j =]x+n_j \theta-\delta,x+n_j \theta+\delta[$ recouvrent $\R/\Z$. En effet, la distance $|x+n_{j+1}\theta-(x+n_j \theta)|<\frac{1}{p}+2\frac{\epsilon}{2p}<2\delta$, donc $[x+n_j \theta,x+n_{j+1}\theta]\subset I_{j}\cup I_{j+1}$. Inversement, les $I_j$ se recouvrent peu : comme $|x+n_{j+1}\theta-(x+n_{j-1} \theta)|\geq \frac{2}{p}-2\frac{\epsilon}{p}\geq 4\delta\frac{1-\epsilon}{1+4\delta+2\epsilon}>2\delta$, $I_{j-1}\cap I_{j+1}=\emptyset$. Enfin, $p\delta\leq \delta(1+\frac{1+2\epsilon}{2\delta})\leq \frac{1}{2}+\delta+\epsilon<1$ pour $\delta$, $\epsilon$ petits.

\item Par invariance de $A$ et de la mesure de Lebesgue,
\begin{eqnarray*}
\frac{\lambda(A\cap]x_0 +n\theta-\delta,x_0 +n\theta+\delta[)}{2\delta}
=\frac{\lambda(T^{-n}(A)\cap]x_0 -\delta,x_0 +\delta[)}{2\delta}
=\frac{\lambda(A\cap]x_0 -\delta,x_0 +\delta[)}{2\delta}>1-\epsilon.
\end{eqnarray*}

\item On utilise les intervalles $I_j$ de la question 4. Soit $B$ (resp. $C$) la réunion des $I_j$ avec $j$ pair (resp. impair). Il s'agit de réunions disjointes. Par conséquent,
\begin{eqnarray*}
\lambda(A\cap B)\geq 2\delta|B|(1-\epsilon),\quad\lambda(A\cap C)\geq 2\delta|B|(1-\epsilon).
\end{eqnarray*}
D'autre part,
\begin{eqnarray*}
\lambda(B\cap C)=\lambda(B)+\lambda(C)-\lambda(B\cup C)=2p\delta-1.
\end{eqnarray*}
Il vient
\begin{eqnarray*}
\lambda(A)&=&\lambda((A\cap B)\cup(A\cap C))\\
&=&\lambda(A\cap B)+\lambda(A\cap C)-\lambda(A\cap B\cap C)\\
&\geq&2p\delta(1-\epsilon)-\lambda(B\cap C)\\
&=&1-2p\delta\epsilon\geq 1-2\epsilon.
\end{eqnarray*}
C'est vrai pour tout $\epsilon>0$, donc $\lambda(A)=1$. Cela prouve que $T$ est ergodique pour la mesure de Lebesgue.
\end{exoliste}
\end{sol}

\begin{exercice}{Puissances de $2$}

On s'intéresse au premier chiffre (en base 10) des puissances de $2$. Voici les 46 premiers : 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3. Pourtant, cette suite n'est pas périodique. D'ailleurs, voici l'histogramme obtenu sur les 1000 premiers termes de la suite.
\begin{center}
\begin{tabular}{|c|ccccccccc|}
\hline
$k$ & 1   &  2  &   3   &  4   &  5   &  6  &   7  &   8  &   9\\
\hline
effectif & 301 &  176  & 125  &  97  &  79  &  69  &  56  & 52  &  45\\
\hline
\end{tabular}
\end{center}
\begin{exoliste}

\item Relier ce problème à celui de la répartition modulo $1$ des multiples de $\log_{10}(2)=0.3010299956639811$.

\item Montrer que $\log_{10}(2)$ est irrationnel.

\item En appliquant le théorème ergodique de Birkhoff, montrer que l'histogramme des premiers chiffres des $n$ premières puissances de $2$ converge, quand $n$ tend vers l'infini, vers une distribution de probabilité sur $\{1,\ldots,9\}$, appelée {\em loi de Benford}.

\item Donner une explication intuitive au fait que, au vu des 46 premiers chiffres, on a l'impression que la suite est périodique.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Le premier chiffre de $2^n$ est $k\in\{1,\ldots,9\}$ si et seulement si
\begin{eqnarray*}
\exists m\in\N~k.10^{m}\leq 2^n <(k+1).10^{m}
&\Leftrightarrow& \exists m~\log_{10}(k)+m\leq n\log_{10}(2)<\log_{10}(k+1)+m\\
&\Leftrightarrow& n\log_{10}(2)\textrm{ mod }1 \in[\log_{10}(k),\log_{10}(k+1)[.
\end{eqnarray*}

\item Par l'absurde. Si $\log_{10}(2)=\frac{p}{q}$ était rationnel, $2^q$ serait égal à $10^p$, ce qui est impossible, car $10^p$ est divisible par $5$ alors que $2^q$ ne l'est pas. On conclut que $\log_{10}(2)$ est irrationnel.

\item Comme la transformation $T(x)=x+\log_{10}(2)$ mod $1$ préserve la mesure de Lebesgue et est ergodique, le théorème ergodique de Birkhoff appliqué à la fonction caractéristique de l'intervalle $[\log_{10}(k),\log_{10}(k+1)[$ implique que pour presque tout $x\in\R/\Z$, le nombre moyen de $n$ tels que $x+n\log_{10}(2)\textrm{ mod }1 \in[\log_{10}(k),\log_{10}(k+1)[$ converge vers
\begin{eqnarray*}
\E(1_{[\log_{10}(k),\log_{10}(k+1)[})=\log_{10}(k+1)-\log_{10}(k).
\end{eqnarray*}
De plus, pour tout $\epsilon>0$, le nombre moyen de $n$ tels que $x+n\log_{10}(2)\textrm{ mod }1$ est à distance $<\epsilon/20$ de l'un des points $\log_{10}(k)$ tend vers $\frac{18}{20}\epsilon$. En prenant $x$ dans l'intervalle $]-\frac{\epsilon}{20},\frac{\epsilon}{20}[$, on trouve que l'histogramme coïncide avec la loi de Benford à $\epsilon$ près pour $n$ assez grand. Il y a donc convergence des histogrammes.

\item Comme $\log_{10}(2)$ est très proche du rationnel $\frac{3}{10}$, le début de la suite coïncide avec celle obtenue en remplaçant $\log_{10}(2)$ par $\frac{3}{10}$, qui est périodique de période $10$. $\log_{10}(2)-0.3\sim 0.001$ donc, pour $n< 150$, $n(\log_{10}(2)-0.3)< 0.15$, ce qui fait que les deux suites tombent dans les mêmes cases de l'histogramme avec seulement deux exceptions, $n=47$ et $n=79$.

\end{exoliste}
\end{sol}


\begin{exercice}{L'urne d'Ehrenfest}

C'est un exemple de chaîne de Markov imaginé par le physicien austro-néerlandais Paul Ehrenfest et la mathématicienne russe Tatiana Afanasyeva-Ehrenfest, pour illustrer le second principe de la thermodynamique, et éclairer le paradoxe apparent soulevé par le Théorème de récurrence de Poincaré.

On considère une boîte fermée séparée par une cloison percée en deux compartiments. Au départ, 100 boules numérotées se trouvent dans le compartiment de gauche, aucune à droite. A chaque seconde, un chiffre entre 1 et 100 est tiré uniformément au hasard, et la boule correspondante est transférée du compartiment où elle se trouvait dans l'autre.

\begin{exoliste}

\item Montrer que le processus $\Upsilon=(Y_n)_{n\in\N}$ décrit est une chaîne de Markov défini sur un ensemble $E_Y$ à $2^{100}$ éléments. 

\item Est-ce une marche au hasard sur un graphe pondéré ? Trouver une distribution stationnaire. Est elle unique ?

\item On s'intéresse au processus $\Xi=(X_n)_{n\in\N}$, où $X_n$ est le nombre de boules situés dans le compartiment de gauche. Montrer que c'est à nouveau une chaîne de Markov. Ecrire la matrice des probabilités de transition. La chaîne est-elle une marche au hasard ?

\item Déterminer la distribution stationnaire. 

\item Quelle est l'entropie par seconde du processus $\Xi$ ?

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Soit $B$ l'ensemble des boules. La configuration de l'urne au temps $n$ est décrite par la fonction $Y_n :B\to\{0,1\}$ qui indique quelles boules sont dans le compartiment de gauche ($Y_n (i)=0$) et lesquelles sont dans le compartiment de droite ($Y_n (i)=1$). $Y_n$ est donc à valeurs dans $E_Y=\{0,1\}^{B}$. Au départ, $Y_0$ est la fonction nulle. Clairement, connaissant les configurations $Y_0 =y_0 ,\ldots,Y_n =y_n$, la probabilité que $Y_{n+1}=y_{n+1}$ est $0$ à moins que $y_{n+1}$ ne diffère de $y_n$ en exactement une boule $i\in B$, et dans ce cas, elle vaut $\frac{1}{100}$, car les numéros des boules à déplacer sont tirés uniformément. Autrement dit, cette probabilité ne dépend que de $y_n$, donc il s'agit d'une chaîne de Markov. 

\item Il s'agit bien de la marche au hasard sur le graphe appelé hypercube. Les poids des arêtes sont $\frac{1}{100}$ (pour les arêtes qui relient deux fonctions différant en exactement une boule) et $0$ sinon. Par symétrie (le graphe pondéré est invariant par toute permutation des boules), la distribution uniforme est stationnaire. Comme le graphe est connexe, la chaîne est irréductible. Elle n'est pas apériodique, car les longueurs des chemins revenant à leur point de départ sont toutes paires. Néanmoins, seule la distribution uniforme est invariante. En effet, la marche $Y_0 ,Y_2 ,Y_4,...$ vit sur deux sous-graphes disjoints $G_0$ et $G_1$, distingués par la parité du nombre de boules dans le compartiment de gauche. Sur chacun de ces sous-graphes, elle est irréductible et apériodique, donc possède une unique distribution invariante, uniforme. Une distribution stationnaire $\mu$ sur $G$ est donc constante sur $G_0$ et constante sur $G_1$. Soient $a_0 =\mu(G_0)$ et $a_1 =\mu(G_1)$. De même pour $\mu P$. L'effet de la marche est de moyenner sur les premiers voisins, donc $(\mu P)(G_0)=a_1$, $(\mu P)(G_1)=a_0$. La stationnarité force $a_0 =a_1$, donc seule la distribution uniforme est invariante.

\item Soit $g:E_Y :=\{0,1\}^B \to E_X :=\{0,\ldots,100\}$ l'application qui à une fonction $f\in E_Y$ associe $\sum_{i\in B}f(i)$. Alors $X_n =g(Y_n)$. La probabilité d'une trajectoire $(x_0 ,\ldots,x_{n+1})$ est
\begin{eqnarray*}
&&\PP(X_{n+1} =x_{n+1},X_n =x_n ,\ldots,X_0 =x_0)\\
&=&\sum_{y_{n+1}\in g^{-1}(x_{n+1})}\sum_{y_{n}\in g^{-1}(x_{n})}\cdots\sum_{y_{0}\in g^{-1}(x_{0})}\PP(Y_{n+1} =y_{n+1},Y_n =y_n ,\ldots,Y_0 =y_0)\\
&=&\sum_{y_{n+1}\in g^{-1}(x_{n+1})}\sum_{y_{n}\in g^{-1}(x_{n})}\cdots\sum_{y_{0}\in g^{-1}(x_{0})}\PP(Y_{n+1} =y_{n+1}|Y_n =y_n ,\ldots,Y_0 =y_0)\PP(Y_n =y_n ,\ldots,Y_0 =y_0)\\
&=&\sum_{y_{n+1}\in g^{-1}(x_{n+1})}\sum_{y_{n}\in g^{-1}(x_{n})}\cdots\sum_{y_{0}\in g^{-1}(x_{0})}\PP(Y_{n+1} =y_{n+1}|Y_n =y_n)\PP(Y_n =y_n ,\ldots,Y_0 =y_0)\\
&=&\sum_{y_{n+1}\in g^{-1}(x_{n+1})}\sum_{y_{n}\in g^{-1}(x_{n})}\PP(Y_{n+1} =y_{n+1}|Y_n =y_n)\PP(Y_n =y_n ,X_{n-1}=x_{n-1}\ldots,X_0 =x_0).
\end{eqnarray*}
Cette probabilité est nulle sauf si $|x_{n+1}-x_{n}|=1$. Si $x_{n+1}=x_{n}+1$, il y a, pour tout choix de $y_n \in g^{-1}(n)$, exactement $100-x_n$ choix de $y_{n+1}$ qui donnent une probabilité conditionnelle non nulle, égale à $\frac{1}{100}$, donc dans ce cas,
\begin{eqnarray*}
\sum_{y_{n+1}\in g^{-1}(x_{n+1})}\PP(Y_{n+1} =y_{n+1}|Y_n =y_n)=\frac{100-x_n}{100},
\end{eqnarray*}
et
\begin{eqnarray*}
&&\PP(X_{n+1} =x_{n+1},X_n =x_n ,\ldots,X_0 =x_0)\\
&=&\frac{100-x_n}{100}\sum_{y_{n}\in g^{-1}(x_{n})}\PP(Y_n =y_n ,X_{n-1}=x_{n-1}\ldots,X_0 =x_0)\\
&=&\frac{100-x_n}{100}\PP(X_n =y_n ,X_{n-1}=x_{n-1}\ldots,X_0 =x_0),
\end{eqnarray*}
d'où
\begin{eqnarray*}
\PP(X_{n+1} =x_{n+1}|X_n =x_n ,\ldots,X_0 =x_0)=\frac{100-x_n}{100}.
\end{eqnarray*}
De même, si $x_{n+1}=x_{n}-1$, il y a, pour tout choix de $y_n \in g^{-1}(n)$, exactement $x_n$ choix de $y_{n+1}$ qui donnent une probabilité conditionnelle non nulle, égale à $\frac{1}{100}$, d'où
\begin{eqnarray*}
\PP(X_{n+1} =x_{n+1}|X_n =x_n ,\ldots,X_0 =x_0)=\frac{x_n}{100}.
\end{eqnarray*}
Dans les deux cas, les variables $X_0 ,\ldots,X_{n-1}$ n'ont joué aucun rôle, donc on a affaire à une chaîne de Markov dont la matrice des probabilités de transition a au plus 2 coefficients non nuls par ligne et colonne,
\begin{eqnarray*}
P_{x,x+1}=\frac{100-x}{100},\quad P_{x,x-1}=\frac{x}{100}.
\end{eqnarray*}
Ce n'est pas une marche au hasard, car $P_{x,x+1}\not=P_{x+1,x}$.

\item L'image par $g$ de la distribution uniforme est
\begin{eqnarray*}
p(x)=\sum_{y\in g^{-1}(x)}2^{-100}=\begin{pmatrix}100\\ x\end{pmatrix}2^{-100}.
\end{eqnarray*}
C'est une loi binômiale $\mathcal{B}(\frac{1}{2},100)$. Elle est stationnaire, car, pour tout $x \in E_X$,
\begin{eqnarray*}
\sum_{x_0 \in E_X}p(x_0)\PP(X_1 =x|X_0 =x_0)
&=&p(x -1)P_{x -1,x}+p(x +1)P_{x +1,x}\\
&=&\begin{pmatrix}100\\ x-1\end{pmatrix}2^{-100}\frac{100-x+1}{100}+\begin{pmatrix}100\\ x+1\end{pmatrix}2^{-100}\frac{x+1}{100}\\
&=&\begin{pmatrix}100\\ x\end{pmatrix}2^{-100}.
\end{eqnarray*}
Cela peut aussi se voir de façon probabiliste. $\mathcal{B}(\frac{1}{2},100)$ est la loi de la somme de $100$ variables indépendantes $Z_j$ de loi $\mathcal{B}(\frac{1}{2})$. Effectuer un pas de la chaîne consiste à changer la valeur de l'une de ces variable, tirée au hasard. Cela ne change pas la loi jointe de $(Z_1 ,\ldots,Z_{100})$, donc cela ne change pas la loi de leur somme.

\item D'après une formule du cours, 
\begin{eqnarray*}
H(\Xi)
&=&-\sum_{x,x'}\mu(x)P_{xx'}\log_2 P_{xx'}\\
&=&-\sum_{x=0}^{100}\begin{pmatrix}100\\ x\end{pmatrix}2^{-100}(\frac{100-x}{100}\log_2 \frac{100-x}{100}+\frac{x}{100}\log_2 \frac{x}{100})\\
&=&-2\sum_{x=0}^{100}\begin{pmatrix}100\\ x\end{pmatrix}2^{-100}\frac{x}{100}\log_2 \frac{x}{100}\\
&=&-2\E(\frac{X}{100}\log_2 \frac{X}{100}).
\end{eqnarray*}
Comme la loi binômiale $\mathcal{B}(\frac{1}{2},100)$ est proche de la loi normale $\mathcal{N}(50,5)$, qui est passablement concentrée autour de $50$, $-2\E(\frac{X}{100}\log_2 \frac{X}{100})$ est voisin de $-2\frac{50}{100}\log_2 \frac{50}{100}=1$.
\end{exoliste}
\end{sol}


\end{document}


\begin{exercice}{}
\begin{exoliste}

\item 

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item 

\end{exoliste}
\end{sol}

