Graphes et chaînes de Markov

En 1736, les habitants de Königsberg, en Prusse orientale, se posent une question en apparence anodine : peut-on se promener dans la ville en franchissant une et une seule fois chacun de ses sept ponts ? Leonhard Euler démontre que c'est impossible. Sa méthode, qui oublie tout des lieux pour ne retenir que des points et des liaisons, fonde une branche entièrement nouvelle des mathématiques : la théorie des graphes. Près de deux siècles plus tard, en 1906, le mathématicien russe Andreï Markov étudie l'alternance des voyelles et des consonnes dans Eugène Onéguine de Pouchkine, et introduit des processus aléatoires dont l'évolution ne dépend que de l'état présent : les chaînes qui portent aujourd'hui son nom. Ces deux idées, nées d'une promenade et d'un poème, sont devenues des outils essentiels du monde contemporain : réseaux sociaux, réseaux routiers ou informatiques sont des graphes, et lorsque Google classe les pages du web avec son algorithme PageRank, il calcule la distribution invariante d'une gigantesque chaîne de Markov. Ce chapitre présente ces deux notions, ainsi que le pont qui les relie : les matrices, étudiées au chapitre précédent.

Graphes : premières définitions

Un graphe est un objet d'une simplicité désarmante : des points, et des liens entre certains de ces points. Cette simplicité est précisément sa force, car elle permet de modéliser des situations très variées : des villes reliées par des routes, des personnes liées par une relation d'amitié, des ordinateurs connectés en réseau, des molécules dont les atomes sont liés chimiquement.

Remarques.

• Sauf mention contraire, les graphes étudiés dans ce chapitre sont simples : deux sommets sont reliés par au plus une arête, et aucune arête ne relie un sommet à lui-même. Lorsqu'on autorise plusieurs arêtes entre deux mêmes sommets, on parle de multigraphe ; nous en rencontrerons un célèbre exemple avec les ponts de Königsberg.
• Seule compte la structure des liaisons : la façon de dessiner le graphe (position des sommets, forme des arêtes) n'a aucune importance mathématique. Deux dessins différents peuvent représenter exactement le même graphe.

Le graphe complet

Le lemme des poignées de main

Voici la première propriété générale des graphes. Son surnom vient de l'image suivante : dans une assemblée, si l'on additionne le nombre de mains serrées par chaque personne, on compte chaque poignée de main deux fois.

Démonstration. Calculons la somme des degrés en comptant les contributions arête par arête. Chaque arête possède exactement deux extrémités : elle ajoute $1$ au degré de chacune d'elles, donc elle contribue pour exactement $2$ à la somme des degrés. Si le graphe compte $m$ arêtes, la somme des degrés vaut donc $2m$. $\mathrm{\square }$

Le lemme a une conséquence remarquable, qui jouera un rôle décisif dans l'étude des chaînes eulériennes.

Démonstration. Notons $S$ la somme des degrés de tous les sommets. Séparons cette somme en deux : la somme $S_1$ des degrés pairs et la somme $S_2$ des degrés impairs, de sorte que $S=S_1+S_2$. D'après le lemme des poignées de main, $S$ est paire ; et $S_1$, somme de nombres pairs, est paire. Donc $S_2=S-S_1$ est paire. Or une somme de nombres impairs est paire si et seulement si elle comporte un nombre pair de termes. Le nombre de sommets de degré impair est donc pair. $\mathrm{\square }$

Chaînes et connexité

Un graphe décrit des liaisons directes. Mais on veut souvent circuler de proche en proche : aller d'une ville à une autre en enchaînant plusieurs routes, transmettre une information d'une personne à une autre par une suite d'intermédiaires. C'est la notion de chaîne.

Remarques.

• Une chaîne peut passer plusieurs fois par le même sommet ou par la même arête : rien ne l'interdit dans la définition.
• Vocabulaire. Le mot « chaîne » est celui du programme pour les graphes non orientés. Dans un graphe orienté (où les liaisons sont des flèches à sens unique), on parle plutôt de chemin. Nous retrouverons les graphes orientés avec les chaînes de Markov.
• Le mot « chaîne » désignera donc deux choses dans ce chapitre : une chaîne dans un graphe (cette section) et une chaîne de Markov (sections suivantes). Le contexte lèvera toujours l'ambiguïté ; l'usage est ainsi fait.

Chaînes eulériennes

Revenons au problème fondateur. Se promener dans Königsberg en franchissant chaque pont exactement une fois, c'est parcourir un graphe en empruntant chaque arête exactement une fois. Donnons un nom à ce type de parcours.

Le génie d'Euler est d'avoir trouvé un critère qui évite d'explorer tous les parcours possibles : il suffit de regarder les degrés. L'idée est naturelle : à chaque passage par un sommet intermédiaire, on « consomme » deux arêtes (une pour arriver, une pour repartir) ; un sommet de degré impair ne peut donc être qu'un point de départ ou d'arrivée du parcours.

Rappelons que d'après la section précédente, le nombre de sommets de degré impair est nécessairement pair : les seuls cas favorables sont donc bien $0$ et $2$, et le cas « exactement un sommet impair » ne peut jamais se produire.

Retour aux ponts de Königsberg

La ville de Königsberg est traversée par un fleuve qui délimite quatre zones : la rive nord $N$, la rive sud $S$, l'île centrale $I$ et l'île est $E$. Sept ponts les relient : deux ponts entre $N$ et $I$, deux ponts entre $S$ et $I$, un pont $N\text{-}E$, un pont $S\text{-}E$ et un pont $I\text{-}E$. On obtient le multigraphe de la figure (certaines paires de sommets sont reliées par deux arêtes, mais le théorème d'Euler et la notion de degré s'y appliquent de la même façon).

Calculons les degrés : $\mathrm{deg}(I)=5$, $\mathrm{deg}(N)=3$, $\mathrm{deg}(S)=3$, $\mathrm{deg}(E)=3$. Les quatre sommets sont de degré impair. Comme $4>2$, le théorème d'Euler conclut : il n'existe aucune chaîne eulérienne. La promenade rêvée des habitants de Königsberg est impossible, et aucune astuce d'itinéraire n'y changera rien. C'est toute la puissance du point de vue d'Euler : une impossibilité définitive, établie par un simple comptage.

Matrice d'adjacence

Pour étudier un graphe par le calcul, on le code dans un tableau de nombres : une matrice. Cette idée, anodine en apparence, va révéler un lien profond entre le produit matriciel du chapitre précédent et le dénombrement des chaînes.

Remarques.

• La matrice d'adjacence dépend de l'ordre choisi pour numéroter les sommets : on précise toujours cet ordre.
• Pour un graphe non orienté, une arête entre $i$ et $j$ donne $a_{ij}=a_{ji}=1$ : la matrice est symétrique par rapport à sa diagonale. Pour un graphe simple, la diagonale est nulle (pas de boucle).
• Pour un graphe orienté, on pose $a_{ij}=1$ lorsqu'une flèche va de $i$ vers $j$ ; la matrice n'a alors aucune raison d'être symétrique.
• La somme des coefficients de la ligne $i$ (ou de la colonne $i$, par symétrie) est le degré du sommet $i$.

Puissances de la matrice d'adjacence et dénombrement des chaînes

Voici le théorème central de cette partie, et la première des démonstrations exigibles du chapitre. Il affirme que le produit matriciel, défini au chapitre précédent par la règle « ligne par colonne », compte exactement les chaînes du graphe.

Démonstration. Raisonnons par récurrence sur $n$. Pour tout $n⩾1$, notons $P(n)$ la propriété : « pour tous sommets $i$ et $j$, le coefficient d'indices $(i;j)$ de $A^n$ est le nombre de chaînes de longueur $n$ reliant $i$ à $j$ ».

Initialisation. Pour $n=1$ : $A^1=A$, et le coefficient $a_{ij}$ vaut $1$ s'il existe une arête entre $i$ et $j$, $0$ sinon. Or une chaîne de longueur $1$ de $i$ à $j$ est exactement une arête entre $i$ et $j$ : le coefficient $a_{ij}$ est bien le nombre de telles chaînes. $P(1)$ est vraie.

Hérédité. Soit $n⩾1$ tel que $P(n)$ soit vraie. Notons $b_{ik}$ le coefficient d'indices $(i;k)$ de $A^n$ : par hypothèse de récurrence, $b_{ik}$ est le nombre de chaînes de longueur $n$ reliant $i$ à $k$. Comme $A^{n+1}=A^n\times A$, la règle du produit « ligne par colonne » donne pour le coefficient d'indices $(i;j)$ de $A^{n+1}$ :

$$b_{i1}{a}_{1j}+b_{i2}{a}_{2j}+\cdots +b_{ip}{a}_{pj}=\sum _{k=1}^p{b}_{ik}{a}_{kj}\mathrm{.}$$

Comptons maintenant les chaînes de longueur $n+1$ reliant $i$ à $j$. Une telle chaîne est entièrement déterminée par la donnée de son avant-dernier sommet $k$ et de son début : elle se décompose de façon unique en une chaîne de longueur $n$ reliant $i$ à $k$, suivie de l'arête $k\text{-}j$. Pour un sommet $k$ fixé :

• si $k$ est adjacent à $j$ (c'est-à-dire $a_{kj}=1$), chaque chaîne de longueur $n$ de $i$ à $k$ se prolonge en exactement une chaîne de longueur $n+1$ de $i$ à $j$ passant par $k$ en avant-dernière position : cela fait $b_{ik}=b_{ik}{a}_{kj}$ chaînes ;
• si $k$ n'est pas adjacent à $j$ (c'est-à-dire $a_{kj}=0$), aucun prolongement n'est possible : cela fait $0=b_{ik}{a}_{kj}$ chaîne.

En sommant sur tous les avant-derniers sommets $k$ possibles, le nombre de chaînes de longueur $n+1$ reliant $i$ à $j$ vaut ${\displaystyle \sum _{k=1}^p{b}_{ik}{a}_{kj}}$, qui est précisément le coefficient d'indices $(i;j)$ de $A^{n+1}$. Donc $P(n+1)$ est vraie.

Conclusion. Par récurrence, $P(n)$ est vraie pour tout entier $n⩾1$. $\mathrm{\square }$

Remarque. Le théorème vaut aussi pour un graphe orienté : le coefficient $(i;j)$ de $A^n$ compte alors les chemins de longueur $n$ allant de $i$ vers $j$, en respectant le sens des flèches. La démonstration est identique.

Chaînes de Markov à deux ou trois états

Quittons les parcours dans les graphes pour une autre question : comment décrire un système qui évolue au hasard, étape après étape ? La météo qui change d'un jour à l'autre, un client qui change d'opérateur téléphonique d'une année sur l'autre, un pion qui se déplace au hasard sur un graphe : dans chacune de ces situations, le système occupe à chaque instant l'un d'un petit nombre d'états, et passe de l'un à l'autre selon des probabilités fixées.

L'hypothèse fondamentale d'Andreï Markov est la suivante : la probabilité de passer à tel ou tel état à l'étape suivante ne dépend que de l'état actuel, et non de tout le passé du système. On dit que le processus est sans mémoire. Pour la météo de notre modèle simplifié, cela signifie que la probabilité qu'il fasse beau demain ne dépend que du temps d'aujourd'hui, pas de celui d'hier ni d'avant-hier.

Démonstration. Les coefficients sont des probabilités, donc positifs ou nuls. Fixons un état $i$ et plaçons-nous dans la situation où le système est dans l'état $i$ à l'instant $n$. À l'instant $n+1$, le système occupe nécessairement un et un seul des états $1,\dots ,N$ : les événements $(X_{n+1}=1),\dots ,(X_{n+1}=N)$ forment une partition de l'univers. La somme de leurs probabilités conditionnelles vaut donc $1$ :

$$p_{i1}+p_{i2}+\cdots +p_{iN}=1,$$

ce qui est exactement la somme de la ligne $i$ de $P$. $\mathrm{\square }$

Graphe orienté pondéré associé

Une chaîne de Markov se visualise naturellement par un graphe, mais d'un type nouveau par rapport à la première partie du chapitre : ses liaisons ont un sens et portent un nombre.

Ce graphe est orienté (les flèches ont un sens : passer de $i$ à $j$ n'a pas la même probabilité que passer de $j$ à $i$) et pondéré (chaque flèche porte un poids). Une flèche d'un état vers lui-même, appelée boucle, représente la probabilité de rester sur place. La propriété des lignes se lit directement sur le graphe : la somme des poids des flèches issues de chaque sommet vaut $1$. Graphe et matrice de transition contiennent exactement la même information ; savoir passer de l'un à l'autre, dans les deux sens, est une compétence essentielle du chapitre.

Exemple à deux états : la météo

Modélisons la météo d'une région en distinguant deux états : l'état $S$ (soleil) et l'état $P$ (pluie). D'un jour au suivant, les observations donnent les règles d'évolution suivantes :

• s'il fait soleil aujourd'hui, il fera soleil demain avec probabilité $\mathrm{0,8}$, et il pleuvra avec probabilité $\mathrm{0,2}$ ;
• s'il pleut aujourd'hui, il fera soleil demain avec probabilité $\mathrm{0,6}$, et il pleuvra avec probabilité $\mathrm{0,4}$.

Autrement dit : $p(S\to S)=\mathrm{0,8}$, $p(S\to P)=\mathrm{0,2}$, $p(P\to S)=\mathrm{0,6}$ et $p(P\to P)=\mathrm{0,4}$. En ordonnant les états ($S$ puis $P$), la matrice de transition est :

$$P=\left(\begin{array}{cc}\mathrm{0,8}& \mathrm{0,2}\\ \mathrm{0,6}& \mathrm{0,4}\end{array}\right)$$

Chaque ligne somme bien à $1$ : $\mathrm{0,8}+\mathrm{0,2}=1$ et $\mathrm{0,6}+\mathrm{0,4}=1$. La première ligne se lit « en partant de $S$ », la seconde « en partant de $P$ ».

Le graphe associé comporte deux boucles (rester au soleil : $\mathrm{0,8}$ ; rester sous la pluie : $\mathrm{0,4}$) et deux flèches croisées (passer du soleil à la pluie : $\mathrm{0,2}$ ; de la pluie au soleil : $\mathrm{0,6}$). Cet exemple nous accompagnera jusqu'à la fin du chapitre.

Exemple à trois états : parts de marché

Trois opérateurs de téléphonie $A$, $B$ et $C$ se partagent un marché. Chaque année, les clients peuvent changer d'opérateur, et les études de fidélité donnent les probabilités de transition suivantes : un client de $A$ reste chez $A$ avec probabilité $\mathrm{0,6}$, part chez $B$ avec probabilité $\mathrm{0,3}$ et chez $C$ avec probabilité $\mathrm{0,1}$ ; un client de $B$ reste avec probabilité $\mathrm{0,7}$, part chez $A$ avec probabilité $\mathrm{0,2}$ et chez $C$ avec probabilité $\mathrm{0,1}$ ; un client de $C$ reste avec probabilité $\mathrm{0,7}$, part chez $A$ avec probabilité $\mathrm{0,1}$ et chez $B$ avec probabilité $\mathrm{0,2}$.

La situation de chaque client suit une chaîne de Markov à trois états dont la matrice de transition, dans l'ordre $A$, $B$, $C$, est :

$$P=\left(\begin{array}{ccc}\mathrm{0,6}& \mathrm{0,3}& \mathrm{0,1}\\ \mathrm{0,2}& \mathrm{0,7}& \mathrm{0,1}\\ \mathrm{0,1}& \mathrm{0,2}& \mathrm{0,7}\end{array}\right)$$

On vérifie que chaque ligne somme à $1$, et le graphe orienté pondéré comporte neuf flèches, boucles comprises.

Remarques (deux modèles célèbres).

• Marche aléatoire. Un pion est posé sur un sommet d'un triangle $A\text{-}B\text{-}C$ ; à chaque étape, il se déplace vers l'un des deux sommets voisins choisi au hasard de façon équiprobable. La position du pion suit une chaîne de Markov à trois états, de matrice de transition $\left(\begin{array}{ccc}0& \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& 0& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}& 0\end{array}\right)$. C'est le prototype des marches aléatoires sur un graphe, où nos deux objets d'étude se rejoignent.
• Le modèle d'urnes d'Ehrenfest. Deux urnes contiennent $2$ boules en tout ; à chaque étape, on choisit une boule au hasard et on la change d'urne. Le nombre de boules de la première urne prend les valeurs $0$, $1$ ou $2$ : c'est une chaîne de Markov à trois états, de matrice de transition $\left(\begin{array}{ccc}0& 1& 0\\ \frac{1}{2}& 0& \frac{1}{2}\\ 0& 1& 0\end{array}\right)$. Ce modèle, imaginé par les physiciens Paul et Tatiana Ehrenfest en 1907, décrit la diffusion d'un gaz entre deux compartiments.

Distribution après n transitions

La matrice de transition décrit l'évolution du système connaissant son état actuel. Mais en général, l'état du système à un instant donné est lui-même aléatoire : on le décrit par une distribution de probabilité, que l'on range dans une matrice ligne pour pouvoir calculer.

Comment passe-t-on de ${\pi }_n$ à ${\pi }_{n+1}$ ? Rappelons d'abord la règle de calcul du chapitre précédent, dans le cas qui nous occupe : si $\pi =\left(\begin{array}{ccc}\pi (1)& \cdots & \pi (N)\end{array}\right)$ est une matrice ligne de taille $1\times N$ et $P$ une matrice carrée d'ordre $N$, le produit $\pi P$ est la matrice ligne de taille $1\times N$ dont le $j$-ième coefficient est le produit de la ligne $\pi$ par la $j$-ième colonne de $P$ :

$$\pi (1)p_{1j}+\pi (2)p_{2j}+\cdots +\pi (N)p_{Nj}\mathrm{.}$$

Ce produit « ligne par colonne » est exactement la formule des probabilités totales, comme le montre la démonstration suivante ; c'est la deuxième démonstration exigible du chapitre.

Démonstration.

Première formule. Fixons un état $j$ et un instant $n$. Les événements $(X_n=1),(X_n=2),\dots ,(X_n=N)$ forment une partition de l'univers : à l'instant $n$, le système est dans un et un seul de ces états. La formule des probabilités totales donne alors :

$$P(X_{n+1}=j)=\sum _{i=1}^{N}P(X_n=i)\times P_{(X_n=i)}(X_{n+1}=j)=\sum _{i=1}^{N}P(X_n=i)p_{ij}\mathrm{.}$$

(Si l'un des événements $(X_n=i)$ est de probabilité nulle, son terme est nul et la formule reste valable.) Le membre de gauche est le $j$-ième coefficient de ${\pi }_{n+1}$ ; le membre de droite est le produit de la ligne ${\pi }_n$ par la $j$-ième colonne de $P$, c'est-à-dire le $j$-ième coefficient de ${\pi }_{n}P$. Comme cette égalité vaut pour chaque $j$, on conclut : ${\pi }_{n+1}={\pi }_{n}P$.

Deuxième formule. Raisonnons par récurrence sur $n$. Notons $Q(n)$ la propriété « ${\pi }_n={\pi }_0{P}^n$ ».

Initialisation. Pour $n=0$ : $P^0=I$ (matrice identité, vue au chapitre précédent) et ${\pi }_{0}I={\pi }_0$, donc $Q(0)$ est vraie.

Hérédité. Soit $n⩾0$ tel que $Q(n)$ soit vraie. Alors, d'après la première formule et l'associativité du produit matriciel :

$${\pi }_{n+1}={\pi }_{n}P=\left({\pi }_0{P}^n\right)P={\pi }_0\left(P^{n}P\right)={\pi }_0{P}^{n+1},$$

donc $Q(n+1)$ est vraie.

Conclusion. Par récurrence, ${\pi }_n={\pi }_0{P}^n$ pour tout entier naturel $n$. $\mathrm{\square }$

Interprétation des coefficients de la puissance n-ième

La formule ${\pi }_n={\pi }_0{P}^n$ met en jeu la puissance $n$-ième de la matrice de transition. Ses coefficients ont une interprétation directe, parfaitement analogue au théorème sur la matrice d'adjacence : là où $A^n$ comptait les chaînes de longueur $n$, la matrice $P^n$ en donne la version probabiliste.

Démonstration. Raisonnons par récurrence sur $n$. Fixons un état $i$ tel que $P(X_0=i)>0$ et notons, pour $n⩾1$, $R(n)$ la propriété : « pour tout état $j$, le coefficient d'indices $(i;j)$ de $P^n$ vaut $P_{(X_0=i)}(X_n=j)$ ».

Initialisation. Pour $n=1$ : par définition de la matrice de transition, $p_{ij}=P_{(X_0=i)}(X_1=j)$, donc $R(1)$ est vraie.

Hérédité. Soit $n⩾1$ tel que $R(n)$ soit vraie. Plaçons-nous dans la situation où le système part de l'état $i$, c'est-à-dire raisonnons avec la probabilité conditionnelle $P_{(X_0=i)}$, qui est une probabilité comme une autre. Les événements $(X_n=k)$, pour $k$ décrivant les états, forment une partition de l'univers ; la formule des probabilités totales appliquée à cette probabilité donne :

$$P_{(X_0=i)}(X_{n+1}=j)=\sum _{k=1}^N{P}_{(X_0=i)}(X_n=k)\times P_{(X_0=i)\cap (X_n=k)}(X_{n+1}=j)\mathrm{.}$$

Or la chaîne est sans mémoire : sachant que le système est dans l'état $k$ à l'instant $n$, la probabilité qu'il passe dans l'état $j$ à l'instant $n+1$ ne dépend pas de son état initial, donc $P_{(X_0=i)\cap (X_n=k)}(X_{n+1}=j)=p_{kj}$. Avec l'hypothèse de récurrence $P_{(X_0=i)}(X_n=k)={\left(P^n\right)}_{ik}$, on obtient :

$$P_{(X_0=i)}(X_{n+1}=j)=\sum _{k=1}^N{\left(P^n\right)}_{ik}{p}_{kj},$$

et le membre de droite est le produit de la ligne $i$ de $P^n$ par la colonne $j$ de $P$, c'est-à-dire le coefficient d'indices $(i;j)$ de $P^n\times P=P^{n+1}$. Donc $R(n+1)$ est vraie.

Conclusion. Par récurrence, la propriété est établie pour tout entier $n⩾1$. $\mathrm{\square }$

Remarque. La ligne $i$ de $P^n$ se lit ainsi : c'est la distribution du système après $n$ transitions lorsqu'il part de façon certaine de l'état $i$. C'est cohérent avec la formule ${\pi }_n={\pi }_0{P}^n$ : si ${\pi }_0$ vaut $1$ en position $i$ et $0$ ailleurs, le produit ${\pi }_0{P}^n$ extrait exactement la ligne $i$ de $P^n$.

Exemple : la météo, suite

Reprenons la chaîne météo de matrice $P=\left(\begin{array}{cc}\mathrm{0,8}& \mathrm{0,2}\\ \mathrm{0,6}& \mathrm{0,4}\end{array}\right)$, et supposons qu'au jour $0$, soleil et pluie soient équiprobables : ${\pi }_0=\left(\begin{array}{cc}\mathrm{0,5}& \mathrm{0,5}\end{array}\right)$.

Distribution au jour $1$. On calcule ${\pi }_1={\pi }_{0}P$, coefficient par coefficient (ligne par colonne) :

$${\pi }_1=\left(\begin{array}{cc}\mathrm{0,5}\times \mathrm{0,8}+\mathrm{0,5}\times \mathrm{0,6}& \mathrm{0,5}\times \mathrm{0,2}+\mathrm{0,5}\times \mathrm{0,4}\end{array}\right)=\left(\begin{array}{cc}\mathrm{0,7}& \mathrm{0,3}\end{array}\right)\mathrm{.}$$

Au jour $1$, il fait soleil avec probabilité $\mathrm{0,7}$.

Distribution au jour $2$. De même, ${\pi }_2={\pi }_{1}P$ :

$${\pi }_2=\left(\begin{array}{cc}\mathrm{0,7}\times \mathrm{0,8}+\mathrm{0,3}\times \mathrm{0,6}& \mathrm{0,7}\times \mathrm{0,2}+\mathrm{0,3}\times \mathrm{0,4}\end{array}\right)=\left(\begin{array}{cc}\mathrm{0,74}& \mathrm{0,26}\end{array}\right)\mathrm{.}$$

Vérification par $P^2$. Calculons la puissance seconde de la matrice de transition :

$$P^2=\left(\begin{array}{cc}\mathrm{0,8}& \mathrm{0,2}\\ \mathrm{0,6}& \mathrm{0,4}\end{array}\right)\left(\begin{array}{cc}\mathrm{0,8}& \mathrm{0,2}\\ \mathrm{0,6}& \mathrm{0,4}\end{array}\right)=\left(\begin{array}{cc}\mathrm{0,76}& \mathrm{0,24}\\ \mathrm{0,72}& \mathrm{0,28}\end{array}\right)$$

Le coefficient d'indices $(1;1)$ s'interprète : sachant qu'il fait soleil aujourd'hui, la probabilité qu'il fasse soleil dans deux jours vaut $\mathrm{0,76}$. De même, le coefficient $(2;1)$ indique qu'après un jour de pluie, il fera soleil le surlendemain avec probabilité $\mathrm{0,72}$. Et l'on retrouve bien :

$${\pi }_0{P}^2=\left(\begin{array}{cc}\mathrm{0,5}\times \mathrm{0,76}+\mathrm{0,5}\times \mathrm{0,72}& \mathrm{0,5}\times \mathrm{0,24}+\mathrm{0,5}\times \mathrm{0,28}\end{array}\right)=\left(\begin{array}{cc}\mathrm{0,74}& \mathrm{0,26}\end{array}\right)={\pi }_2\mathrm{.}$$

Distributions invariantes

Dans l'exemple météo, les distributions successives $\left(\begin{array}{cc}\mathrm{0,5}& \mathrm{0,5}\end{array}\right)$, $\left(\begin{array}{cc}\mathrm{0,7}& \mathrm{0,3}\end{array}\right)$, $\left(\begin{array}{cc}\mathrm{0,74}& \mathrm{0,26}\end{array}\right)$ semblent se rapprocher d'une distribution limite. Existe-t-il une distribution qui, elle, ne bouge plus du tout ? C'est la notion de distribution invariante, qui décrit le régime stationnaire de la chaîne.

Calcul complet sur l'exemple météo

Cherchons les distributions invariantes de la chaîne météo, de matrice $P=\left(\begin{array}{cc}\mathrm{0,8}& \mathrm{0,2}\\ \mathrm{0,6}& \mathrm{0,4}\end{array}\right)$. Posons $\pi =\left(\begin{array}{cc}x& y\end{array}\right)$. L'équation $\pi P=\pi$ s'écrit coefficient par coefficient :

$$\{\begin{array}{l}\mathrm{0,8}x+\mathrm{0,6}y=x\\ \mathrm{0,2}x+\mathrm{0,4}y=y\end{array}⟺\{\begin{array}{l}\mathrm{0,6}y=\mathrm{0,2}x\\ \mathrm{0,2}x=\mathrm{0,6}y\end{array}⟺x=3y\mathrm{.}$$

Les deux équations sont bien équivalentes, comme annoncé. Avec la condition $x+y=1$, on obtient $3y+y=1$, donc $y=\mathrm{0,25}$ et $x=\mathrm{0,75}$. Les coefficients sont positifs et de somme $1$ : la chaîne admet une unique distribution invariante,

$$\pi =\left(\begin{array}{cc}\mathrm{0,75}& \mathrm{0,25}\end{array}\right)\mathrm{.}$$

Vérification. On contrôle que $\pi P=\pi$ : le premier coefficient de $\pi P$ vaut $\mathrm{0,75}\times \mathrm{0,8}+\mathrm{0,25}\times \mathrm{0,6}=\mathrm{0,6}+\mathrm{0,15}=\mathrm{0,75}$, et le second $\mathrm{0,75}\times \mathrm{0,2}+\mathrm{0,25}\times \mathrm{0,4}=\mathrm{0,15}+\mathrm{0,1}=\mathrm{0,25}$. L'invariance est confirmée.

Interprétation. En régime stationnaire, il fait soleil trois jours sur quatre dans cette région.

Calcul sur l'exemple à trois états

Convergence vers la distribution invariante

Revenons à la météo et observons numériquement l'évolution de $P(X_n=S)$, la probabilité de soleil au jour $n$, pour trois distributions initiales très différentes :

Le constat est frappant : dans les trois cas, $P(X_n=S)$ se rapproche très vite de $\mathrm{0,75}$, la valeur donnée par la distribution invariante. En quelques jours, le système oublie sa condition initiale : c'est une manifestation spectaculaire du caractère sans mémoire de la chaîne. Ce phénomène sera toujours constaté dans les situations étudiées dans ce chapitre : nous l'admettons. Sa démonstration générale dépasse largement le programme, et il existe d'ailleurs des chaînes de Markov pour lesquelles la convergence n'a pas lieu.

La propriété suivante éclaire le lien entre convergence et invariance : si la suite des distributions converge, sa limite ne peut être qu'une distribution invariante.

Démonstration. Chaque coefficient de ${\pi }_{n+1}={\pi }_{n}P$ est une combinaison des coefficients de ${\pi }_n$ à coefficients constants (ceux de $P$) : par opérations sur les limites, le membre de droite tend vers le coefficient correspondant de $\pi P$, tandis que le membre de gauche tend vers celui de $\pi$. À la limite, $\pi =\pi P$. De plus, les coefficients de ${\pi }_n$ sont positifs et de somme $1$ pour tout $n$ : par passage à la limite, ceux de $\pi$ aussi. Donc $\pi$ est une distribution invariante. $\mathrm{\square }$

Remarques.

• Dans les deux exemples traités, le système $\pi P=\pi$ complété par la condition de somme $1$ admet une unique solution. Ce sera le cas dans toutes les situations étudiées, mais ce n'est pas automatique en général : pour la matrice de transition $P=I$ (le système ne bouge jamais), toute distribution est invariante.
• Culture : l'algorithme PageRank. Conçu en 1998 par Larry Page et Sergueï Brin, les fondateurs de Google, PageRank repose exactement sur le principe de ce chapitre. Le web est modélisé par un graphe orienté gigantesque : les pages sont les sommets, les liens hypertextes les flèches. Un internaute idéalisé qui clique au hasard de page en page définit une chaîne de Markov, et la distribution invariante de cette chaîne attribue à chaque page un score, son PageRank, qui mesure son importance : les pages vers lesquelles convergent beaucoup de chemins reçoivent un score élevé. Nos chaînes à deux ou trois états sont les modèles réduits d'un calcul que Google mène sur des milliards d'états.

L'essentiel du chapitre

• Un graphe est un ensemble de sommets reliés par des arêtes ; son ordre est son nombre de sommets, le degré d'un sommet est son nombre d'arêtes incidentes. La somme des degrés vaut le double du nombre d'arêtes (lemme des poignées de main), donc le nombre de sommets de degré impair est toujours pair.
• Une chaîne de longueur $n$ est une suite de $n$ arêtes mises bout à bout ; un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne.
• Un graphe connexe admet une chaîne eulérienne (chaque arête une et une seule fois) si et seulement si le nombre de sommets de degré impair vaut $0$ ou $2$ (théorème d'Euler, admis).
• Le coefficient $(i;j)$ de $A^n$, où $A$ est la matrice d'adjacence, compte les chaînes de longueur $n$ reliant $i$ à $j$.
• Une chaîne de Markov à deux ou trois états est un processus aléatoire sans mémoire ; elle est décrite par sa matrice de transition $P$ (stochastique : lignes positives de somme $1$) et représentée par un graphe orienté pondéré.
• La distribution ${\pi }_n$ (matrice ligne) évolue selon ${\pi }_{n+1}={\pi }_{n}P$, d'où ${\pi }_n={\pi }_0{P}^n$ ; le coefficient $(i;j)$ de $P^n$ est la probabilité de passer de $i$ à $j$ en $n$ transitions.
• Une distribution invariante vérifie $\pi P=\pi$ avec des coefficients positifs de somme $1$ ; on la calcule en résolvant un système linéaire. Dans les situations étudiées, ${\pi }_n$ converge vers cette distribution quelle que soit la distribution initiale (résultat admis).