\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}
\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{\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$2}

\end{center}

\vskip 1cm

\nosol


\begin{exercice}{Codages uniquement décodables}

Un codage $C:E\to\{0,1\}^*$ est dit {\em non singulier} si c'est une application injective. C'est une condition plus faible que d'être uniquement décodable. Les codages suivants de l'ensemble $E=\{1,2,\ldots,8\}$ sont ils uniquement décodables ? Non singuliers ?

\begin{exoliste}

\item
\begin{tabular}{|l|cccccccc|}
\hline
$x$ & 1&2&3&4&5&6&7&8\\
\hline
$C(x)$   &$0$&$10$&$110$&$1110$&$1001$&$1010$&$1011$&$1100$\\
\hline
\end{tabular}

\item
\begin{tabular}{|l|cccccccc|}
\hline
$x$ & 1&2&3&4&5&6&7&8\\
\hline
$C'(x)$   &$0$&$10$&$110$&$1110$&$111100$&$111110$&$111101$&$111111$\\
\hline
\end{tabular}

\item Soit $X$ une variable aléatoire à valeurs dans $E$, de distribution

\begin{tabular}{|l|cccccccc|}
\hline
$x$ & 1&2&3&4&5&6&7&8\\
\hline
$p(x)$   &$\frac{1}{2}$&$\frac{1}{4}$&$\frac{1}{8}$&$\frac{1}{16}$&$\frac{1}{64}$&$\frac{1}{64}$&$\frac{1}{64}$&$\frac{1}{64}$\\
\hline
\end{tabular}

Calculer son entropie. Calculer les longueurs moyennes des deux codages ci-dessus.
\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item $C$ est non singulier mais n'est pas uniquement décodable. La suite $1100=C(8)=C(3)C(1)$ possède deux décodages.

\item $C'$ est non singulier et uniquement décodable. En effet, aucun mot-code $C(x)$ n'est un préfixe d'un autre mot-code. Voir la suite de l'argument dans la preuve du Théorème du codage de source.

\item $H(X)=2$. $\E(\ell(X))=\frac{15}{8}=1.875$. $\E(\ell'(X))=2$.

\end{exoliste}
\end{sol}

\begin{exercice}{Codage de longueur moyenne inférieure à l'entropie}

L'exercice précédent contient un exemple, sur un ensemble à $8$ éléments, de variable aléatoire $X$ à valeurs dans $E$ et de codage $C:E\to\{0,1\}^*$ non singulier tels que $\E(\ell(X))<H(X)$. Peut on faire plus simple~? Donner un exemple, le plus simple possible.
\end{exercice}

\begin{sol}

Si $E$ a deux éléments, $H(X)\leq 1$, or tout codage utilise des mots de longueurs $\geq 1$, d'où $\E(\ell(X))\geq 1\geq H(X)$. Il faut donc au moins trois éléments.

Soit $E=\{a,b,c\}$ avec distribution de probabilité $p(a)=\frac{1}{2}$, $p(b)=p(c)=\frac{1}{4}$. On code $E$ par $C(a)=0$, $C(b)=1$ et $C(c)=00$. Alors $\E_p (\ell)=\frac{5}{4}$ alors que $H(p)=\frac{3}{2}$.

Evidemment, ce codage n'est pas uniquement décodable. On remarque que $2^{-\ell(a)}+2^{-\ell(b)}+2^{-\ell(c)}=\frac{5}{4}>1$. Néanmoins, il est non singulier.

\end{sol}

\begin{exercice}{Codages non singuliers}

Soit $X$ une variable aléatoire à valeurs dans $E$. On s'intéresse à la borne inférieure $L_{ns}(X)$ des longueurs moyennes $\E(\ell(X))$ des codages non singuliers sur deux lettres.
 
\begin{exoliste}

\item Montrer que, pour tout codage non singulier, $\E(\ell(X))\geq \frac{1}{\log_2 3}H(X)-1$ (remarquer qu'en ajoutant une lettre (``espace''), tout codage non singulier devient uniquement décodable). Cette borne est elle atteinte ?

\item Montrer que le codage non singulier qui minimise $\E(\ell(X))$ est celui qui utilise au maximum les suites de lettres courtes, en attribuant les suites les plus courtes aux éléments de plus forte probabilité. En déduire la formule
\begin{eqnarray*}
L_{ns}(X)=\sum_{i=1}^{|E|}p(x_i)\lceil \log_2 (\frac{i}{2}+1) \rceil.
\end{eqnarray*}

\item On note
\begin{eqnarray*}
M=\sum_{i=1}^{|E|}p(x_i)\log_2 (\frac{i}{2}+1).
\end{eqnarray*}
Prouver l'encadrement $M\leq L_{ns}(X)<M+1$. Posant 
\begin{eqnarray*}
c=\sum_{i=1}^{|E|}\frac{1}{\frac{i}{2}+1}, \quad q(x_i)=\frac{1}{c}\frac{1}{\frac{i}{2}+1},
\end{eqnarray*}
utiliser $D(p||q)$ pour minorer $H(X)-M$.

\item Majorer $c$ et en déduire l'encadrement
\begin{eqnarray*}
H(X)-\log_2 \log_2 (|E|)-2\leq L_{ns}(X)<H(X)+1.
\end{eqnarray*}

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item On ajoute un caractère ``espace'' à la fin de chacun des mots-code. Le codage $C'$ obtenu est uniquement décodable, et $\E(\ell'(X))=\E(\ell(X))\geq +1$. D'après le Théorème du codage de source de Shannon, $\E(\ell'(X))\geq \frac{H(X)}{\log_2 3}$, d'où $\E(\ell(X))\geq \frac{1}{\log_2 3}H(X)-1$. Cette borne n'est pas atteinte. En effet, la borne de Shannon est atteinte uniquement pour des codages qui satisfont $\sum_{x\in E} 3^{-\ell'(x)}=1$. Or dans un codage comme $C'$, il n'y a aucun mot de longueur $1$, et pour $k\geq 2$, le nombre de mots de longueur $k$ est $\leq 2^{k-1}$, donc
\begin{eqnarray*}
\sum_{x\in E} 3^{-\ell'(x)}\leq \sum_{k=2}^{\infty}2^{k-1}3^{-k}=\frac{2}{3}<1.
\end{eqnarray*} 

\item La seule contrainte sur l'application $C:E\to \{0,1\}^*$ est d'être injective. Modifier $C$ en $x\in E$ en remplaçant $C(x)$ par une suite plus courte non encore utilisée fait diminuer la longueur moyenne. Donc on peut supposer que les $|E|$ suites les plus courtes sont toutes utilisées. Etant donnés $x\not=y\in E$, échanger $C(x)$ et $C(y)$ diminue la longueur moyenne si la suite la plus courte est associée à l'élément de plus forte probabilité. Donc on peut supposer que $\ell$ est fonction décroissante de $p$. Ordonnons les éléments de $E$ par probabilité décroissante. Dans un codage non singulier optimal, les deux premiers éléments sont codés par des suites de longueur $1$, les $4$ suivant par des suites de longueur $2$, etc... La longueur $\ell(x_i)$ du $i$-ème élément de $E$ satisfait
\begin{eqnarray*}
\sum_{k=1}^{\ell(x_i)-1}2^k < i \leq \sum_{k=1}^{\ell(x_i)}2^k ,
\end{eqnarray*}
i.e.
\begin{eqnarray*}
2^{\ell(x_i)}-2 < i \leq 2^{\ell(x_i)+1}-2 ,
\end{eqnarray*}
ce qui s'écrit aussi
\begin{eqnarray*}
\ell(x_i)<\log_2 (i+2)\leq\ell(x_i)+1,
\end{eqnarray*}
soit $\ell(x_i)=\lceil \log_2 (i+2) -1\rceil=\lceil \log_2 (\frac{i}{2}+1)\rceil$.
D'où la formule $\displaystyle L_{ns}(X)=\sum_{i=1}^{|E|}p(x_i)\lceil \log_2 (\frac{i}{2}+1) \rceil$.

\item Pour tout $i$, $\log_2 (\frac{i}{2}+1)\leq \lceil \log_2 (\frac{i}{2}+1) \rceil<\log_2 (\frac{i}{2}+1) +1$. La somme pondérée donne $M\leq L_{ns}(X)<M+1$. Comme $q$ est une distribution de probabilité,
\begin{eqnarray*}
0&\leq& D(p||q)=\sum_{i=1}^{|E|}p(x_i)\log_2 p(x_i)-\sum_{i=1}^{|E|}p(x_i)\log_2 q(x_i)\\
&=&-H(X)+\sum_{i=1}^{|E|}p(x_i)\log_2 (c(\frac{i}{2}+1))\\
&=&-H(X)+\log_2 (c)+M,
\end{eqnarray*}
d'où $H(X)-M\leq\log_2 (c)$.

\item On utilise l'encadrement de la série harmonique par le logarithme népérien : si $H(k)=\sum_{j=1}^{n}\frac{1}{j}$, alors $H(k)\leq \ell n(k)+1$. Ici,
\begin{eqnarray*}
c=\sum_{i=1}^{|E|}\frac{1}{\frac{i}{2}+1}=2(H(|E|+2)-1-\frac{1}{2})\leq \ell n(|E|+2)-2\leq \ell n(|E|).
\end{eqnarray*}
Il vient $\log_2 (c)\leq \log_2 \log_2 (|E|)-\log_2 \log_2 (e)\leq \log_2 \log_2 (|E|)+2$. D'où la minoration $L_{ns}(X)\geq M\geq H(X)-\log_2 \log_2 (|E|)-2$.
Elle est bonne lorsque $H(X)$ est grand.

La majoration résulte du Théorème du codage de source (existence de codages de longueur moyenne $<H(X)+1$). Elle n'est pas très bonne.

\end{exoliste}
\end{sol}

\begin{exercice}{Combien ai-je de jouets ?}

Je cache un certain nombre de jouets dans mon tiroir. Nous jouons au jeu des 10 questions (je choisis un jouet, tu me poses des questions très astucieuses, je reponds par oui ou par non, jusqu'à ce que tu devines quel jouet j'ai choisi) de façon répétée. En moyenne, il te suffit de 6.65 questions. Peut on donner une minoration grossière du nombre de jouets que contient mon tiroir ?

\end{exercice}

\begin{sol}

Soit $X$ la variable aléatoire ``choix d'un jouet'', à valeurs dans l'ensemble $E$ des jouets. Le devineur est très astucieux, cela signifie qu'il utilise une excellente stratégie, qui donne une durée moyenne proche de l'entropie $H(X)$, en tout cas inférieure à $H(X)+1$. Quelle que soit la loi de $X$, $H(X)\leq \log_2 |E|$. On en déduit que $5.65=6.65 -1\sim H(X)\leq \log_2 |E|$, d'où $|E|\geq 2^{5.65}=50$.
Ca fait beaucoup de jouets.

\end{sol}

\begin{exercice}{Vin empoisonné}

On doit décider laquelle parmi 6 bouteilles de vin contient un poison mortel. On peut dispose d'un certain nombre de rats de laboratoire, on peut leur faire goûter des mélanges. L'effet du poison est immédiat, même à faible dose. Un rat qui a goûté et survécu est saoûl donc ne peut être réutilisé. Il s'agit d'utiliser le moins de rats possible, sachant que la probabilité que le poison se trouve dans la $i$-ème bouteille est donnée par le tableau
\begin{tabular}{|l|cccccc|}
\hline
$i$ & 1&2&3&4&5&6\\
\hline
$p(i)$   &$\frac{8}{23}$&$\frac{6}{23}$&$\frac{4}{23}$&$\frac{2}{23}$&$\frac{2}{23}$&$\frac{1}{23}$\\
\hline
\end{tabular}.

\begin{exoliste}

\item Quelle est l'espérance du nombre de rats utilisés ?

\item Par quel mélange faut il commencer ?

\item Quelle est l'espérance du nombre de rats sacrifiés ?

\item Le protocole retenu minimise t'il aussi l'espérance du nombre de rats sacrifiés ?

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Il s'agit d'un jeu des 10 questions. On construit l'arbre de Huffman associé à la distribution $p$. On fusionne 6 et 5 en un noeud 7 de probabilité $\frac{1}{23}+\frac{2}{23}=\frac{3}{23}$. On fusionne 4 et 7 en un noeud 8 de probabilité $\frac{2}{23}+\frac{3}{23}=\frac{5}{23}$. On fusionne 3 et 8 en un noeud 9 de probabilité $\frac{4}{23}+\frac{5}{23}=\frac{9}{23}$. On fusionne 2 et 1 en un noeud 10 de probabilité $\frac{6}{23}+\frac{8}{23}=\frac{14}{23}$. On fusionne 9 et 10 en un noeud 11 de probabilité $\frac{9}{23}+\frac{14}{23}=1$. Le nombre moyen de questions est
\begin{eqnarray*}
2.\frac{8}{23}+2.\frac{6}{23}+2.\frac{4}{23}+3.\frac{2}{23}+4.\frac{2}{23}+4.\frac{1}{23}=\frac{54}{23}=2.35..
\end{eqnarray*}
D'après l'optimalité des codes de Huffman, on ne peut pas faire mieux.

\medskip

\def\GraphLegend{Arbre de Huffman}
\figinit{cm}
\def\Xori{0}
\def\Yori{0}
\figpt{11}:(\Xori,\Yori)
\figpt{10}:(-2,1)
\figpt9:(2,1)
\figpt3:(1,2)
\figpt8:(4,2)
\figpt4:(1.5,2)
\figpt1:(-4,2)
\figpt2:(-1,2)
\figpt4:(3,3)
\figpt7:(6,3)
\figpt5:(5,4)
\figpt6:(8,4)
% 2. Creation of the graphical file
\figdrawbegin{}
\figdrawline [11,9]
\figdrawline [11,10]
\figdrawline [10,1]
\figdrawline [10,2]
\figdrawline [9,3]
\figdrawline [9,8]
\figdrawline [8,4]
\figdrawline [8,7]
\figdrawline [7,5]
\figdrawline [7,6]
\figdrawend
% 3. Writing text on the figure
\figvisu{\figBoxA}{\GraphLegend}{%
\figwrites {11}:$11$(5pt) 
\figwrites {10}:$10$(5pt) 
\figwritew 1:$1$(5pt)
\figwritee 2:$2$(5pt)
\figwritew 3:$3$(5pt) 
\figwritew 4:$4$(5pt) 
\figwritew 5:$5$(5pt) 
\figwritee 6:$6$(5pt) 
\figwrites 7:$7$(5pt) 
\figwrites 8:$8$(5pt)
\figwrites 9:$9$(5pt)
}
\centerline{\box\figBoxA}


\item Les mots-codes donnés par l'arbre de Huffman sont
\begin{center}
\begin{tabular}{|l|cccccc|}
\hline
$i$ & 1&2&3&4&5&6\\
\hline
$C(i)$   &00&01&10&110&1110&1111\\
\hline
\end{tabular}
\end{center}
La première question doit départager le sous-ensemble $\{1,2\}$ de son complémentaire. On doit donc faire boire au premier rat un mélange des bouteilles 1 et 2, ou bien des autres. Comme la probabilité que le poison se trouve dans l'une des bouteilles 1 et 2 vaut $\frac{14}{23}>\frac{1}{2}$, on a intérêt à faire boire au premier rat un mélange des bouteilles 3, 4, 5 et 6. On en tirera la même information, avec moins de chances de tuer le rat.

\item Sans modifier l'arbre, on modifie les questions, de sorte que la réponse 1 corresponde au sacrifice d'un rat. A chaque fois, on choisit le mélange qui a la probabilité la plus faible d'être empoisonné. On vient de voir que pour la première question, le mélange est 3456. En cas de réponse négative, le mélange de la 2e question est 2. En cas de réponse positive, le mélange de la 2e question est 3. En cas de réponse négative, le mélange de la 3e question est 4. En cas de réponse négative, le mélange de la 4e question est 6. Cela donne le codage
\begin{center}
\begin{tabular}{|l|cccccc|}
\hline
$i$ & 1&2&3&4&5&6\\
\hline
$C'(i)$   &01&00&11&101&1000&1001\\
\hline
\end{tabular}
\end{center}

\medskip

\def\GraphLegend{Le même arbre disposé de sorte qu'on va à droite quand on sacrifie un rat}
\figinit{cm}
\def\Xori{0}
\def\Yori{0}
\figpt{11}:(\Xori,\Yori)
\figpt{10}:(-2,1)
\figpt9:(2,1)
\figpt3:(4,2)
\figpt8:(1,2)
\figpt4:(3,3)
\figpt1:(-1,2)
\figpt2:(-4,2)
\figpt7:(0,3)
\figpt5:(-1,4)
\figpt6:(2,4)
\figptbary 12:[11,9 ; 1,{1.5}]
\figptbary 13:[10,1 ; 1,2]
\figptbary 14:[9,3 ; 1,2]
\figptbary 15:[8,4 ; 1,2]
\figptbary 16:[7,6 ; 1,2]

% 2. Creation of the graphical file
\figdrawbegin{}
\figdrawline [11,9]
\figdrawline [11,10]
\figdrawline [10,1]
\figdrawline [10,2]
\figdrawline [9,3]
\figdrawline [9,8]
\figdrawline [8,4]
\figdrawline [8,7]
\figdrawline [7,5]
\figdrawline [7,6]
\figdrawend
% 3. Writing text on the figure
\figvisu{\figBoxA}{\GraphLegend}{%
\figwrites {11}:$11$(5pt) 
\figwrites {10}:$10$(5pt) 
\figwritee 1:$1$(5pt)
\figwritew 2:$2$(5pt)
\figwritee 3:$3$(5pt) 
\figwritee 4:$4$(5pt) 
\figwritew 5:$5$(5pt) 
\figwritee 6:$6$(5pt) 
\figwrites 7:$7$(5pt) 
\figwrites 8:$8$(5pt)
\figwrites 9:$9$(5pt)
\figwrites 12:$\dagger$(5pt)
\figwrites 13:$\dagger$(5pt)
\figwrites 14:$\dagger$(5pt)
\figwrites 15:$\dagger$(5pt)
\figwrites 16:$\dagger$(5pt)
}
\centerline{\box\figBoxA}

\medskip

Le nombre de rats sacrifiés est le nombre de 1 dans le mot-code. Le nombre moyen de rats sacrifiés est
\begin{eqnarray*}
1.\frac{8}{23}+0.\frac{6}{23}+2.\frac{4}{23}+2.\frac{2}{23}+1.\frac{2}{23}+2.\frac{1}{23}=\frac{24}{23}=1.04..
\end{eqnarray*}

\item Non. On peut faire en sorte que, quoi qu'il arrive, au plus un rat est sacrifié. Il suffit de faire goûter le contenu d'une bouteille à la fois. Il n'est pas nécessaire de faire goûter la bouteille 1, il suffit, pour savoir si elle est empoisonnée, d'avoir goûté toutes les autres. L'espérance du nombre de rats sacrifiés, dans ce cas, vaut $1-\frac{8}{23}=\frac{15}{23}=0.65..$.

\end{exoliste}
\end{sol}

\begin{exercice}{Jeu des 10 questions aléatoires}

Je cache $m=2^n$ jouets dans mon tiroir $E$, $n$ grand. Nous jouons au jeu des 10 questions, mais tu es très bête, tu tires tes questions au hasard. Une question étant une fonction $f:E\to\{0,1\}$, la tirer au hasard signifie tirer indépendamment au hasard les valeurs $f(x)$, $x\in E$, suivant $\mathcal{B}(\frac{1}{2})$. On pose successivement $k$ questions tirées indépendamment au hasard, et on obtient $k$ fonctions $f_k :E\to\{0,1\}$.

\begin{exoliste}

\item Soit $x_0 \in E$. On note $N$ le nombre de $x\in E\setminus\{x_0\}$ tels que pour tout $i=1,\ldots,k$, $f_i (x)=f_i (x_0)$. Quelle est la loi de $N$ ?

\item On suppose que $k=n-1$. Donner une approximation de la loi de $N$. En déduire que pour tout $x\in E$, avec probabilité bornée inférieurement, le jeu se termine en moins de $n-1$ questions. 

\item On suppose que $k=n-1$. Montrer qu'il existe $x\in E$ pour lequel le jeu nécessite au moins $n$ questions.

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item Pour $x\in E$ et $i\leq k$, soit $Y_{x,i}$ la variable aléatoire qui vaut $1$ si $f_i (x)=f_i (x_0)$, et qui vaut $0$ sinon. Alors les $Y_{x,i}$ sont indépendantes, de même loi $\mathcal{B}(\frac{1}{2})$. Soit $Z_{x}=\prod_{i=1}^{k}Y_{x,i}$ la variable qui vaut $1$ si $f_i (x)=f_i (x_0)$ pour tout $i=1,\ldots,k$, et qui vaut $0$ sinon. Les $Z_x$ sont indépendantes. 
\begin{eqnarray*}
\PP(Z_x =1)=\prod_{i=1}^{k}\PP(Y_{x,i}=1)=\frac{1}{2^{k}},
\end{eqnarray*}
donc $Z_x$ suit la loi $\mathcal{B}(\frac{1}{2^k})$. Le nombre de $x\in E\setminus\{x_0\}$ tels que pour tout $i=1,\ldots,k$, $f_i (x)=f_i (x_0)$ vaut
$N=\sum_{x\in E\setminus\{x_0\}}Z_x$, il suit une loi binomiale $\mathcal{B}(\frac{1}{2^k},|E|-1)$.

\item Lorsque $k=n-1$, $\E(N)=\frac{2^n -1}{2^{n-1}}$ est proche de $2$. On sait que $\mathcal{B}(\frac{1}{2^{n-1}},2^n -1)$ est proche de la loi de Poisson de paramètre $2$. En particulier, $\PP(N=0)$ est proche de $e^{-2}>0$. Si $N=0$, $x_0$ est l'unique solution du système d'équations $f_i (x)=f_i (x_0)$, $i=1,\ldots,n-1$, donc le jeu se termine en au plus $n-1$ questions. Cet argument s'applique pour tout $x_0 \in E$, avec la même borne inférieure sur $\PP(N=0)$.

\item Lorsque $k<n$, $F_k =(f_1 ,\ldots,f_k):E\to\{0,1\}^k$ ne peut pas être injective, donc il existe deux jouets distincts $x\not=x'\in E$ pour lesquels les réponses à toutes les questions sont les mêmes. Pour ces jouets, le jeu n'est pas terminé après $k$ questions, il en faut au moins $n$.

\end{exoliste}
\end{sol}


\end{document}

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

\item 

\end{exoliste}
\end{exercice}

\begin{sol}
\begin{exoliste}

\item 

\end{exoliste}
\end{sol}