
\begin{enumerate}
\item
\begin{enumerate}
\item Dans ce programme, \texttt{R1} est une liste initialement composée des nombres 1, 2, ..., $n$. Elle représente ainsi la partie de gauche de l'espace séparé en deux, les $n$ nombres distincts représentant les $n$ particules. \texttt{R2} est une liste vide représentant ainsi la partie de droite, qui est initialement vide.

\medskip

On entre ensuite dans une boucle dans laquelle on exécute $n$ fois la même chose: on choisit un nombre aléatoire \texttt{j} entre 1 et $n$; si la particule $j$ est dans $R_1$, on la transfert dans $R_2$ en l'ajoutant dans la liste \texttt{R2} et en la supprimant de la liste \texttt{R1}.

\medskip

Une fois hors de la boucle, la fonction retourne la longueur des deux lites, soit le nombre de particules dans chacune des parties.

\item Effectuons plusieurs simulations:
\begin{console}
>>> Ehrenfest(200,2000)
(100,100)
>>> Ehrenfest(900,2000)
(424, 476)
>>> Ehrenfest(900,5000)
(460, 440)
\end{console}
On peut alors conjecturer qu'à longs termes (après un très grand nombre d'étapes), les particules se répartissent de façon équitable.
\end{enumerate}

\item \textbf{Étude mathématique pour $\pmb{k=2}$.}
\begin{enumerate}
\item Le graphe complété est le suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[Math]{E_{2,0}}
\Vertex[Math,x=3,y=0]{E_{1,1}}
\Vertex[Math,x=6,y=0]{E_{0,2}}
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{2,0})(E_{1,1})
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{0,2})
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{0,2})(E_{1,1})
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{2,0})
\end{tikzpicture}
\end{center}
En effet, le passage de $E_{2,0}$ à $E_{1,1}$ est inéluctable, d'où une probabilité de passage de l'état  $E_{2,0}$ à $E_{1,1}$ égale à 1.

De même pour le passage de  $E_{0,2}$ à $E_{1,1}$.

Quant aux probabilités de passage de $E_{1,1}$ à l'un des états $E_{0,2}$ ou  $E_{2,0}$, elles sont identiques, donc égales à 0,5.

\item $U_0=\begin{pmatrix}1\\0\\0\end{pmatrix}$ et $M=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}$.

\item Montrons par récurrence ces égalités.
\begin{itemize}
\item \textbf{Initialisation.}
\begin{itemize}
\item $U_1=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}1\\0\\0\end{pmatrix}=\begin{pmatrix}0\\1\\0\end{pmatrix}$.
\item $U_2=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0\\1\\0\end{pmatrix}=\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}$.
\item $U_3=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}=\begin{pmatrix}0\\1\\0\end{pmatrix}=U_1$.
\item $U_4=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0\\1\\0\end{pmatrix}=\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}=U_2$.
\end{itemize}

\item \textbf{Hérédité.} Supposons que pour un entier $p$ fixé, $U_{2p}=U_2$ et $U_{2p+1}=U_1$.
\begin{itemize}
\item $U_{2p+2}=MU_{2p+1}=MU_1=U_2$ et donc $U_{2(p+1)} = U_2$;
\item $U_{2p+3}=MU_{2p+2}=MU_2=U_3=U_1$ et donc $U_{2(p+1)+1}=U_1$.
\end{itemize}
L'hérédité est alors vérifiée.
\end{itemize}
Ainsi, les égalités sont vraies pour tout entier $k\geqslant1$.
\end{enumerate}

\item \textbf{Étude mathématique pour $\pmb{k=4}$.}
\begin{enumerate}
\item $U_0 = \begin{pmatrix}0 & 0&  0 & 0 & 1\end{pmatrix}$.

En effet, initialement, il y a 4 particules dans la partie de gauche donc \mbox{$\probavar{X_0}{4}=1$.}

\item Le graphe complété est le suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[Math]{R_0}
\Vertex[Math,x=3,y=0]{R_1}
\Vertex[Math,x=6,y=0]{R_2}
\Vertex[Math,x=9,y=0]{R_3}
\Vertex[Math,x=12,y=0]{R_4}
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](R_0)(R_1)
\Edge[label={0,75},labelstyle={draw=brown,text=brown},style={bend right,->}](R_1)(R_2)
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](R_2)(R_3)
\Edge[label={0,25},labelstyle={draw=brown,text=brown},style={bend right,->}](R_3)(R_4)
\Edge[label={1},labelstyle={draw=brown,text=brown},style={bend right,->}](R_4)(R_3)
\Edge[label={0,75},labelstyle={draw=brown,text=brown},style={bend right,->}](R_3)(R_2)
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](R_2)(R_1)
\Edge[label={0,25},labelstyle={draw=brown,text=brown},style={bend right,->}](R_1)(R_0)
\end{tikzpicture}
\end{center}

La matrice de transition du graphe est donc:
\[
M = \begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
0,25 & 0 & 0,75 & 0 & 0\\
0 & 0,5 & 0 & 0,5 & 0\\
0 & 0 & 0,75 & 0 & 0,25\\
0 & 0 & 0 & 1 & 0
\end{pmatrix}.
\]

\item Calculons l'espérance mathématique de $X_n$:
\begin{itemize}
\item si $n=2p$: $E(X_{2p}) = \frac{3}{4}\times2 + \left( \frac{1}{8} -\frac{1}{2^{2p+1}}\right)\times 4 = 2 + \frac{1}{2^{2p-1}}$;
\item si $n=2p+1$: $E(X_{2p+1}) = 1\times\left(\frac{1}{2}-\frac{1}{2^{2p+1}} \right) + 3\times\left( \frac{1}{2}+\frac{1}{2^{2p+1}}\right)=2-\frac{2}{2^{2p}}$.
\end{itemize}
On constate alors que l'espérance tend vers 2 lorsque $n$ tend vers l'infini, ce qui signifie qu'à longs termes, il ne restera que deux particules dans la partie de gauche.
\end{enumerate}
\end{enumerate}
