\documentclass[12pt,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[pdftex]{graphicx} \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} \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} \vskip.5cm {\Large \bf Feuille d'auto-test, mai 2012} \end{center} \vskip 1cm \nosol %\begin{exercice}{Foire aux questions} Cette liste de questions est destinée à vous aider dans vos révisions. Si vous hésitez, n'hésitez pas à écrire à \texttt{pierre.pansu@u-psud.fr}. \vskip1cm \begin{exoliste} \item Soit $E$ un ensemble fini. L'entropie est-elle une fonction concave, convexe, sur l'ensemble des distributions de probabilité sur $E$ ? \item Soient $E_X$ et $E_Y$ des ensembles finis. On peut voir l'information mutuelle $I(X;Y)$ comme une fonction sur l'ensemble des distributions de probabilité sur $E_X\times E_Y$. Est elle concave ? convexe ? \item Soit $C:E\to\{0,1\}^*$ une application injective. On voit $C$ comme un codage. La longueur moyenne de $C$ lorsque la source est une variable aléatoire $X$ est-elle toujours $\geq H(X)$ ? \item Une marche aléatoire sur un graphe fini possède-t'elle toujours une distribution stationnaire ? \item On fait des tirages répétés d'une variables aléatoire à valeurs dans un ensemble fini. Les suites typiques sont elles les suites dont la probabilité de sortie est la plus forte ? \item On se donne un couple de variables aléatoires non indépendantes à valeurs dans des ensembles finis. On fait des tirages répétés et indépendants de l'une de ces variables, puis, indépendamment, de l'autre. Les suites de couples obtenues sont elles fréquemment conjointement typiques ? \item On considère un canal sans mémoire. On consitue un nouveau canal en en utilisant $n$ copies en parallèle (l'alphabet d'entrée devient $E_X^n$, celui de sortie $E_Y^n$). La capacité peut-elle être multipliée par plus de $n$ ? \item Si deux variables aléatoires $X$ et $Y$ prennent la même valeur avec forte probabilité, alors l'entropie conditionnelle $H(X|Y)$ est faible. Quel énoncé du cours précise cette idée ? \item Soient $\alpha$, $\alpha'$ et $\beta$ des partitions finies d'un espace probabilisé, avec $\alpha'$ plus fine que $\alpha$. Alors $H(\alpha|\beta)\leq H(\alpha'|\beta)$. Prouvez le. Quel est l'énoncé équivalent pour des variables aléatoires ? \item Soit $T$ la rotation d'un tiers de tour sur le cercle. $T$ et $T\circ T$ sont elles conjuguées ? \end{exoliste} %\end{exercice} \begin{sol} \begin{exoliste} \item Elle est concave. C'est le corollaire 38 du cours. \item Ni l'un ni l'autre. Fixons une distribution de probabilité $p_X$ sur $E_X$. Considérons le sous-espace affine $F$ de l'espace des distributions de probabilité sur $E_X \times E_Y$ constitué par les distributions de marginale $p_X$. Sur ce sous-espace, l'application $p_{X,Y}\mapsto p_X \otimes p_Y$ est affine, donc $I(X;Y)=D(p_{X,Y}||p_X \otimes p_Y)$ est convexe, car l'entropie relative $D$ est fonction convexe de ses deux arguments. En revanche, lorsque $E_X=E_Y$, sur le sous-espace affine $G$ constitué des distributions concentrées sur la diagonale, représentant les couples $(X,Y)$ de variables aléatoires tels que $Y=X$, $I(X;Y)=I(X;X)=H(X)$ est fonction concave de $p_X$ et donc de $p_{X,Y}$. \item NON. Voir à l'exercice 2 de la feuille 2 un contre-exemple sur un ensemble à 3 éléments et des mots-codes de longueurs 1 et 2. La bonne hypothèse (théorème de codage de source) est "$C$ uniquement décodable". \item OUI. Voir l'exercice 1 de la feuille 3. \item NON. Ce sont les suites dont la probabilité de sortie est la plus fréquemment observée. \item NON. La probabilité d'obtenir par ce procédé une suite conjointement typique est de l'ordre de $2^{-nI(X,Y)}$, elle décroît exponentiellement car, comme $X$ et $Y$ ne sont pas indépendantes, $I(X,Y)>0$. \item NON. Cela résulte du lemme 88 du cours, inégalité $I(X_1^n ;Y_1^n)\leq n\kappa$. \item C'est la signification de l'inégalité de Fano. \item C'est énoncé dans le Lemme 95. En voici une preuve, basée sur la formule d'addition pour l'entropie conditionnelle \begin{eqnarray*} H(\alpha\vee\gamma|\beta)=H(\alpha|\beta)+H(\gamma|\alpha\vee\beta). \end{eqnarray*} Comme $\alpha\leq\alpha'\vee\beta$, $H(\alpha|\alpha'\vee\beta)=0$, donc \begin{eqnarray*} H(\alpha|\beta)&=&H(\alpha\vee\alpha'|\beta)-H(\alpha'|\alpha\vee\beta)\\ &\leq&H(\alpha\vee\alpha'|\beta)\\ &=&H(\alpha'|\beta)+H(\alpha|\alpha'\vee\beta)\\ &=&H(\alpha'|\beta). \end{eqnarray*} L'énoncé équivalent pour trois variables aléatoires à valeurs dans des ensembles finis est le suivant : si $Z$ est fonction de $X$, i.e? s'il existe une application $f:E_X \to E_Z$ telle que $Z=f(X)$ presque sûrement, alors $H(Z|Y)\leq H(X|Y)$. \item OUI. L'application $x\mapsto -x$ induit une bijection de $\R/\Z$ préservant la mesure qui conjugue $T$ et $T^2 =T^{-1}$. \end{exoliste} \end{sol} \vfill\eject \textbf{Retour sur le siège d'Alesia} Dans le modèle étudié par Fabien (César renvoie chaque pigeon capturé porteur d'une lettre tirée au hasard parmi les 255 autres que la lettre apportée par le pigeon), la capacité est inférieure à celle du modèle de l'exercice (elle s'annule même en $\alpha=1-\frac{1}{2^8}$), sauf pour $\alpha$ très proche de $1$, voir figure 1, agrandissement au voisinage de $1$. Pour le modèle étudié par Théo (César renvoie chaque pigeon capturé porteur de la lettre E), je ne sais pas faire autrement qu'en appliquant la formule obtenue dans le Devoir 2. On trouve \begin{eqnarray*} \kappa=\log_2 (1+(2^{8}-1)2^{-\frac{h(\alpha)}{1-\alpha}}). \end{eqnarray*} La figure 2 montre les courbes obtenues en remplaçant $2^8$ par $2^4$ (sinon, on ne voit rien). \begin{center} \vskip-2.5cm \includegraphics[width=3.5in]{alesia(1).pdf} \vskip-3.4cm Figure 1 \end{center} \begin{center} \vskip-3cm \includegraphics[width=3.5in]{alesia(4).pdf} \vskip-3.4cm Figure 2 \end{center} \end{document}