\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\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 $a1$. 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_0M$ 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}