Maths expertes
Graphes et chaines de Markov
Avant les chaines de Markov, on commence par lire un graphe simple : sommets, aretes, degres, connexite et parcours. Cette partie servira de base au chapitre suivant.
Version HTML statique du cours. Si JavaScript est actif, MathSups affiche l’expérience interactive avec QCM, exercices guidés et assistant IA.
Graphes: vocabulaire
Avant les chaines de Markov, on commence par lire un graphe simple : sommets, aretes, degres, connexite et parcours. Cette partie servira de base au chapitre suivant.
Graphe, sommets et aretes
Un graphe est un ensemble de sommets relies par des aretes.
L'ordre d'un graphe est le nombre de sommets. Le degre d'un sommet est le nombre d'aretes qui lui sont incidentes.
Une chaine est une suite de sommets relies par des aretes. Si on peut aller d'un sommet a un autre par une chaine, on dit que le graphe est connexe.
Exemple: un reseau de villes reliees par des routes peut etre modelise par un graphe dont les sommets sont les villes et les aretes les routes.
Somme des degrés
Dans tout graphe, la somme des degrés de tous les sommets est égale au double du nombre d'arêtes :
$$\sum_{v} \deg(v) = 2 \times |E|$$
Démonstration : chaque arête contribue exactement 2 au total des degrés (une fois pour chaque sommet qu'elle relie).
Conséquence : le nombre de sommets de degré impair est toujours pair.
Graphe complet
Dans un graphe complet, chaque sommet est relie a tous les autres sommets.
Pour un graphe complet a $n$ sommets, chaque sommet a pour degre $n-1$.
Cette notion est utile comme modele "maximal": toutes les liaisons possibles sont presentes.
Lire un graphe
Pour etudier un graphe, on commence en general par identifier:
- les sommets;
- les aretes;
- l'ordre du graphe;
- les sommets de degre particulier;
- les chaines possibles et la connexion.
Ce premier tri permet deja de lire une situation avant de passer au calcul matriciel.
Exemple de lecture
Dans un reseau de 5 sommets, si un sommet est relie a 3 autres sommets, son degre vaut 3. Si tous les sommets sont accessibles les uns des autres, le graphe est connexe. Si deux sommets sont relies par exactement une chaine, le graphe peut modeliser un parcours unique ou presque unique selon le contexte.
Nombre d aretes d un graphe complet
Dans un graphe complet a $n$ sommets, chaque sommet est relie aux $n-1$ autres. On compte donc $$n(n-1)$$ extremites d aretes.
Comme chaque arete est comptee deux fois, le nombre total d aretes vaut :
$$\frac{n(n-1)}{2}.$$
Somme des degres et nombre d aretes
Dans un graphe non oriente ayant $$m$$ aretes, la somme des degres de tous les sommets vaut :
$$\sum d(s)=2m.$$
Chaque arete est en effet comptee deux fois, une fois a chacun de ses extremites.
Dans le graphe complet $$K_n,$$ chaque sommet a pour degre $$n-1,$$ donc :
$$n(n-1)=2m \qquad \Rightarrow \qquad m=\frac{n(n-1)}{2}.$$
\sum d(s)=2m
Matrice d'adjacence et chemins
Un graphe peut etre encode par une matrice d'adjacence. Cette representation permet de compter des chemins et de transformer un probleme de graphe en calcul matriciel.
Matrice d'adjacence
Pour un graphe a $n$ sommets, la matrice d'adjacence est la matrice $A$ dont le coefficient $a_{ij}$ indique s'il existe une arete du sommet $i$ vers le sommet $j$.
Dans un graphe non oriente simple, on a en general $a_{ij}=1$ si les sommets $i$ et $j$ sont relies, et $0$ sinon.
Lecture de $A^n$
Le coefficient $(i,j)$ de la matrice $A^n$ donne le nombre de chemins de longueur $n$ reliant le sommet $i$ au sommet $j$.
C'est une propriete cle du programme: elle relie directement le calcul matriciel et les graphes.
Idee de la preuve
Pour $n=1$, le coefficient $(i,j)$ de $A$ compte les aretes. Si on passe de $n$ a $n+1$, chaque chemin de longueur $n+1$ s'obtient en ajoutant une etape a un chemin de longueur $n$. La formule de multiplication matricielle reproduit exactement ce comptage par sommation sur les sommets intermediaires.
Compter des chemins
On procede souvent ainsi:
- on ecrit la matrice d'adjacence;
- on calcule la puissance demandee, souvent $A^2$, $A^3$ ou $A^n$;
- on lit le coefficient voulu.
Ce passage du graphe vers la matrice permet d'automatiser un probleme qui serait laborieux a la main.
Exemple de comptage
Si $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}$, alors $A^2=\begin{pmatrix}1&1\\1&2\end{pmatrix}$. Le coefficient $(2,2)$ vaut donc 2: il existe deux chemins de longueur 2 du sommet 2 vers lui-meme.
Graphes ponderes et transitions
Les chaines de Markov modelisent des situations ou l on passe d un etat a un autre avec des probabilites de transition. Le support naturel est un graphe oriente pondere.
On represente souvent les etats par des sommets et les transitions par des fleches munies de probabilites. La somme des probabilites sortantes d un etat vaut 1.
Graphe oriente pondere
Un graphe oriente pondere est un graphe ou chaque arete orientee porte un nombre, souvent une probabilite.
Si l on part d un etat donne, les poids des fleches sortantes indiquent comment se repartit la probabilite au pas suivant.
Somme des probabilites sortantes
Pour chaque etat, la somme des probabilites des transitions sortantes vaut 1.
C est la condition de base pour que le modele soit probabiliste.
Pourquoi cette somme vaut 1
En partant d un etat, il faut forcement aller quelque part au pas suivant. Comme les issues possibles forment une partition des cas, leurs probabilites doivent s additionner a 1.
Exemple a deux etats
Si depuis l etat $1$ on reste en $1$ avec probabilite $0.7$ et on va vers $2$ avec probabilite $0.3$, alors la ligne de sortie de l etat $1$ est $(0.7,0.3)$.
Distribution initiale et matrice de transition
Une chaine de Markov se lit avec une distribution initiale et une matrice de transition. Ces deux objets suffisent a decrire l evolution de la repartition des probabilites.
Distribution initiale
La distribution initiale est la repartition des probabilites au temps 0. Pour une chaine a deux ou trois etats, on la note souvent sous forme de matrice ligne $\pi_0$.
Par exemple, si on est certain d etre dans l etat 1 au depart, alors $\pi_0=(1,0)$ dans le cas a deux etats.
Matrice de transition
La matrice de transition $P$ contient les probabilites de passer d un etat a un autre en un pas.
Chaque ligne de $P$ est une distribution de probabilite, donc la somme des coefficients d une ligne vaut 1.
Evolution d une distribution
Si $\pi_n$ designe la distribution au temps $n$, alors on a la relation $\pi_{n+1}=\pi_nP$.
Par recurrence, $\pi_n=\pi_0P^n$.
Demonstration de $\pi_{n+1}=\pi_nP$ par la formule des probabilites totales
Notons $\pi_n^{(i)} = P(X_n = i)$ la probabilite d etre dans l etat $i$ au temps $n$.
Par la formule des probabilites totales, en conditionnant sur l etat au temps $n$ :
$$P(X_{n+1}=j) = \sum_{i} P(X_n=i)\cdot P(X_{n+1}=j \mid X_n=i).$$
Or $P(X_{n+1}=j \mid X_n=i) = P_{ij}$ est le coefficient de la ligne $i$, colonne $j$ de $P$. Donc :
$$\pi_{n+1}^{(j)} = \sum_i \pi_n^{(i)} P_{ij}.$$
C est exactement le $j$-ieme coefficient du produit matriciel $\pi_nP$. On obtient ainsi $\pi_{n+1}=\pi_nP$.
Par recurrence immediate : $\pi_n = \pi_0 P^n$.
Lire une matrice de transition
Pour lire une matrice de transition, on identifie d abord les etats, puis on verifie pour chaque ligne que les coefficients representent bien des probabilites et que leur somme vaut 1.
Cette lecture est essentielle avant tout calcul.
Exemple a deux etats
Si $P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}$ et si $\pi_0=(1,0)$, alors $\pi_1=(0.8,0.2)$.
La premiere ligne dit que depuis l etat 1, on reste en 1 avec probabilite 0.8 et on va en 2 avec probabilite 0.2.
Cas standard a deux etats
Dans beaucoup d exercices, on ecrit la matrice de transition sous la forme :
$$P=\begin{pmatrix}p&1-p\\ q&1-q\end{pmatrix}.$$
Chaque ligne somme bien a 1, ce qui garantit le sens probabiliste du modele. Cette ecriture est pratique pour faire des calculs explicites et chercher une distribution invariante.
Interpretation de $P^n$
Les puissances de la matrice de transition donnent les probabilites apres plusieurs transitions. C est l outil central pour faire evoluer un modele de Markov.
Coefficient de $P^n$
Le coefficient $(i,j)$ de $P^n$ s interprete comme la probabilite de passer de l etat $i$ a l etat $j$ en $n$ transitions.
Autrement dit, $P^n$ resume l evolution du systeme apres $n$ pas.
Dans une chaine a deux etats, cela signifie par exemple que le coefficient $(1,2)$ de $$P^3$$ est la probabilite de partir de l etat 1 et d arriver en etat 2 apres exactement trois transitions.
Idee de la preuve
Pour $n=1$, l interpretation est celle de la matrice de transition. Pour passer de $n$ a $n+1$, on utilise la loi des probabilites totales: on somme sur l etat intermediaire. C est exactement ce que realise le produit matriciel.
Calculer une distribution apres n pas
On procede souvent de la facon suivante:
- on ecrit $\pi_0$;
- on calcule $P^n$ ou on exploite une relation de recurrence;
- on obtient $\pi_n=\pi_0P^n$;
- on lit la probabilite recherchee dans le bon coefficient.
Attention au sens des lignes
Dans le programme, on utilise des matrices ligne pour les distributions: $\pi_n=\pi_0P^n$. Il faut donc rester coherent avec cette convention de multiplication.
Exemple de passage a deux pas
Si $\pi_0=(1,0)$ et $P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}$, alors $\pi_2=\pi_0P^2$. Le calcul de $P^2$ permet de lire directement les probabilites apres deux transitions.
Distribution invariante
Une distribution invariante est une distribution qui ne change plus lorsqu on applique la matrice de transition. C est l etat d equilibre de la chaine quand il existe.
Distribution invariante
Une matrice ligne $\pi$ est invariante si $\pi P=\pi$.
Elle verifie donc une equation de point fixe sur les probabilites.
Trouver une distribution invariante
On ecrit l equation $\pi P=\pi$ avec la condition supplementaire que les coefficients de $\pi$ somment a 1.
On obtient alors un petit systeme lineaire a resoudre.
Sens probabiliste
Si une chaine admet une distribution invariante, elle represente une repartition stable a long terme. Cela aide a comprendre l e comportement global du modele.
Cas a deux etats
Pour $P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}$, cherchons $\pi=(a,b)$ tel que $\pi P=\pi$ et $a+b=1$.
On obtient un systeme lineaire qui conduit a $a=\frac23$ et $b=\frac13$.
Convergence vers la distribution invariante (cas regulier)
Si une matrice de transition $P$ est reguliere (il existe $n$ tel que tous les coefficients de $P^n$ soient strictement positifs), alors :
- Il existe une unique distribution invariante $\pi$.
- Pour toute distribution initiale $\pi_0$, on a $\pi_0 P^n \to \pi$ quand $n \to +\infty$.
Cas a deux etats : si $P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}$ avec $0 < a,b < 1$, la distribution invariante est $\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)$.
Interpretation
La presence d une distribution invariante ne signifie pas automatiquement que toutes les chaines convergent vers elle dans le programme detaille. On l utilise surtout comme outil de calcul et de lecture asymptotique simple.
Resoudre concretement $\pi P = \pi$
On pose $$\pi=(a,b)$$ ou $$\pi=(a,b,c)$$ selon le nombre d etats. On ecrit ensuite $$\pi P=\pi$$ puis on ajoute la condition :
$$a+b=1 \quad \text{ou} \quad a+b+c=1.$$
On obtient un systeme lineaire. En pratique, une des equations est souvent redondante, donc la condition de somme egale a 1 est indispensable pour conclure.
Distribution invariante a trois etats
Pour une chaine a trois etats de matrice $$P,$$ on cherche $$\pi=(a,b,c)$$ tel que :
$$\pi P=\pi \qquad \text{et} \qquad a+b+c=1.$$
On obtient un petit systeme lineaire ; une equation est souvent redondante, puis la condition $$a+b+c=1$$ permet de terminer. Cette methode est exactement la meme qu a deux etats, avec une inconnue de plus.
Methode et reflexes
L essentiel sur les chaines de Markov tient en quelques reflexes: lire le graphe, construire la matrice, faire evoluer la distribution, puis verifier ou non l existence d un point fixe.
Lire un exercice
Devant un exercice de Markov, on commence par:
- identifier les etats;
- lire les probabilites de transition;
- ecrire la matrice $P$;
- calculer $\pi_n=\pi_0P^n$ ou resoudre $\pi P=\pi$.
Pourquoi les matrices sont utiles ici
La matrice rend les transitions successives compactes. Au lieu de refaire un arbre de probabilites a chaque pas, on manipule un seul objet algebraique.
Erreurs classiques
Les erreurs frequentes sont: inverser ligne et colonne, oublier que les lignes somment a 1, mal ordonner les etats, ou confondre $\pi_0P^n$ avec $P^n\pi_0$.
QCM du chapitre
-
Question 1. Le degre d un sommet est :
- A. le nombre d aretes incidentes a ce sommet
- B. le nombre total de sommets
- C. le nombre de matrices associees
- D. le nombre de chemins de longueur 2
Réponse. A. le nombre d aretes incidentes a ce sommet
Explication. Le degre compte les aretes qui touchent le sommet.
-
Question 2. Le coefficient (i,j) de la matrice d adjacence A^n compte :
- A. le degre du sommet i
- B. le nombre de chemins de longueur n de i vers j
- C. le nombre total d aretes
- D. une probabilite invariante
Réponse. B. le nombre de chemins de longueur n de i vers j
Explication. C est le lien fondamental entre graphes et calcul matriciel.
-
Question 3. Dans une chaine de Markov, la somme des probabilites sortantes d un etat vaut :
- A. 0
- B. 1
- C. 2
- D. cela depend du nombre d etats
Réponse. B. 1
Explication. Chaque ligne de la matrice de transition est une distribution de probabilite.
-
Question 4. La relation correcte est :
- A. $\pi_{n+1}=P\pi_n$
- B. $\pi_{n+1}=\pi_nP$
- C. $\pi_{n+1}=\pi_n+P$
- D. $\pi_{n+1}=P^n$
Réponse. B. $\pi_{n+1}=\pi_nP$
Explication. Dans ce cours, les distributions sont ecrites en matrice ligne.
-
Question 5. Une distribution invariante verifie :
- A. $\pi P=\pi$
- B. $P\pi=\pi$
- C. $\pi^2=\pi$
- D. $P^n=I$
Réponse. A. $\pi P=\pi$
Explication. C est la condition de point fixe de la dynamique.
-
Question 6. Le coefficient (i,j) de P^n represente :
- A. un nombre de sommets
- B. la probabilite de passer de i a j en n transitions
- C. le determinant de P
- D. le nombre d aretes incidentes a j
Réponse. B. la probabilite de passer de i a j en n transitions
Explication. P^n decrit les transitions apres n pas.
Exercices guidés
Exercice 1. Modeliser un reseau par une matrice d adjacence
A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}
-
Étape 1. Ecrire la matrice d adjacence.
Comme chaque sommet est relie aux deux autres, on obtient $$A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}.$$A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix} -
Étape 2. Interpreter le coefficient cherche dans A^2.
Le coefficient $$(1,3)$$ de $$A^2$$ compte les chemins de longueur 2 allant de 1 vers 3.(A^2)_{1,3} -
Étape 3. Conclure.
Il y a un unique chemin de longueur 2 de 1 vers 3, en passant par 2. Donc $$(A^2)_{1,3}=1.$$(A^2)_{1,3}=1
Exercice 2. Calculer une evolution a deux etats
\pi_1=\pi_0P
-
Étape 1. Utiliser directement la relation de recurrence.
On calcule $$\pi_1=(1,0)\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}=(0.8,0.2).$$\pi_1=(0.8,0.2)
-
Étape 2. Interpreter les deux coefficients.
Apres un pas, la probabilite d etre dans l etat 1 vaut 0.8 et celle d etre dans l etat 2 vaut 0.2.Etat 1 : 0.8,\quad Etat 2 : 0.2
Exercice 3. Trouver une distribution invariante
\pi P=\pi,\quad a+b=1
-
Étape 1. Ecrire l equation pi P = pi.
On pose $$\pi=(a,b).$$ Alors $$\pi P=(0.8a+0.4b,\ 0.2a+0.6b).$$(0.8a+0.4b,\ 0.2a+0.6b)
-
Étape 2. Utiliser la condition a+b=1.
Le systeme donne $$0.8a+0.4b=a,$$ soit $$a=2b.$$ Avec $$a+b=1,$$ on obtient $$b=\frac13$$ et $$a=\frac23.$$a=\frac23,\quad b=\frac13
-
Étape 3. Conclure.
La distribution invariante est donc $$\pi=\left(\frac23,\frac13\right).$$\pi=\left(\frac23,\frac13\right)
Exercice 4. Compter des chemins de longueur 3
(A^3)_{1,2}
-
Étape 1. Ecrire la matrice d adjacence.
Dans l ordre $$1,2,3,4,$$ on obtient $$A=\begin{pmatrix}0&1&1&0\\1&0&0&1\\1&0&0&1\\0&1&1&0\end{pmatrix}. $$A=\begin{pmatrix}0&1&1&0\\1&0&0&1\\1&0&0&1\\0&1&1&0\end{pmatrix} -
Étape 2. Utiliser l interpretation de $$A^3$$.
Le coefficient $$ (1,2) $$ de $$A^3$$ compte les chemins de longueur 3 de 1 vers 2. En calculant, on trouve $$ (A^3)_{1,2}=4.$$ -
Étape 3. Conclure.
Il y a donc $$4$$ chemins de longueur $$3$$ allant de $$1$$ vers $$2.$$(A^3)_{1,2}=4
Exercice 5. Calculer une distribution apres deux etapes
\pi_1=\pi_0P,\quad \pi_2=\pi_1P
-
Étape 1. Calculer $$\pi_1$$.
Comme $$\pi_0=(1,0,0),$$ on lit la premiere ligne de $$P$$ : $$\pi_1=\left(\frac12,\frac12,0\right).$$\pi_1=\left(\frac12,\frac12,0\right)
-
Étape 2. Calculer $$\pi_2$$.
On multiplie $$\pi_1$$ par $$P$$ et on obtient $$\pi_2=\left(\frac38,\frac12,\frac18\right).$$\pi_2=\left(\frac38,\frac12,\frac18\right)
-
Étape 3. Lire la probabilite demandee.
La probabilite d etre dans l etat 3 apres deux etapes est la troisieme coordonnee de $$\pi_2,$$ soit $$\dfrac18.$$\mathbb P(X_2=3)=\frac18
Exercice 6. Trouver une distribution invariante a trois etats
\pi P=\pi,\quad a+b+c=1
-
Étape 1. Ecrire les equations.
La relation $$\pi P=\pi$$ donne : $$\begin{cases}0.5a+0.2b=a\\0.5a+0.5b+0.4c=b\\0.3b+0.6c=c\end{cases}$$ puis on ajoute $$a+b+c=1.$$ -
Étape 2. Simplifier.
Les deux premieres relations donnent $$a=0.4b$$ et $$c=0.75b.$$ -
Étape 3. Utiliser la somme egale a 1.
On a donc $$0.4b+b+0.75b=1,$$ soit $$2.15b=1.$$ Ainsi $$b=\dfrac{20}{43},$$ puis $$a=\dfrac{8}{43}$$ et $$c=\dfrac{15}{43}.$$\pi=\left(\frac{8}{43},\frac{20}{43},\frac{15}{43}\right)