1.9. Chaines de Markov à temps discret

On commence par une définition d’une chaine de Markov sur un espace générale \(E\) mesurable. Cette définition met l’accent sur le côté dynamique d’une chaine de Markov vue comme une suite récurrente aléatoire.

Definition 1.5 (chaine de Markov simulable)

Une chaine de Markov (dite simulable) sur \(E\) est une suite \((X_n)_{n \ge 0}\) de variables aléatoires à valeurs dans \(E\) telle que

\[\begin{equation*} \forall n \ge 0, \quad X_{n+1} = \Phi(n, X_n, \xi_{n+1}), \end{equation*}\]

où

• \((\xi_n)_{n \ge 1}\) est une suite de variables aléatoires indépendantes à valeurs dans \(V\) (ensemble mesurable), indépendante de \(X_0\),

• \(\Phi: \mathbf{N} \times E \times V\) est une application (déterministe) mesurable à valeurs dans \(E\).

Remark 1.2

• L’espace \(E\) s’appelle l’espace des états de la chaine de Markov \((X_n)_{n \ge 0}\)

• La suite \((\xi_n)_{n \ge 1}\) s’appelle la suite des innovations et l’ensemble \(V\) est l’espace des innovations.

• Si \(\Phi\) ne dépend pas de l’itération \(n\) et que \((\xi_n)_{n \ge 1}\) est i.i.d., on dit que la chaine est homogène.

• Il est important d’avoir indépendance entre les \(\xi_{k+1}\) et le passé de la chaine \((X_0, \dots, X_k)\).

Example 1.6 (la marche aléatoire symétrique sur \(\mathbf{Z}\))

L’espace d’état est \(\mathbf{N}\), l’espace des innovations est \(V = \{-1, 1\}\), la condition initiale est \(X_0 = 0\) (ou encore \(X_0 \sim \delta_0\) i.e. la loi de \(X_0\) est la dirac en \(0\)) et les innovations sont \((\xi_n)_{n \ge 1}\) une suite i.i.d. telle que \(\mathbf{P}\big(\xi_1 = 1\big) = \mathbf{P}\big(\xi_1 = -1\big) = \frac{1}{2}\). La dynamique est donnée par \(\Phi(x, \xi) = x + \xi\) c’est à dire

\[\begin{equation*} X_{n+1} = X_n + \xi_{n+1}, \quad X_0 = 0. \end{equation*}\]

Example 1.7 (une marche aléatoire sur \(\mathbf{R}\))

L’espace d’état est \(\mathbf{R}\), l’espace des innovations est \(V = \mathbf{R}\), la condition initiale est \(X_0 = 0\) et les innovations sont \((\xi_n)_{n \ge 1}\) une suite i.i.d. telle que \(\xi_1 \sim \mathcal{N}(0, h)\) où \(h > 0\) est un paramètre fixé. La dynamique est la même que l’exemple précédant

\[\begin{equation*} X_{n+1} = X_n + \xi_{n+1}, \quad X_0 = 0. \end{equation*}\]

Dans ce cas la loi de \((X_1, \dots, X_n)\) est calculable. C’est un vecteur Gaussien centré de matrice de covariance \(\operatorname{cov}(X_i, X_j) = \min(ih, jh)\).
Il s’agit d’un mouvement Brownien standard aux instants \(t_k = k h\), \(k =1, \dots, n\).

1.9.1. Chaine de Markov sur un espace d’états discret

Soit \(E\) un espace d’états discret (fini ou débombrable). On considère une suite de variables aléatoires \((X_n)_{n \ge 0}\) à valeurs dans \(E\). La loi \(\pi_n\) de \(X_n\) est donnée pour tout borélien \(A\) par

\[\begin{equation*} \pi_n(A) = \mathbf{P} \big(X_n \in A\big) = \sum_{x \in A} \pi_n(x) \quad \text{avec} \quad \pi_n(x) = \mathbf{P} \big(X_n = x\big). \end{equation*}\]

La loi \(\pi_n\) est la loi marginale (en \(n\)) de la suite (ou processus) \((X_n)_{n \ge 0}\). Il ne faut pas la confondre avec la loi du processus qui s’obtient à partir des lois marginales fini-multidimensionnelles de \((X_n)_{n \ge 1}\) (hors programme dans ce cours).

On rappelle la définition classique d’une chaine de Markov sur \(E\) en commencant par la notion de matrice stochastique.

Definition 1.6

Une matrice \(P= \big( P(x, y)_{x, y \in E} \big)\) est une matrice stochastique (ou matrice markovienne ou matrice de transition) sur \(E\) si

\[\begin{equation*} P(x, y) \ge 0 \quad \text{et} \quad \sum_{y \in E} P(x, y) = 1. \end{equation*}\]

Une matrice stochastique a pour chaque vecteur ligne \(P(x, .) = \big( P(x, y) \big)_{y \in E}\) une loi de probabilité sur \(E\).

Definition 1.7

Une suite \((X_n)_{n \ge 0}\) est une chaine de Markov de matrice de transition \(P\) et de loi initiale \(\pi_0\) si \(\forall n \ge 0\), \(\forall x_0, \dots, x_n \in E\),

(1.8)\[ \mathbf{P}\big( X_0 = x_0, \dots, X_n = x_n \big) = \pi_0(x_0) P(x_0, x_1) \dots P(x_{n-1}, x_n),\]

ou de façon équivalente (par récurrence)

\[ \mathbf{P}\big( X_0 = x_0, \dots, X_n = x_n \big) = \mathbf{P} \big(X_0 = x_0, \dots, X_{n-1} = x_{n-1} \big) P(x_{n-1}, x_n).\]

On déduit immédiatement de cette définition que

()\[\begin{equation} \forall n \ge 0, \quad \forall x, y \in E, \quad \mathbf{P} \big( X_{n+1} = y | X_n = x \big) = P(x, y). \end{equation}\]

1.9.2. Propriétés algébriques

Si \(E\) est dénombrable on considère les fonctions \(f:E \to \mathbf{R}\) comme des vecteurs colonnes (de taille finie ou infinie) et les mesures \(\mu\) sur \(E\) comme des vecteurs lignes. Alors \(Pf\) est une fonction de \(E \to \mathbf{R}\) définie par

()\[\begin{equation} \forall x \in E, \quad Pf(x) = \sum_{y \in E} f(y) P(x, y) \end{equation}\]

et \(\mu P\) est une mesure sur \(E\) définie par

()\[\begin{equation} \forall x \in E, \quad \mu P(x) = \sum_{z \in E} \mu(z) P(z, x) \end{equation}\]

D’autre part le produit de 2 matrices stochastiques \(P\) et \(Q\) est donné par

()\[\begin{equation} \forall x, y \in E, \quad PQ(x, y) = \sum_{z \in E} P(x, z) Q(z, y) \end{equation}\]

et on pose \(P^0 = \operatorname{Id}\) et \(P^n = P^{n-1} P = P P^{n-1}\).

1.9.3. Interprétation probabiliste

Il est important de bien interpréter ces relations algébriques avec le formalisme probabiliste. En effet comme \(P(x, .)\) est la loi conditionnelle de \(X_{n+1}|X_n = x\) (pour tout \(n \ge 0\)) on a

\[\begin{align*} \forall x \in E, \quad Pf(x) &= \mathbf{E} \big[ f(X_1) | X_0 = x \big] \\ \mu P(x) & = \mathbf{P} \big( X_1 = x|X_0 \sim \mu \big) = \sum_{z \in E} \mathbf{P} \big( X_1 = x|X_0 = z \big) \mu(z). \end{align*}\]

De plus si \(X_0 \sim \mu\) alors la loi de \(X_n\) est donnée par \(\mu P^n\). En effet

\[\begin{equation*} \mathbf{P} \big(X_0 = x, X_n = y\big) = \sum_{x_1, \dots, x_{n-1} \in E} \mathbf{P} \big(X_0 = x, X_1 = x_1, \dots, X_{n-1} = x_{n-1}, X_n = y \big) \end{equation*}\]

et d’après (1.8) on a

\[\begin{align*} \mathbf{P} \big(X_0 = x, X_n = y \big) &= \sum_{x_1, \dots, x_{n-1} \in E} \mu(x) P(x, x_1) \dots P(x_{n-1}, y), \\ & = \mu(x) P^n(x, y). \end{align*}\]

On en déduit que \(\mathbf{P} \big(X_n = y|X_0 = x\big) = P^n(x, y)\) et par suite que \(\mathbf{P} \big(X_n = y| X_0 \sim \mu\big) = \mu P^n(y)\).

Proposition 1.8

Toute chaine de Markov \((X_n)_{n \ge 0}\) à valeurs dans \(E\) dénombrable (au sens de la définition Definition 1.7) est simulable au sens de la définition Definition 1.5.

Proof. Soit \((X_n)_{n \ge 0}\) une chaine de Markov de loi initiale \(\pi_0\) et de matrice de transition \(P\) sur \(E\). On dénombre l’espace d’états et on le note \(E = \big\{x_j, j \ge 0\big\}\). Le but est de construire \(X_{n+1}\) à partir de \(X_n\) et d’une variable aléatoire auxiliaire \(\xi_{n+1}\) indépendante du passé. On connait la loi conditionnelle de \(X_{n+1}|X_n = x\) car cette loi est donnée par \(P(x, .)\) (\(x\)–ème ligne de la matrice \(P\)). Conditionnellement à l’événement \(\{X_n = x\}\) la variable aléatoire \(X_{n+1}\) est donc de fonction de répartition

()\[\begin{equation} F_{X_{n+1}|X_n = x}(y) = \sum_{j \ge 0} \sum_{l=0}^{j} P(x, x_l) \mathbf{1}_{x_{j} \le y < x_{j+1}} \end{equation}\]

et l’inverse généralisée s’écrit

()\[\begin{equation} \forall u \in [0,1], \quad \Phi(x, u) = \sum_{j \ge 0} x_j \mathbf{1}_{\sum_{l=0}^{j-1} P(x, x_l)< u \le \sum_{l=0}^j P(x, x_l)}. \end{equation}\]

Pour \(U \sim \mathcal{U}\big(]0,1[\big)\) on a donc \(\Phi(x, U) \sim X_{n+1}|X_n = x\). La chaine de Markov \((X_n)_{n \ge 0}\) de loi initiale \(\pi_0\) et de matrice de transition \(P\) peut donc s’écrire sous la forme itérative

(1.15)\[\begin{split} \begin{split} X_0 &\sim \pi_0 \\ \forall n \ge 0, \quad X_{n+1} & = \Phi(X_n, U_{n+1}). \end{split}\end{split}\]

On vérifie que si \((X_n)_{n \ge 0}\) satisfait (1.15) alors \(\forall x_0, \dots, x_n \in E\),

\[\begin{align*} \mathbf{P} \big(X_0 = x_0, X_1 = x_1, \dots, X_n = x_n \big) = \mathbf{P} \big(X_0 = x_0 \big) \mathbf{P} \big(\Phi(x_0, U_1) = x_1 \big) \dots \mathbf{P} \big( \Phi(x_{n-1}, U_n) = x_n \big), \end{align*}\]

et \(\mathbf{P} \big(\Phi(x_{k-1}, U_1) = x_k\big) = P(x_{k-1}, x_k)\) pour tout \(k \ge 1\).

Ce résultat se généralise à \(E = \mathbf{R}^d\) par exemple.

See also

Pour en savoir plus sur les chaines de Markov sur un espace d’état dénombrable, vous pouvez consulter les ouvrages suivants (avec exercices corrigés): [Graham, 2008], [Cottrell et al., 2005] ou [Mazliak et al., 1998].

[CGCDM05]

Marie Cottrell, V Genon-Catalot, C Duhamel, and T Meyre. Exercices de probabilités. Cassini, 2005.

[Gra08]

Carl Graham. Chaînes de Markov. Dunod, Paris, 2008.

[MPB98]

Laurent Mazliak, Pierre Priouret, and Paolo Baldi. Martingales et chaînes de Markov. Hermann Paris, 1998.