Définition 1Chaînes de Markov

Matrices de transition et chemins

Dans tout ce chapitre, $I$ est un ensemble fini ou dénombrable, l'espace des états, muni de toutes ses parties ; on en fixe une fois pour toutes une énumération $y_0, y_1, \dots$ , indexée par $\{0, \dots, m - 1\}$ ou par ${\mathbb N}$ . Les sommes de familles positives indexées par $I$ sont celles du nœud Sommes dans [0, +∞] : elles ne dépendent d'aucun ordre.

Une mesure sur $I$ est une famille $\lambda = (\lambda(x))_{x \in I}$ d'éléments de $[0, +\infty]$ , identifiée à la mesure $A \mapsto \sum_{x \in A}\lambda(x)$ sur les parties de $I$ ; c'est une probabilité si $\sum_{x \in I}\lambda(x) = 1$ .

Une matrice de transition sur $I$ est une famille $Q = (Q(x, y))_{(x, y) \in I \times I}$ de réels positifs telle que, pour tout $x \in I$ , $\sum_{y \in I} Q(x, y) = 1 :$ la ligne $Q(x, \cdot)$ est une probabilité sur $I$ , la loi du pas suivant depuis l'état $x$ . La lettre $P$ reste réservée aux probabilités, comme dans le reste de l'atlas.

Pour deux matrices de transition $Q$ et $R$ , une mesure $\lambda$ et des états $x$ , $z$ , on pose $\begin{aligned} (QR)(x, z) &= \sum_{y \in I} Q(x, y)R(y, z), \\ (\lambda Q)(z) &= \sum_{y \in I} \lambda(y)Q(y, z), \end{aligned}$ puis $Q^0(x, y) = 1$ si $x = y$ et $0$ sinon, et $Q^{n+1} = Q^nQ$ .

Énoncé

(i) $QR$ est une matrice de transition, et le produit est associatif : $(QR)S = Q(RS)$ . Par suite, $Q^{m+n} = Q^mQ^n$ pour tous $m, n \in \mathbb N$ .

(ii) Pour toute mesure $\lambda$ , $(\lambda Q)R = \lambda(QR)$ , et $\lambda Q$ a la même masse totale que $\lambda$ ; en particulier, si $\lambda$ est une probabilité, $\lambda Q$ en est une.

(iii) Chemins. Pour $n \geqslant 1$ , $\begin{aligned} Q^n(x, y) = \sum_{x_1, \dots, x_{n-1}} &Q(x, x_1)Q(x_1, x_2) \\ &\cdots Q(x_{n-1}, y), \end{aligned}$ somme sur les chemins $x \to x_1 \to \cdots \to x_{n-1} \to y$ de longueur $n$ . En particulier, $Q^{m+n}(x, z) \geqslant Q^m(x, y)\,Q^n(y, z)$ pour tout état $y$ .

Démonstration

(i) Les termes étant positifs, la sommation par paquets (Sommes dans [0, +∞], (iv)) permet d'intervertir les sommes, et un facteur constant sort d'une somme par le point (ii) du même nœud. Ainsi $\begin{aligned} \sum_z (QR)(x, z) &= \sum_y Q(x, y)\sum_z R(y, z) \\ &= \sum_y Q(x, y) = 1, \end{aligned}$ ce qui montre aussi que chaque $(QR)(x, z)$ est un réel de $[0, 1]$ .

De même, les deux membres de l'associativité, évalués en $(x, w)$ , valent la somme sur $I \times I$ des termes $Q(x, y)R(y, z)S(z, w)$ .

La formule $Q^{m+n} = Q^mQ^n$ vaut pour $n = 0$ , puisque $Q^0$ est neutre pour le produit ; si elle vaut pour $n$ , l'associativité donne $\begin{aligned} Q^{m+n+1} &= (Q^mQ^n)Q \\ &= Q^m(Q^nQ) = Q^mQ^{n+1}. \end{aligned}$

(ii) C'est le même calcul, la mesure $\lambda$ jouant le rôle d'une ligne ; la masse totale de $\lambda Q$ est $\sum_y \lambda(y)\sum_z Q(y, z) = \sum_y \lambda(y)$ .

(iii) Pour $n = 1$ , il n'y a rien à démontrer. Si la formule vaut pour $n$ , on écrit $Q^{n+1}(x, y) = \sum_{x_n} Q^n(x, x_n)Q(x_n, y)$ , on remplace $Q^n(x, x_n)$ par sa somme sur les chemins, et l'on regroupe par paquets.

Enfin $Q^{m+n}(x, z) = \sum_{y'} Q^m(x, y')Q^n(y', z)$ par (i), et cette somme de termes positifs majore son terme d'indice $y$ .

□

Remarque

Sur $I = \{1, 2, 3\}$ , la matrice $Q = \begin{pmatrix} \frac12 & \frac12 & 0 \\[2pt] \frac14 & \frac12 & \frac14 \\[2pt] 0 & \frac13 & \frac23 \end{pmatrix}$ se lit sur son graphe de transition, qui a une flèche de $x$ vers $y$ chaque fois que $Q(x, y) > 0$ .

Le graphe de transition de

Q

: la flèche de

x

vers

y

porte

Q(x, y)

, et les nombres qui sortent d'un même état ont pour somme

1

. Le seul chemin de longueur

2

1

3

, en rouge, passe par

2

, d'où

Q^2(1, 3) = \frac12 \cdot \frac14 = \frac18

, conformément à (iii).

Cette matrice sert d'exemple dans tout le chapitre ; on verra au nœud Récurrence positive que sa probabilité invariante est $(\frac29, \frac49, \frac13)$ .

Remarque

Quand $I = \{1, \dots, m\}$ est fini, $Q$ est une matrice carrée (Matrices), et les produits ci-dessus sont les produits matriciels : une mesure est un vecteur ligne, que $Q$ multiplie à droite. L'erreur la plus répandue est d'écrire $Q\lambda$ au lieu de $\lambda Q$ . Le produit $Q\mathbf 1$ par la colonne dont toutes les coordonnées valent $1$ vaut $\mathbf 1$ , puisque les lignes sont de somme $1$ ; il dit que $1$ est valeur propre de $Q$ , mais rien sur l'évolution des lois.

Repose sur

C'est un point de départ.

Sert à

Chaînes de Markov et lois fini-dimensionnelles