Théorème 1Chaînes de Markov

Construction d'une chaîne à partir de variables uniformes ⋆

⋆ Axiome du choix

Le point (iii) hérite du choix dénombrable dont dépend la mesure de Lebesgue, par la suite de variables uniformes indépendantes du nœud Suites indépendantes ; c'est le seul usage du choix dans ce chapitre, signalé ici une fois. Les points (i) et (ii) n'en font aucun : l'énumération de $I$ est fixée une fois, et les constructions sont explicites. Les fiches suivantes énoncent des propriétés de chaînes données ; plusieurs, comme la récurrence, la mesure $\gamma_x$ ou la formule $\pi(x) = 1/E_x[T_x]$ , ne portent que sur $Q$ , mais s'écrivent avec $P_x$ , qui suppose une chaîne issue de $x$ . Une chaîne irréductible donnée en fournit une pour chaque état sans aucun choix (Propriété de Markov, (ii)) ; à défaut, (iii) en donne une, et ces énoncés héritent alors de ce ⋆. Le couplage du nœud Convergence vers l'équilibre, points (i) et (ii), reste sans choix : il se fait sur un ensemble fini, par (ii).

Soient $\mu$ une probabilité et $Q$ une matrice de transition sur $I$ , dont les états sont énumérés $y_0, y_1, \dots$ Pour $x \in I$ et $u$ réel, on pose $f(x, u) = y_k$ , où $k$ est le plus petit indice tel que $u \leqslant Q(x, y_0) + \cdots + Q(x, y_k),$ si $0 < u \leqslant 1$ et si un tel indice existe, et $f(x, u) = y_0$ sinon. On définit de même $g(u)$ à partir des $\mu(y_k)$ .

Énoncé

(i) Soient, sur un espace probabilisé quelconque, $U_0, U_1, \dots$ des variables indépendantes de loi uniforme sur $[0, 1]$ . La suite définie par $X_0 = g(U_0), \qquad X_{n+1} = f(X_n, U_{n+1})$ est une chaîne $(\mu, Q)$ . Pour tout $x \in I$ , la suite $X^x_0 = x$ , $X^x_{n+1} = f(X^x_n, U_{n+1})$ est une chaîne issue de $x$ .

(ii) Horizon fini. Pour $m \in \mathbb N$ , la formule $\begin{aligned} &p(x_0, \dots, x_m) \\ &= \mu(x_0)Q(x_0, x_1)\cdots Q(x_{m-1}, x_m) \end{aligned}$ définit une probabilité sur l'ensemble fini ou dénombrable $I^{m+1}$ , muni de toutes ses parties, sous laquelle les coordonnées forment une chaîne $(\mu, Q)$ jusqu'à l'instant m.

(iii) Il existe une chaîne $(\mu, Q)$ sur $[0, 1[$ muni de la mesure de Lebesgue.

Démonstration

(i) La loi d'un pas. Fixons $x$ , posons $s_{-1} = 0$ et $s_k = Q(x, y_0) + \cdots + Q(x, y_k)$ . Pour $k \geqslant 1$ , on a $f(x, u) = y_k$ si et seulement si $0 < u \leqslant 1$ et $s_{k-1} < u \leqslant s_k$ .

Si $0 < u < 1$ , un indice $k$ tel que $u \leqslant s_k$ existe, puisque les $s_k$ croissent vers $1$ ; l'ensemble des $u$ où $f(x, u) = y_0$ est donc $]0, s_0]$ , augmenté d'une partie de ${\mathbb R} \setminus \,]0, 1[$ .

Si $U$ est uniforme sur $[0, 1]$ , $P(a < U \leqslant b) = b - a$ pour $0 \leqslant a \leqslant b \leqslant 1$ et $P(U \notin \,]0, 1[) = 0$ ; donc $f(x, U)$ est une variable à valeurs dans I, et $P(f(x, U) = y_k) = s_k - s_{k-1} = Q(x, y_k)$ . De même, $g(U)$ a pour loi $\mu$ .

La récurrence. Par récurrence sur $n$ , $X_n$ est une variable à valeurs dans $I$ , mesurable pour $\sigma(U_0, \dots, U_n)$ , puisque $\begin{aligned} &\{X_{n+1} = y\} \\ &= \bigcup_{x \in I}\big(\{X_n = x\} \cap \{f(x, U_{n+1}) = y\}\big). \end{aligned}$

L'événement $A = \{X_0 = x_0, \dots, X_n = x_n\}$ appartient donc à $\sigma(U_0, \dots, U_n)$ , qui est indépendante de $U_{n+1}$ par regroupement (Indépendance, (ii)). Ainsi $\begin{aligned} &P(A \cap \{X_{n+1} = x_{n+1}\}) \\ &= P\big(A \cap \{f(x_n, U_{n+1}) = x_{n+1}\}\big) \\ &= P(A)\,Q(x_n, x_{n+1}), \end{aligned}$ et la formule de définition s'obtient par récurrence, à partir de $P(X_0 = x_0) = \mu(x_0)$ . Le cas de $X^x$ est identique, avec $X^x_0 = x$ .

(ii) Les poids sont positifs. En sommant d'abord sur $x_m$ , puis sur $x_{m-1}$ , et ainsi de suite, par paquets (Sommes dans [0, +∞], (iv)), chaque somme sur une ligne de $Q$ vaut $1$ , puis $\sum \mu = 1$ : la masse totale est $1$ , et $A \mapsto \sum_{w \in A}p(w)$ est une probabilité, σ-additive par sommation par paquets.

Pour $n \leqslant m$ , la même sommation sur $x_{n+1}, \dots, x_m$ seulement donne $P(X_0 = x_0, \dots, X_n = x_n) = \mu(x_0)\cdots Q(x_{n-1}, x_n)$ .

(iii) Le nœud Suites indépendantes, (i), fournit sur $[0, 1[$ une suite de variables indépendantes de loi uniforme ; on applique (i).

□

Remarque

La construction évite tout théorème d'extension de Kolmogorov ou d'Ionescu Tulcea, qui construirait directement une probabilité sur $(I^{\mathbb N}, \mathcal C)$ : la chaîne est une fonction explicite d'une suite de variables uniformes. C'est aussi la façon dont on simule une chaîne, chaque pas tirant un nombre au hasard dans $[0, 1]$ et cherchant dans quel intervalle de longueurs $Q(x, y_0), Q(x, y_1), \dots$ il tombe. Pour des espaces d'états non dénombrables, ces théorèmes deviennent nécessaires ; ils sont admis ici.

Remarque

Les chaînes $X^x$ et $X^y$ de (i), issues de deux états, sont construites sur les mêmes variables $U_n$ . L'erreur serait de les croire indépendantes : dès qu'elles se rencontrent, elles restent égales, puisque chaque pas applique la même fonction $f$ au même $U_{n+1}$ . Faire marcher deux chaînes ensemble jusqu'à ce qu'elles se rejoignent est l'idée du couplage, que le nœud Convergence vers l'équilibre mettra en œuvre avec deux chaînes indépendantes jusqu'à leur rencontre.

Repose sur

Chaînes de Markov et lois fini-dimensionnelles

Sert à

Convergence vers l'équilibre par couplage