\documentclass{pbsheet}
\TITRE{Feuille de TP n°12 \\ 
  Chaînes de Markov à espace d'états au plus dénombrable}
\FORMATION{Épreuve de modélisation - Agrégation Externe de Mathématiques}
\ETABLISSEMENT{Université Paul Sabatier Toulouse III}
\ANNEE{2005}
\MEL{chafai@math.ups-tlse.fr}
\AUTEUR{B. Bercu \& D. Chafaï}
\WEB{http://www.lsp.ups-tlse.fr/Chafai/agregation.html}
\DATE{Décembre 2004}

\begin{document}

%FIXME: un exo sur MCMC et Gibbs sampling. Perfect sampling ?
%FIXME: thoérème de Dynkin sur les fonctions de CM qui sont CM.

%
\section{Quelques rappels}
%

Une \emph{chaîne de Markov} sur un \emph{espace d'états} au plus dénombrable
$\dE$ est une suite de variables aléatoires $(X_n)_{n\in\dN}$ à valeurs dans
$\dE$ telles que pour tout $n\in\dN$,
\begin{equation*}
  \cL(\COND{X_{n+1}}{X_0,\ldots,X_n}) = \cL(\COND{X_{n+1}}{X_n}).
\end{equation*}
En d'autres termes, à tout instant, le «futur» et le «passé» de la chaîne sont
conditionnellement indépendants par rapport au «présent». Lorsque
$\cL(\COND{X_{n+1}}{X_n})$ ne dépend pas de $n$, on dit que la chaîne est
\emph{homogène}. Dans la suite, nous ne nous intéresserons qu'aux chaînes de
Markov homogènes. La loi d'une telle chaîne est entièrement caractérisée par
la donnée de la loi initiale $\cL(X_0)$ et la donnée de la \emph{matrice de
  transition} $\bP=(\bP_{x,y})_{x,y\in\dE}$ définie pour tout $x$ et $y$ dans
$\dE$ par:
\begin{equation}\label{eq:defcm}
 \bP_{x,y}:= \dP(\COND{X_{n+1}=y}{X_n=x}).
\end{equation}
Cette matrice est infinie lorsque $\dE$ est infini. Les coefficients de cette
matrice sont dans $[0,1]$ et chaque ligne est une loi conditionnelle (donc de
somme égale à $1$). On parle alors de matrice \emph{markovienne} ou
\emph{stochastique}. Étudier une chaîne de Markov homogène consiste à analyser
ses propriétés (à temps fini et asymptotiquement), via l'étude de $\bP$, en
fonction de la loi initiale $\cL(X_0)$. Si l'on assimile les lois de
probabilité sur $\dE$ à des \emph{vecteurs ligne} et les fonctions de $\dE$
dans $\dR$ à des \emph{vecteurs colonne}, on a, en notant $\nu$ la loi de
$X_0$, $x\in\dE$ un état quelconque, et $f:\dE\to\dR$ une fonction: $$
\cL(X_n) = \nu \bP^n %
\text{\quad et \quad} %
\cL(\COND{X_n}{X_0=x}) = \bP^n_{x,\cdot} %
\text{\quad et \quad} %
\bE(\COND{f(X_{n+m})}{X_n=x})=(\bP^m f)_x. $$
Si $\mu$ est une mesure sur
$\dE$ et si $x\in \dE$, on note $\mu_x=\mu(x)=\mu(\{x\})$; et si $f:\dE\to\dR$
est $\mu$-intégrable, alors $\mu(f)$ désigne $\int_\dE\!\!f\,d\mu$. Comme
$\dE$ est au plus dénombrable, une suite de lois $(\mu_n)_{n\in\dN}$ sur $\dE$
converge vers la loi $\mu$ si et seulement si pour tout $x\in \dE$, la suite
de réels $(\mu_n(x))_{n\in\dN}$ converge vers $\mu(x)$.

\begin{thm}[Propriété de Markov forte]
  Soit $(X_n)_{n\in\dN}$ une chaîne de Markov d'espace d'états $\dE$ et soit
  $\tau$ un temps d'arrêt pour la filtration naturelle $(\cF_n)_{n\in\dN}$ où
  $\cF_n:=\si(X_0,\ldots,X_n)$. Pour tout $x\in \dE$, on a sur l'événement
  $\BRA{X_\tau=x}\cap\BRA{\tau<\infty}$:
  \begin{equation*}
    \cL\PAR{\COND{\PAR{X_{\tau+n}}_{n\in\dN}}{\cF_\tau}} %
    = \cL\PAR{\COND{(X_n)_{n\in\dN}}{X_0=x}}.
  \end{equation*}
  En particulier, pour un temps d'arrêt déterministe $\tau\equiv m$, on
  retrouve la propriété de Markov faible qui revient à la propriété de base
  \eqref{eq:defcm} des chaînes de Markov.
\end{thm}

\begin{defi}[Prendre la mesure du temps qui passe]
  Soit $(X_n)_{n\in\dN^*}$ une chaîne de Markov d'espace d'états $\dE$ et soit
  $\mu$ une mesure positive sur $\dE$. On dit que $\mu$ est une mesure\ldots
  \begin{enumerate}
  \item\emph{invariante}\label{en:invariante} %
    lorsque $\mu \bP = \mu$, i.e. le vecteur $\mu^\top$ est un vecteur propre
    de $\bP^\top$ associé à la valeur propre $1$;
  \item\emph{stationnaire}\label{en:stationnaire} %
    lorsque $\cL(X_0)=\mu$ implique que pour tout $n\in\dN$, $\cL(X_n)=\mu$;
  \item\emph{asymptotique}\label{en:asymptotique} %
    lorsqu'il existe une loi de probabilité $\nu$ telle que
    $\PAR{\cL(X_0)=\nu}\ \Rightarrow\ \PAR{X_n\limL{n}\mu}$.
  \end{enumerate}
\end{defi}

\begin{prop}[Cosi fan tute ?]
  Une mesure asymptotique est toujours une mesure de probabilité.  De plus,
  pour une mesure de probabilité $\mu$, les propriétés \ref{en:asymptotique},
  \ref{en:invariante} et \ref{en:stationnaire} sont équivalentes.
\end{prop}

\begin{thm}[Perron-Frobenius] \label{th:perron-frobenius} Toute chaîne de
  Markov homogène à valeurs dans un espace d'états fini\footnote{Ce théorème,
    dont la preuve fait appel à la compacité de l'ensemble des mesures de
    probabilités sur $\dE$ (extraire une sous suite convergente de la suite
    $\mu_n:=\frac{1}{n+1}(\mu+\mu\bP+\cdots+\mu\bP^n)$), n'est plus vrai si
    l'espace d'états est infini. Un contre exemple est donné par la marche
    aléatoire simple sur $\dE=\dZ$, pour laquelle
    $\bP_{i,j}=\frac{1}{2}\,\de_{|i-j|=1}$, cf. Barbe-Ledoux, exercice 4.6
    page 214 et suivantes. La mesure invariante de cette chaîne est la 
    mesure de comptage sur $\dZ$, qui n'est pas une loi de probabilité.} $\dE$ possède
  au moins une mesure de probabilité invariante.
\end{thm}

On remarquera que pour toute matrice stochastique $\bP$,  $1$ est valeur propre
de $\bP$, associée au vecteur propre $(1,\ldots,1)$. Il en découle que $1$ est
également valeur propre de $\bP^\top$, mais les espaces propres ne sont pas
ceux de $\bP$ en général. Le théorème \ref{th:perron-frobenius} assure
l'existence d'un vecteur propre $(p_1,\ldots,p_n)$ de $\bP^\top$ associé à la
valeur propre $1$, dont les composantes sont positives ou nulles et de somme $1$.

\begin{rem}[Un peu de géométrie convexe élémentaire]
  L'ensemble des lois de probabilité sur $\{1,\ldots,n\}$ est un convexe
  compact de $\dR^n$ dont les point extrémaux sont les masses de Dirac. On
  parle alors de simplexe $\La_n$ des lois de probabilités sur
  $\{1,\ldots,n\}$. La frontière de $\La_n$ dans l'hyperplan affine de $\dR^n$ 
  qui le contient est constituée des éléments de $\La_n$ dont le support est 
  strictement inclus dans $\{1,\ldots,n\}$.
  L'ensemble des matrices stochastiques de taille $n\times n$ est un convexe
  compact de $\cM_n(\dR)$ dont les points extrémaux sont les matrices de
  permutations (sur chaque ligne et sur chaque colonne, on trouve un seul $1$
  et que des $0$). Ces matrices extrémales sont donc orthogonales et
  bistochastiques, et leurs lignes et leur colonnes sont des masses de Dirac
  (points extrémaux de $\La_n$).
\end{rem}

\section{Simulation d'une chaîne de Markov}

\noindent\textbf{Approche pas à pas.}
Pour simuler une trajectoire $x_0,\ldots,x_n$ d'une chaîne de Markov de loi
initiale $\nu:=\cL(X_0)$ et de matrice de transition $\bP$, on peut procéder
de la sorte (pour $n>0$):
\begin{enumerate}
\item Poser $k=0$;
\item Simuler une réalisation $x_k=x_0$ de la loi discrète $\nu:=\cL(X_0)$
\item Incrémenter $k$;  \label{en:simcm}
\item Simuler une réalisation $x_k$ de loi discrète
  $\bP_{x_{k-1},\cdot}:=\sum_{y\in\dE}\bP_{x_{k-1},y}\,\de_y$;
\item Si $k<n$ alors passer à l'étape \ref{en:simcm} sinon sortir en affichant
  $x_0,\ldots,x_n$.
\end{enumerate}
Rappelons que les lois discrètes à nombre au plus dénombrable d'atomes peuvent
être simulées très simplement à partir de la loi uniforme en partitionnant
l'intervalle $[0,1]$ en $[0,p_1[\cup[p_1,p_1+p_2[\cup\ldots$ Cette technique
de simulation des chaînes de Markov est utilisable quelque soit le cardinal de
$\dE$, y compris lorsque la chaîne n'est pas homogène.

\noindent\textbf{Approche matricielle.} Lorsque $\dE$ est fini et que la
chaîne est homogène, $\bP$ est une matrice finie fixée et les choses sont plus
simples. Ainsi, si l'on souhaite alors simuler $x_n$ plutôt que la trajectoire
toute entière, il suffit de calculer par récurrence la loi discrète
$\cL(X_n)=\nu\bP^n$ par multiplication du vecteur ligne $\nu\bP^k$ par la
matrice $\bP$, pour $k=0,\ldots,n$. Cette approche matricielle permet
également de simuler la trajectoire mais nécessite alors le stockage de la
suite $\bP,\ldots,\bP^n$ des puissances de $\bP$.

\begin{exo}[Un peu de calcul pour mieux calculer] 
  Évaluer la complexité algorithmique (nombre d'opérations élémentaires) des
  deux approches en fonction du cardinal de $\dE$, de $n$ et de la structure
  de $\bP$. Comparer leur mérites et tares respectifs, puis donner enfin les
  circonstances qui feront préférer l'une à l'autre.
\end{exo}

\section{Les chaînes dans tous leurs états}

Soit $(X_n)_{n\in\dN}$ une chaîne de Markov d'espace d'états $\dE$, et de
matrice de transition $\bP$. Pour tout $\dF\subset\dE$ et tout $n\in\dN^*$, on
note $\tau_\dF^{n+1}:=\inf\BRA{k>\tau_\dF^n,\;X_k\in\dF}$ avec $\tau_\dF^0=0$
le $(n+1)$-ième \emph{temps de passage} dans $\dF$. De même, on note
$N_\dF:=\sum_{n=1}^{\infty} \rI_\BRA{X_n\in\dF}$ le nombre de passages en
$\dF$ à partir du temps $1$. On dit qu'un état $x\in\dE$ est \emph{récurrent}
lorsque $\dP(\COND{\tau_x^1<\infty}{X_0=x})=1$, et qu'il est
\emph{transitoire} sinon. Un état récurrent $x\in\dE$ est dit \emph{récurrent
  nul} (resp. \emph{récurrent positif}) lorsque
$\bE(\COND{\tau_x^1}{X_0=x})=+\infty$ (resp.
$\bE(\COND{\tau_x^1}{X_0=x})<+\infty$). La fonction
$\bG:\dE\times\dE\to\dR_+\cup\BRA{+\infty}$ définie par 
\begin{equation*}
  \bG(x,y):=\sum_{n=1}^{\infty} \bP^n_{x,y} = \bE(\COND{N_y}{X_0=x}),
\end{equation*}
est appelée \emph{potentiel} de la chaîne. Pour tout $x$ et $y$ dans $\dE$, on
note $x \to y$, et on dit que $x$ \emph{conduit} à $y$, lorsque $\bG(x,y)>0$.
Un état $x\in\dE$ est récurrent si et seulement si $\bG(x,x)=+\infty$. On
montre que sur l'ensemble $\dE_R$ des états récurrents, la relation binaire
$\to$ est une relation d'équivalence, dont les classes sont appelées
\emph{classes de récurrence}. La relation d'équivalence $\to$ permet
d'associer à la chaîne un graphe dont les sommets sont les états. On montre
que pour tout état $x\in\dE$, $$
\cL(\COND{N_x}{X_0=x}) %
= \cG(\rho(x)):=(1-\rho(x))\,\sum_{k=0}^{+\infty}(\rho(x))^k\,\de_k, $$
où
$\rho(x):=\dP(\COND{\tau_x^1<\infty}{X_0=x})$. Un état $x\in\dE$ est dit
\emph{absorbant} lorsque $\bP_{x,x}=1$. Un état absorbant est donc un piège
qui fige la chaîne. On dit qu'un sous-ensemble d'états $\dF\subset\dE$ est
\emph{clos} lorsque pour tout état initial $x\in\dF$,
$\dP(\COND{X_1\in\dF}{X_0=x})=1$. En d'autres termes, un ensemble clos réduit
l'espace d'états de la chaîne. Un sous-ensemble clos $\dF\subset\dE$ est dit
\emph{clos irréductible} lorsqu'il ne contient pas deux sous ensembles clos
disjoints.

\begin{prop}[Décomposition de l'espace d'états]
  L'espace d'états $\dE$ se décompose en une union disjointe (partition)
  constituée du sous-ensemble $\dE_T$ des états transitoires et du
  sous-ensemble $\dE_R$ des états récurrents. Ce dernier se décompose à son
  tour en une union disjointe de sous-ensembles clos irréductibles qui sont
  exactement les classes de récurrence. Les classes singletons correspondent
  aux états absorbants. La propriété d'être récurrent positif est constante
  sur chaque classe de récurrence.
\end{prop}

On peut montrer qu'une mesure asymptotique ne charge pas les points
transitoires. Ce n'est pas le cas des mesures invariantes, comme le montre un
exemple de marche aléatoire.

\subsection{Loi forte des Grands Nombres \& convergence vers l'équilibre}

On dit qu'une chaîne de Markov est \emph{récurrente-irréductible} (RI) lorsque
l'espace d'état est consitué d'une unique classe de récurrence, en
particulier, elle ne possède pas d'états transitoires. On dit qu'elle est RI
positive (RIP) lorsque son espace d'état se réduit à la classe de récurrence
constituée des états récurrents positifs.

\begin{thm}[Loi des Grands Nombres forte pour chaînes RIP]\label{th:cv-ri}
  Si $(X_n)_{n\in\dN}$ est une chaîne de Markov RIP, alors elle possède une
  unique loi de probabilité invariante $\mu$, et cette mesure charge tous les
  états. Pour toute fonction $f:\dE\to\dR$ $\mu$-intégrable, on a quelque soit
  la loi de $X_0$:
  \begin{equation*}
    \frac{f(X_1) + \cdots + f(X_n)}{n} \limPS{n} \int_\dE\!f\,d\mu. 
  \end{equation*}
\end{thm}

On trouvera une preuve du théorème \ref{th:cv-ri} dans \cite[Th. VIII.6.9 p.
234]{barbe-ledoux}. Lorsque la chaîne est RI mais pas positive, tous les états
sont récurrents nuls, et la chaîne possède une mesure invariante $\mu$
vérifiant $\mu(\dE)=+\infty$, unique à dilatation près. La loi des grands
nombres reste alors valable mais pour les rapports de la forme
$\frac{f(X_1)+\cdots+f(X_n)}{g(X_1)+\cdots+g(X_n)}$ où $f$ est
$\mu$-intégrable et $g$ est positive avec $\bE(g)>0$, cf. \cite[Prop.
2.15]{bouleau2bis} et \cite[Sec. 9.3]{cottrell-duhamel}.

\begin{rem}[Ergodicité]
  Le théorème \ref{th:cv-ri} exprime le fait que la moyenne en temps converge
  vers la $\mu$-moyenne en espace où $\mu$ est la mesure invariante. En effet,
  pour $f=\rI_{\{x\}}$ où $x\in\dE$ est un état fixé, on a:
  \begin{equation*}
    \frac{1}{n}\,\CARD\{0\leq k\leq n,\text{ tels que }X_k =x\}\limPS{n}\mu(x).
  \end{equation*}
  La fraction de temps passée sur un état (temps d'occupation) «converge» vers
  la masse relative de ce point pour la loi invariante. En d'autre termes, la
  mesure empirique $\dP_n:=\frac{1}{n}\,(X_1+\cdots+X_n)$ converge presque
  sûrement en loi vers $\mu$ lorsque $n$ tend vers l'infini.
\end{rem}

On appelle \emph{période} d'un état $x\in\dE$ le PGCD des entiers $n$ tels que
$\bP^n_{x,x}>0$. On peut montrer que la période est constante sur chaque
classe de récurrence. Si $(X_n)_{n\in\dN}$ est RI de période $d$ et de matrice
de transition $\bP$, alors $\bP^d$ possède exactement $d$ classes de
récurrence, que la chaîne visite de façon cyclique. La périodicité empêche
pour une chaîne RI la convergence de $(\cL(X_n))_{n\in\dN}$ vers une mesure
asymptotique, qui serait un résultat plus fort que le théorème \ref{th:cv-ri}.
On dit qu'une chaîne RI est \emph{apériodique} (RIA) lorsque la période est
égale à $1$. On note RIPA pour \emph{récurrente irréductible positive
  apériodique}. On peut montrer que pour une matrice de transition $\bP$ RI,
il y a équivalence entre
\begin{itemize}
\item apériodicité;
\item $\exists m\in\dN$, tel que $\forall (x,y)\in\dE\times\dE$,
  $\bP^m_{x,y}>0$;
\item $1$ est la seule valeur propre (complexe) de module $1$ de $\bP$.
\end{itemize}

\begin{thm}[Convergence vers l'équilibre pour les chaînes RIPA]\label{th:cv-erg}
  Soit $(X_n)_{n\in\dN}$ une chaîne de Markov RIPA de matrice de transition
  $\bP$. Alors pour toute loi initiale $\nu:=\cL(X_0)$, la suite
  $(X_n)_{n\in\dN}$ converge en loi vers l'unique loi invariante $\mu$. En
  d'autre termes, pour tout vecteur ligne $\nu$, la suite de vecteurs lignes
  $(\nu \bP^n)_{n\in\dN}$ converge vers le vecteur ligne $\mu$. Dit autrement,
  toutes les lignes de la matrice $\bP^n$ convergent vers le vecteur ligne
  $\mu$.
\end{thm}

Le théorème \ref{th:cv-erg} exprime le fait que la chaîne «oublie» la mesure
initiale, i.e. la loi $\cL(X_0)$, au profit de la mesure invariante qui
représente son «équilibre».  Un exemple simple de matrice de
transition RI non apériodique est donné par la chaîne oscillante sur $\{0,1\}$
de matrice de transition \texttt{[0,1;1,0]}.

\begin{rem}[Finis les problèmes]
  Sur un espace d'états fini, une chaîne a au moins un état récurrent. De
  plus, si elle est irréductible, tous ses états sont récurrents positifs
  (i.e. RI=RIP et donc RIA=RIPA) et son unique mesure invariante se normalise
  en une loi de probabilité.  Lorsque l'espace d'états est infini
  (dénombrable), les choses sont un peu plus délicates car les mesures
  positives ne peuvent pas toujours être normalisées en lois de probabilité,
  et le théorème de Perron-Frobenius n'est plus vrai.
\end{rem}

\begin{rem}[Comment approximer l'éventuelle loi invariante d'une chaîne RI ?]
  En vertu du théorème \ref{th:cv-ri}, on peut utiliser un histogramme associé
  à une trajectoire avec un point de départ $x$ quelconque. Si la chaîne est
  RIPA, on pourra alternativement et en vertu du théorème \ref{th:cv-erg}
  utiliser un histogramme associé à un échantillon de réalisations i.i.d. de
  loi commune $\cL(\COND{X_n}{X_0=x})=\bP_{x,\cdot}$ pour un point de départ
  $x$ quelconque.
\end{rem}

\begin{rem}[Astuces visuelles]
  Soit $\bP$ une matrice de transition.
  \begin{itemize}
  \item Si tous ses coefficients sont strictements positifs, alors elle est
    RIA;
  \item Si elle est symétrique, alors la loi uniforme est une mesure
    invariante;
  \item Les états correpondants à des colonnes avec un coefficient $\rho<1$
    sur la diagonale et $0$ ailleurs sont transitoires. Ce sont plus
    précisément des états \emph{répulsifs}. Cette notion d'état répulsif est
    duale de celle d'état absorbant: la chaîne n'atteint jamais un état
    répulsif au temps $n>1$, en revanche, si elle part d'un état $X_0$
    répulsif, elle le quitte définitivement au bout d'un temps aléatoire de
    loi géométrique $\cG(1-\rho)$;
  \item Les états absorbants correspondent exactement aux lignes qui
    contiennent $1$ sur la diagonale et $0$ ailleurs. De plus, les états
    correspondants aux coefficients non nuls de la colonne contenant le $1$
    sont transitoires;
  \item Parmis les états absorbants, certains sont triviaux, car aucun état
    (transitoire) n'y mène. Ils peuvent alors être éliminés de l'espace
    d'états.
  \end{itemize}
\end{rem}

\begin{rem}[Bibliographie expéditive]
  Pour des preuves et des exercices, cf. \cite{barbe-ledoux},
  \cite{revuz-probas}, \cite{norris}, \cite{cottrell-duhamel},
  \cite{foata-fushs}, \cite{baldi-mazliak-priouret}, \cite{bouleau2bis},
  \cite{ycart}.
\end{rem}

%%
\section{Exercices et exemples d'utilisation en modélisation}
%%

\begin{exo}[Sauts symétriques]
  Déterminez la matrice de transition de la chaîne de Markov sur $\{0,1\}$
  telle que $\dP(\COND{X_{n+1}=1}{X_n=1})=p$ et
  $\dP(\COND{X_{n+1}=0}{X_n=0})=q$. Dans quels cas est-elle RI ? RIA ? Dans ce
  dernier cas, déterminer sa mesure invariante théorique et la vérifier
  numériquement, d'abord en considérant les puissances de la matrice de
  transition pour différentes valeurs de $p$, puis en diagonalisant la matrice
  de transition. Cf. \cite[ex. 9.12 p. 286]{cottrell-duhamel}.
\end{exo}

\begin{exo}
  Écrire une fonction \texttt{rtpsim} de simulation d'une loi discrète à
  support au plus dénombrable quelconque à partir de la loi uniforme. S'en
  servir pour écrire une fonction \texttt{rmtpsim} qui permet de simuler la
  loi $\cL(\COND{X_n}{X_0=x})$ d'une chaîne de Markov à espace d'états au plus
  dénombrable partir de sa matrice de transition et du point initial. Lorsque
  l'espace d'états est fini, on pourra passer la matrice de transition en
  paramètre.
\end{exo}

\begin{exo}[Jeux de construction]
  Construire une matrice de transition sur $\{0,1,2,3\}$ RI, d'abord
  apériodique, puis non-apériodique. En utilisant la fonction
  \texttt{rmtpsim}, regarder dans les deux cas les différents régimes
  asymptotiques suivant les valeurs initiales de la chaîne.
\end{exo}

\begin{exo}[Temps d'atteinte géométiques]
  Soit $(X_n)_{n\in\dN}$ une chaîne de Markov d'espace d'états $\dE$ et de
  matrice de transition $\bP$ telle que $\bP_{x,y}>0$ pour tout couple
  $(x,y)\in\dE\times\dE$. On suppose que $\cL(X_0)=\de_x$, i.e. que $X_0=x$
  p.s. où $x\in\dE$ est un état fixé. Soit $y\in\dE$ avec $y\neq x$, et
  $\tau:=\inf\BRA{n\geq1,\ X_n=y}$ le temps d'atteinte de $y$. En utilisant la
  propriété de Markov forte, montrer qu'il existe un réel $\rho\in]0,1[$ tel
  que pour tout $n\in\dN^*$, $\dP(\tau>n)\leq\rho^n$. Comparer ce résultat à
  des simulations, que signifie-t-il pour la marche aléatoire simple ? Cf.
  \cite[ex. VIII.7.4. p. 236]{barbe-ledoux}
\end{exo}

\begin{exo}[Identité de Wald -- Franchissement de barrières -- Chaîne de vie
  et de mort -- Ruine] Soit $(X_n)_{n\in\dN}$ une chaîne de Markov sur $\dN$
  de matrice de transition $\bP_{x,\bullet} :=
  p_x\,\de_{x+1}+r_x\,\de_{x}+q_x\,\de_{x-1}$, où $q_0=0$ et pour tout
  $x\in\dN$, $p_x+r_x+q_x=1$ avec $p_x>0$, et $q_x>0$ si $x>0$. Que peut
  modéliser une telle chaîne ? Pour tout $x\in\dN$, on note
  $\tau_x:=\inf\BRA{n\geq0;\,X_n=x}$ et pour tous réels $a\leq x\leq b$, on
  note $u(x):=\dP_x(\tau_a<\ta_b)$ et $\ga(x):=q_1\cdots q_x / p_1\cdots p_x$
  avec $\ga(0)=1$.
  \begin{enumerate}
  \item Lorsque $a<x<b$, déterminer une relation entre $u(x+1)-u(x)$ et
    $u(x)-u(x-1)$;
  \item Lorsque $a\leq x<b$, calculer $u(a)-u(a+1)$ en fonction de $\ga$ et en
    déduire que pour $a\leq x \leq b$,
    $u(x)=\frac{\ga(x)+\cdots+\ga(b-1)}{\ga(a)+\cdots+\ga(b-1)}$.  Traiter le
    cas où les fonctions $p$ et $q$ sont constantes et égales sur $\dN^*$;
  \item Déterminer $\dP(\COND{\tau_0=\infty}{X_0=0})$. Montrer que la chaîne
    est récurrente si et seulement si $\sum_{x=0}^{+\infty}\ga(x)=+\infty$;
  \item Déterminer les mesures invariantes. En déduire qu'elle est RIP si et
    seulement si $\sum_{x=0}^{+\infty}\frac{p_0\cdots p_{x-1}}{p_1\cdots
      q_x}<+\infty$.
  \end{enumerate}
  On étend à présent l'espace d'états à $\dZ$ et l'on suppose que $p_x$, $r_x$
  et $q_x$ ne dépendent plus de $x$ et qu'ils sont fixés à $p$, $r$, et $q$
  respectivement, avec $r<1$. Soit $a$ et $b$ deux réels tels que $a<0<b$. On
  pose $S_0:=0$ et $S_n=X_1+\cdots+X_n$ pour $n\geq1$. On note
  $\mu:=p\,\de_{+1}+r\,\de_0+q\,\de_{-1}$ et $\vphi:\dR\to\dR$ la transformée
  de Laplace de $\mu$ donnée pour tout $\la\in\dR$ par
  $\vphi(\la):=p\,\exp(-\la)+r+q\,\exp(+\la)$. Que peut modéliser
  $(S_n)_{n\in\dN^*}$ ?
  \begin{enumerate}
  \item Montrer $(S_n+n(1-2p))_{n\in\dN^*}$ est une
    $(\cF_n)_{n\in\dN^*}$-martingale, où $\cF_n:=\si(X_1,\ldots,X_n)$;
  \item Montrer en utilisant le TLC que $T:=\inf\BRA{n\geq1,\ 
      S_n\not\in]a,b[}$ est un temps d'arrêt fini p.s.;
  \item Soit $\la\in\dR$ et $Y_n:=\vphi(\la)^{-n}\,e^{\la S_n}$.  Montrer que
    $(Y_n)_{n\in\dN^*}$ est une $(\cF_n)_{n\in\dN^*}$-martingale;
  \item Soit $\la\in\dR$ tel que $\vphi(\la)\geq1$. Montrer que $\bE(Y_T)=1$;
  \item On suppose dans la suite que $p=q=1/2$. Calculer $\bE(S_T)$,
    $\dP(S_T=a)$, et $\dP(S_T=b)$;
  \item Soit $\al\in\dR$ tel que $\al>1$. En utilisant l'équation
    $\vphi(\la)=\al$, calculer $\bE(\al^{-T}\,\rI_\BRA{S_T=x})$ pour
    $x\in\{a,b\}$;
  \item Calculer $\bE(\COND{T}{S_T})$ et $\bE(T)$. Confronter les prédictions
    à des simulations.
  \end{enumerate}
  Cf. \cite[ex. 8.8 p. 247, ex. 9.16 p. 296]{cottrell-duhamel}.
\end{exo}

\begin{exo}[Temps de record et chaînes non homogènes]
  Soit $(X_n)_{n\in\dN}$ une suite de v.a.r. i.i.d. dont la loi commune a pour
  fonction de répartition $F$ que l'on supposera continue. Les temps de record
  $R_n$ sont les v.a.r. définies par $R_0=0$ et $$
  R_{n+1} := \inf\BRA{k>R_n,\
    X_k\geq X_{R_n}}. $$
  Montrer que les suites $(R_n)_{n\in\dN}$ et
  $(X_{R_n})_{n\in\dN}$ sont des chaînes de Markov non homogènes. Écrire un
  programme permettant de les simuler pour différentes fonctions de
  répartition $F$. Cf. \cite[ex. VIII.7.4. p. 236]{barbe-ledoux}.
\end{exo}

\begin{exo}[Modèle d'Ehrenfest et paradoxe\footnote{Ce modèle a été proposé
    par le physicien Ehrenfest pour modéliser la diffusion des particules d'un
    gaz dans une enceinte constituée par deux récipients qui communiquent :
    par exemple l'air ambiant et l'intérieur d'un pneu de voiture percée. Le
    paradoxe vient de la périodicité de la chaîne, qui permet au pneu de se
    regonfler ! En effet, il est possible de passer de l'état d'équilibre
    parfait à un état très déséquilibré. Ce paradoxe, qui met en contradiction
    la théorie cinétique des gaz avec la thermodynamique, se résoud en tenant
    compte du temps, si cher à la thermodynamique. Le temps nécessaire au
    passage de l'état d'équilibre parfait à un déséquilibre fort est
    colossal.} des récipients du même nom] On considère deux urnes contenant
  respectivement $k$ et $d-k$ boules avec $k\leq d$. À chaque étape, on
  choisit aléatoirement l'une des $d$ boules et on la change d'urne. Soit
  $X_n$ le nombre de boules dans la première urne à l'étape $n$. Si $X_n=j$,
  alors on déplace une boule de la première urne vers la seconde avec
  probabilité $j/d$ et réciproquement avec la probabilité $1-j/d$. Ainsi
  définie, la suite $(X_n)_{n\in\dN}$ est une chaîne de Markov homogène
  d'espace d'états $\dE:=\{0,\ldots,d\}$ qui décrit l'évolution du paramètre
  d'une loi de Bernoulli $\cB(X_n/d)$. Déterminez la matrice de transition,
  les états récurents. Montrer que la chaînes est RI mais pas RIA et que sa
  période vaut $2$. Ainsi la LGN s'applique mais pas la chaîne de converge
  pas vers l'équilibre indépendamment de son état initial.
  Vérifier que la loi binomiale $\cB(d,1/2)$ est invariante\footnote{Noter que
    $\mu:=\cB(d,1/2)$ est symétrique : $\mu(i) \bP_{i,j} = \mu(j) \bP_{j,i}$
    pour tout $i$ et $j$, ce qui est suffisant pour assurer son invariance
    (pourquoi ?).}.
  
  Montrer qu'il existe deux constantes $a,b \in \dR$ telles que, $\forall x
  \in \dE$, $\sum_{y \in \dE} y \bP(x,y)=ax+b$. En déduire que
  $(\dE(X_n|X_0))_{n\in\dN}$ converge vers $d/2$. Écrire un programme
  permettant de générer une chaîne d'Ehrenfest et d'illustrer ces résultats de
  convergence. On trouvera dans \cite{cottrell-duhamel} des exercices corrigés
  dans le même esprit (ex. 9.13 par exemple).
\end{exo}

\begin{exo}[Retournements de veste aléatoires] 
  Soit $(\veps_n)_{n\in\dN^*}$ une suite de v.a. i.i.d. de loi de Bernoulli
  symétrique $\cB(p)=(1-p)\,\de_{-1}+p\,\de_{+1}$ avec $p\in[0,1]$. Soit
  $(X_n)_{n\in\dN}$ la suite définie par 
  \begin{equation*}
    X_0:=+1,\quad\text{et pour tout
    }n\geq 1,\ X_n:=\prod_{k=1}^n \veps_k. 
  \end{equation*}
  Montrer que $(X_n)_{n\in\dN}$ une chaîne de Markov homogène d'espace d'états
  $\dE=\BRA{-1,+1}$. Que pourrait modéliser une telle chaîne, somme toute
  élémentaire ? Calculer sa matrice de transition $\bP$. Déterminer, suivant
  les valeurs de $p$, sa mesure invariante $\mu$. \'Ecrire un programme
  permettant de simuler cette chaîne de Markov et de vérifier la convergence
  en loi de $(X_n)_{n\in\dN}$ vers $\mu$.
\end{exo}

\begin{exo}[Modèle de Wright-Fisher en génétique pour la reproduction haploïde]
  Considérons un gène et deux de ses allèles A et B. Considérons également une
  population de taille fixe $N\in\dN^*$ dans laquelle chaque individu ne
  possède qu'une seule copie de ce gène, sous sa forme A oubien sous sa forme
  B. Soit $X_n$ le nombre d'individus de la $n$-ième génération qui possèdent
  l'allèle A. Le passage d'une génération à une autre consiste à tirer au sort
  (avec remise) les $N$ individus de la nouvelle génération parmis ceux de la
  génération précédente (qui meurent tous, donc). Le nombre de A dans la
  $(n+1)$-ième génération suit donc asymptotiquement (sur $N$) une loi
  binomiale de taille $N$ et de paramètre $X_n/N$. Cette modélisation
  correspond à la définition de la chaîne de Markov de Wright-Fisher
  $(X_n)_{n\in\dN}$ d'espace d'états fini $\dE=\{0,1,\ldots,N\}$
  vérifiant\footnote{On remarquera au passage que le présent $X_n$
    n'intervient pour la définition du futur $X_{n+1}$ qu'à travers le
    paramètre $X_n/N\in[0,1]$ de la loi de Bernoulli $\cB(X_n/N)$. La loi
    binomiale $\cB(N,X_n/N)$ qui apparaît dans la définition de la transition
    n'est que le nombre de gains lors de $N$ lancés à un jeu de pile ou face
    avec probabilité de gain $X_N/N$. Ainsi, la chaîne décrit l'évolution
    d'une loi de Bernoulli, et plus généralement, les version à $m\geq2$
    allèles de la chaîne de Wright-Fisher décrivent l'évolution d'une loi
    discrète à $m$ atomes. Il faut alors remplacer la loi binomiale par une
    loi multinomiale de taille $N$, qui correspond au jeu de pile ou face avec
    un dés à $m$ faces en quelque sorte\ldots L'image des $N$ tirages avec
    remise dans une urne contenant une infinité de boules colorées de $m$
    couleurs différentes est sans doute plus adaptée, l'infinité des boules
    permettant une loi discrète quelconque sur leur couleur. Enfin, on
    remarquera que $(N^{-1}\,X_n)_{n\in\dN}$ est une chaîne de Markov à valeur
    dans $\dE_N:=N^{-1}\,\BRA{0,\ldots,N}\subset[0,1]$, et que $\dE_N$ est une
    discrétisation uniforme de l'intervalle $[0,1]$.} $$
  \cL(\COND{X_{n+1}}{X_n}) = \cB\PAR{N,\frac{X_n}{N}}, $$
  où $\cB(N,p):=\sum_{K=0}^{N}p^K(1-p)^{N-K}C_N^K\de_K$ est la
  loi binomiale de taille $N$ et de paramètre $p$.
  La matrice de transition
  $\bP$ de la chaîne $(X_n)_{n\in\dN}$ est donc donnée par $$
  \bP_{i,j} :=
  \dP(\COND{X_{n+1}=j}{X_n=i}) %
  = C_N^j\PAR{\frac{i}{N}}^j\PAR{1-\frac{i}{N}}^{N-j}, $$
  puisque
  $\bP_{i,\cdot} = \cB(N,\frac{i}{N})$.
  \begin{enumerate}
  \item Tracer le graphe de la chaîne. Montrer que $0$ et $N$ sont des états
    absorbants (donc récurrents) et que les autres états sont tous
    transitoires. Montrer que presque-sûrement, la chaîne est capturée par
    l'un des deux états absorbants au bout d'un temps aléatoire fini;
  \item \'Ecrire un programme de simulation des trajectoires de la chaîne de
    Markov $(X_n)_{n\in\dN}$. On pourra utiliser
    \texttt{sum(rand(1,N)<X(n)/N)} à la place de \texttt{rbinom} pour éviter
    les problèmes numériques dus au fait que $\cB(N,0)=\de_0$ et
    $\cB(N,N)=\de_N$. Constater la capture par les points absorbants;
  \item Montrer que $(X_n)_{n\in\dN}$ est une martingale bornée. En déduire
    qu'il existe une variable aléatoire $X_\infty$ telle que $(X_n)_{n\in\dN}$
    converge presque-sûrement vers $X_\infty$. Montrer que $X_\infty$ prend
    ses valeurs dans $\{0,N\}$. Montrez que sur l'évènement $\{X_0=i\}$, la
    probabilité d'être absorbé par le gène $A$ est $i/N$. Illustrer cela par
    un graphique obtenu par une simulation de la capture par les états
    absorbants en fonction du point de départ;
  \item Utilisez le TLC de Moivre - Laplace pour obtenir des intervalles de
    confiance dans la simulation précédente;
  \item Soit $P_1,\ldots,P_N$ des v.a. i.i.d. de loi de Poisson $\la>0$.
    Montrez que $\cL(P_1,\ldots,P_N\,\vert\,P_1+\cdots+P_N=N)$ est une loi
    multinomiale de taille $N$ et de paramètre
    $(\frac{1}{N},\ldots,\frac{1}{N})$, cf. \cite[ex. 6.1
    2.a]{cottrell-duhamel}. En déduire que pour tout $i\in\{0,\ldots,N\}$,
    $\cL(P_1+\cdots+P_i\,\vert\,P_1+\cdots+P_N=N)=\cB(N,\frac{i}{N})$. En
    déduire une interpretation Poissonienne du mécanisme de transition de la
    chaîne de Wright-Fisher.
  \end{enumerate}                            
  Afin de rendre la chaîne de Wright-Fisher RIA, on introduit la possibilité
  de mutations. Le passage de la génération $n$ à $n+1$ se fait d'abord en
  provoquant de façon indépendante pour chacun des $N$ individus de la
  génération $n$ une mutation de $A$ à $B$ avec probabilité $p_B$ et une
  mutation de $B$ à $A$ avec probabilité $p_A$. Ensuite, on procède comme pour
  le cas sans mutation pour obtenir les $N$ individus de la génération $n+1$.
  La nouvelle chaîne $(Y_n)_{n\in\dN}$ est donnée par
  \begin{equation*}
    \cL(\COND{Y_{n+1}}{Y_n}) %
    = \cB\PAR{N,q_B\,\frac{Y_n}{N}+p_A\,\PAR{1-\frac{Y_n}{N}}} %
    = \cB\PAR{N,p_A+(q_B-p_A)\,\frac{Y_n}{N}},
  \end{equation*}
  et sa matrice de transition $\bQ$ est donc donnée par
  \begin{equation*}
    \bQ_{i,j} := \dP(\COND{Y_{n+1}=j}{Y_n=i}) %
    = \,C_N^j\PAR{p_A+(q_B-p_A)\,\frac{i}{N}}^j %
    \PAR{q_A-(q_B-p_A)\,\frac{i}{N}}^{N-j}. 
  \end{equation*}
  Cette nouvelle chaîne, qui apparaît comme une version mélangée de la
  précédente, a le bon goût de s'échapper des pièges du «tout A» ou «tout B»
  grâce à la mutation. Dans la suite, on prendra $p:=p_A=p_B$ pour simplifier.
  \begin{enumerate}
  \item Montrer que la chaîne $(Y_n)_{n\in\dN}$ est RIA lorsque $0<p<1$. Que
    se passe-t-il lorsque $p$ est dans $\{0,1\}$ ?;
  \item Lorsque $0<p<1$, montrer que $(X_n)_{n\in\dN}$ n'est pas une
    sous-martingale, ni une sur-martingale;
  \item En utilisant le théorème de convergence vers l'équilibre
    \ref{th:cv-erg} ou la loi des
    grands nombres \ref{th:cv-ri}, écrire un programme fournissant un
    histogramme approximatif de la mesure invariante de $(Y_n)_{n\in\dN}$,
    pour différentes valeurs de $N$ et $p$;
  \item Comment pourrait-on estimer le paramètre de mutation $p$ à partir d'un
    échantillon i.i.d. dont la loi commune est la loi invariante de
    $(Y_n)_{n\in\dN}$ ?
    % FIXME: ajouter l'estimation de $p$ par maximum de vraisemblance.
    % FIXME: algo EM lorsque $Y$ est construite cond. à partir de$(J)$
    % FIXME: où $J\in\{0,1\}^N$ représente la présence ou non de l'allèle A.
    % FIXME: la loi du couple (Y,J) avec $J$ non observé est parfait pour 
    % FIXME: faire du ML via EM : 
    % FIXME: $\cL(\COND{Y}{J=(c_1,\ldots,c_N)}) = en fonction de $|J|$ et $N$,
    % FIXME: où $|J|:=c_1+\cdots+c_N$.
  \item Donner un sens à la chaîne de Markov $(Z_n)_{n\in\dN}$ définie pour
    $p\in[0,1]$ par 
    \begin{equation*}
    \cL(\COND{Z_{n+1}}{Z_n}) %
    = p\,\cB\PAR{N,\frac{Z_n}{N}}+(1-p)\,\cB\PAR{N,1-\frac{Z_n}{N}}.
    \end{equation*}
  \end{enumerate}  
  On pourra par exemple consulter \cite[Sec. 5.4]{istas} et \cite[p.
  21--26]{ruget}.
\end{exo}

\begin{exo} On considère la chaîne de Markov $(X_n)_{n\in\dN}$
  homogène d'espace d'états $\dE:=\BRA{1,2,3,4}$ et de matrice de transition
  $$
  \bP:=\left(\begin{array}{cccc}
      0 & 1 & 0 & 0 \\
      \frac{1}{2} & 0 & \frac{1}{4} &\frac{1}{4} \\
      \frac{1}{2}& \frac{1}{2} & 0 & 0\\
      0 & 0 & 1 & 0
    \end{array}\right).
  $$
  Montrer que $(X_n)_{n\in\dN}$ est RI. Déterminer sa loi invariante $\mu$.
  À partir de la LGN, montrer que $$
  \frac{1}{n}\sum_{k=0}^{n}X_k\limPS{n}=a
  \text{\quad et \quad} \frac{1}{n}\sum_{k=0}^{n}X_k^2\limPS{n}=b $$
  avec $a$
  et $b$ à déterminer. \'Ecrire un programme permettant de simuler cette
  chaîne de Markov et de vérifier ces résultats de convergence.
\end{exo}

\begin{exo}[File d'attente M/M/1 à temps discret]
  Considérons un serveur informatique répondant à des requettes effectuées par
  des programmes clients. On suppose que le serveur ne peut répondre qu'à une
  seule requette à la fois, et que les requettes des programmes sont rangées
  en une file d'attente en attendant d'être traitées par le serveur. Les temps
  séparant les arrivées des nouvelles requettes des clients dans la file
  d'attente sont i.i.d. et suivent une loi géométrique $\cG(p_c)$. Les temps
  de traitement des requettes par le serveur sont des v.a. i.i.d. de loi
  géométrique $\cG(p_s)$, indépendantes des précédentes liées aux clients. On
  s'intéresse à la variable aléatoire $X_n$ qui représente le nombre de
  requettes dans la file à l'étape $n$, y compris l'éventuelle requette en
  cours de traitement par le serveur. Montrez que $(X_n)_{n\in\dN}$ est une
  chaîne de Markov à espace d'états infini $\dE=\dN$, dont on déterminera la
  matrice (infinie) de transition et les propriétés asymptotiques en fonction
  du signe de $1-p_c/p_s$. Si l'on réinterprète ce modèle de file d'attente à
  temps discret comme un modèle de marche aléatoire aux plus proches voisins
  sur $\dN$, à quoi correspond la chaîne de Markov $(X_n)_{n\in\dN}$ ? Si l'on
  réinterprète à son tour ce modèle de marche aléatoire en terme de problème
  de ruine du joueur, à quoi correspond la chaîne de Markov ? Quid du premier
  temps d'annulation de la chaîne lorsqu'elle ne part pas de $0$ ? On trouvera
  dans \cite{cottrell-duhamel} des exercices corrigés dans le même esprit (ex.
  9.8, 9.10, 9.11).
\end{exo}

%\begin{exo}[Image par une fonction d'une chaîne de Markov et théorème de
%  Dynkin]
%FIXME: à faire.
%\end{exo}

%\begin{exo}[Méthode de simulation «Monte Carlo via Chaînes de Markov» (MCMC)]
%FIXME: à faire.
%\end{exo}

%\begin{exo}[Chaîne de Markov «Move To Front» sur le
%  groupe symétrique en informatique] FIXME: à faire.
%\end{exo}

%\begin{exo}[Fluctuation du flux de pollen sauvage]
%FIXME: à faire. Cf. section 5.7.2 du livre de J. Istas.
%\end{exo}

% {\tiny
\bibliographystyle{smfplain}
\bibliography{biblio}
% }

\end{document}