\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{2004}
\MEL{chafai@math.ups-tlse.fr}
\AUTEUR{B. Bercu \& D. Chafaï}
\WEB{http://www.lsp.ups-tlse.fr/Chafai/agregation.html}
\DATE{Mars 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 brefs rappels introductifs}
%

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$,
$$
\cL(\COND{X_{n+1}}{X_0,\ldots,X_n}) = \cL(\COND{X_{n+1}}{X_n}).
$$
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}$:
  $$
  \cL\PAR{\COND{\PAR{X_{\tau+n}}_{n\in\dN}}{\cF_\tau}} %
  = \cL\PAR{\COND{(X_n)_{n\in\dN}}{X_0=x}}.
  $$
  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$, 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 loi
    uniforme 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_y^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
$$
\bG(x,y):=\sum_{n=1}^{\infty} \bP^n_{x,y} = \bE(\COND{N_y}{X_0=x}),
$$
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 lorsque pour tout $y\in\dE$,
$x\to y$ entraîne $y\to x$.  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 appelé parfois \emph{graphe de
  Markov}. 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})$. 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. 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\dE$,
$\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. L'une de ces classes est constituée de
  tous les états récurrent positifs, et les classes singletons correspondent
  aux états absorbants.
\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 peut le
montrer un exemple de marche aléatoire.

\subsection{Loi forte des Grands Nombres \& théorème ergodique}

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}[Chacon-Ornstein : LGN forte pour chaînes RI]\label{th:cv-ri}
  Si $(X_n)_{n\in\dN}$ une chaîne de Markov RI, alors 
  \begin{itemize}
  \item La mesure invariante $\mu$ existe, est unique à une multiplication par
    une constante positive près, et charge tous les états;
  \item Pour tout couple d'états $(x,y)\in\dE\times\dE$, on a:
    $$
    \bE(\COND{N_{x,y}}{X_0=x}) = \frac{\mu(y)}{\mu(x)},
    $$
    où $N_{x,y}:=\sum_{k=0}^{\tau_x^1-1}\rI_\BRA{X_k=y}$ désigne le nombre de
    passages en $y\in\dE$ avant d'atteindre $x\in\dE$;
  \item Pour tout couple de fonctions $f,g:\dE\to\dR$ toutes deux
    $\mu$-intégrables ou toutes deux positives, on a:
    $$
    \frac{f(X_1) + \cdots + f(X_n)}{g(X_1)+\cdots+g(X_n)} %
        \limPS{n} \frac{\int_\dE\!f\,d\mu}{\int_\dE\!g\,d\mu}.
    $$
    En particulier, pour $(f,g)=(\de_x,\de_y)$ où $(x,y)\in\dE\times\dE$ sont
    deux états fixés, on a:
    $$
    \frac{\CARD\{0\leq k\leq n,\text{ tels que }X_k =x\}} %
    {\CARD\{0\leq k\leq n,\text{ tels que }X_k =y\}} %
    \limPS{n}\frac{\mu(x)}{\mu(y)};
    $$
   \item Si $\mu(\dE)<+\infty$ (c'est toujours le cas si $\dE$ fini), il 
    existe une loi de probabilité stationnaire unique obtenue en renormalisant
    $\mu$. On a alors pour tout $x\in\dE$, 
    $\bE(\COND{\tau^1_x}{X_0=x})=1/\mu(x)$;
   \item Si $\mu(\dE)=+\infty$, on a pour tout $x\in\dE$, 
   $\bE(\tau^1_x)=+\infty$.
  \end{itemize}
\end{thm}

\begin{rem}[Les chausses trappes du théorème \ref{th:cv-ri}]
  On prendra garde au fait que la fonction constante $g\equiv1$ dans le
  théorème \ref{th:cv-ri} donne bien $n^{-1}\,(f(X_1)+\cdots+f(X_n))$ mais que
  la quantité $\int_\dE g\,d\mu$ n'est alors finie que lorsque $\mu(\dE)$ est
  fini.  Ceci explique les formulations sous forme de fractions dans le
  théorème \ref{th:cv-ri}, qui permettent d'énoncer le résultat dans un cadre
  général.  Lorsque la mesure invariante $\mu$ est une loi de probabilité, 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
  particulier, la fraction de temps passée sur un état (temps d'occupation)
  «converge» vers la masse relative de ce point pour la mesure invariante. En
  d'autre termes, la mesure empirique $\dP_n:=n^{-1}\,(X_1+\cdots+X_n)$
  converge presque sûrement en loi vers $\mu$ lorsque $n$ tend vers l'infini.
\end{rem}

\begin{cor}[Classificassion des chaînes irréductibles]
  Pour toute chaîne irréductible (i.e. qui ne possède qu'une seule classe de
  récurrence), les états sont soit tous transitoires, soit tous récurrents
  nuls, soit tous récurrents positifs. De plus, la mesure invariante ne peut
  être normalisée en une loi de probabilité que dans ce dernier cas seulement.
\end{cor}

L'éventuelle périodicité de certains états empèche, pour un 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}. Reppelons que pour une
chaîne RI, tous les états ont même période car il n'y a qu'une seule classe de
récurrence. 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}[Ergodicité 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 mesure 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 sont état d'«é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, on pourra consulter les livres de Barbe
  \& Ledoux, Cottrell \& al, Revuz, Norris, Foata \& Fush, Mazliak \& al,
  Dacunha-Castelle \& Duflo, Bouleau, etc.
\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.  Cottrell \& al ex. 9.12 p. 286.
\end{exo}

\begin{exo}
  Écrire une fonction Matlab \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.
  Barbe \& Ledoux ex.  VIII.7.4. p236.
\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. Cottrell \& al ex. 8.8 p. 247, et ex. 9.16 p. 296.
\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. Barbe \& Ledoux
  ex.  VIII.7.4.  p. 236.
\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'une roue de voiture pércée. Le
    paradoxe vient de la périodicité de la chaîne, qui permet à la roue 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 $n$ 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 le théorème ergodique.
  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.}.
  
  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$.  Créer un code Matlab
  permettant de générer une chaîne d'Ehrenfest et d'illustrer ces résultats de
  convergence.  On trouvera dans Cottrell \& al. 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 
  $$
  X_0:=+1,\quad\text{et  pour tout }n\geq 1,\ 
  X_n:=\prod_{k=1}^n \veps_k.
  $$
  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$.  Créer un code
  Matlab 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)$ est la loi binomiale de taille $N$ et de paramètre $p$
  définie par $\cB(N,p):=\sum_{k=0}^N p^k(1-p)^{N-k}\,\de_k$.  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,i/N)$. 
  On rappelle que $\cB(N,0)=\de_0$ et que $\cB(N,N)=\de_N$, ce qui peut
  provoquer des problèmes numériques avec \texttt{rbinom}.
  Montrer que $0$ et $N$ sont des
  états absorbants (donc récurrents) et que les autres états sont tous
  transitoires. Écrire un programme permettant de simuler une trajectoire de
  la chaîne en utilisant la fonction Stixbox \texttt{rbinom}.  Illustrer la
  capture de la chaîne par les points absorbants en fonction du point de
  départ.  Lorsque $N=2M$, évaluer les probabilités d'absorbtion par les
  points $0$ et $N$. Traiter les cas $X_0<M$, $X_0>M$ et $X_0=M$. Confronter
  les prédictions théoriques à des simulations.
                                  
  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
  $$
  \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}},
  $$
  et sa matrice de transition $\bQ$ est donc donnée par
  $$
  \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}.
  $$
  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.  Montrer qu'elle est bien RIA lorsque $p_A$ et $p_B$
  sont dans $]0,1[$. Si $p_A=p_B=0$, alors $(Y_n)_{n\in\dN}=(Y_n)_{n\in\dN}$,
  plus généralement, que se passe-t-il lorsque $p_A$ et $p_B$ sont dans
  $\{0,1\}$ ?  En utilisant le théorème ergodique \ref{th:cv-erg}, estimer par
  la simulation sa mesure invariante dans le cas RIA pour différentes valeurs
  de $N$, $p_A$ et $p_B$. Dans le cas simple où $p:=p_A=p_B$, 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 conditionnellement à 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$.

  Donner un sens à la chaîne de Markov $(Z_n)_{n\in\dN}$ définie
  pour $p\in[0,1]$ par
  $$
  \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}},
  $$
  de matrice de transition $\bR$ donnée par 
  $$
  \bR_{i,j} %
     := C_N^j\,\PAR{\frac{i}{N}}^j\,\PAR{1-\frac{i}{N}}^j\, %
      \PAR{p\,\PAR{1-\frac{i}{N}}^{N-2j} %
       + (1-p)\,\PAR{\frac{i}{N}}^{N-2j}}.
  $$
  Pour les aspects théoriques, on pourra par exemple se reporter à la section
  5.4 du livre intitulé
  «Introduction aux modélisations mathématiques pour les sciences du 
  vivant», par J. Istas, collection «Mathématiques et Applications», n°34, 
  éditions Springer, ISBN 3-540-67254-0.
  %FIXME: mettre ici la ref du livre «... ADN ...».
\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. Créer un code Matlab 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 Cottrell \& al. 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}



\end{document}







