Lycée · Terminale · Maths expertes (option Tle)
Graphes probabilistes et chaînes de Markov
Modélisation de phénomènes aléatoires évolutifs par des graphes probabilistes et des matrices de transition (programme Maths expertes Tle)
À propos de cette page
Ce cours de maths expertes (option tle) en terminale sur « Graphes probabilistes et chaînes de Markov » suit le programme officiel de maths expertes (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Graphes probabilistes — définition et vocabulaire, Matrice de transition, Chaînes de Markov — définition et propriété sans mémoire, Distribution d'état à l'instant n. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths expertes (option tle).
1
Graphes probabilistes — définition et vocabulaire
Un graphe probabiliste est un graphe orienté dans lequel :
- chaque sommet représente un état possible du système ;
- chaque arc de l'état $i$ vers l'état $j$ porte un poids $p_{ij} \in [0,1]$, appelé probabilité de transition de $i$ vers $j$ ;
- pour tout état $i$, la somme des probabilités des arcs issus de $i$ vaut $1$.
Définition. Un graphe probabiliste à $n$ états est un graphe orienté pondéré $(S, A)$ avec $S = \{E_1, E_2, \ldots, E_n\}$ et, pour tout $i$, $\displaystyle\sum_{j=1}^{n} p_{ij} = 1$ (les $p_{ij} \geq 0$).
On représente souvent ce graphe avec des flèches numérotées par les probabilités de passage.
Exemple. Une urne contient des boules rouges et bleues. À chaque étape, on tire une boule et on note sa couleur.
- Si on a tiré rouge : probabilité $0{,}7$ de retirer rouge, $0{,}3$ de tirer bleu.
- Si on a tiré bleu : probabilité $0{,}4$ de retirer rouge, $0{,}6$ de tirer bleu.
Schéma du graphe probabiliste à deux états (Rouge et Bleu). Chaque arc sortant porte une probabilité, la somme des probabilités sortant d'un nœud est toujours 1.
2
Matrice de transition
À tout graphe probabiliste à $n$ états, on associe une matrice de transition (ou matrice stochastique) $M$ de taille $n \times n$.
Définition. La matrice de transition $M = (p_{ij})$ est telle que $p_{ij}$ est la probabilité de passer de l'état $E_i$ à l'état $E_j$. La ligne $i$ correspond à l'état de départ $E_i$; la colonne $j$ à l'état d'arrivée $E_j$. La somme de chaque ligne vaut $1$ : $\displaystyle\sum_{j=1}^{n} p_{ij} = 1$.
Exemple (suite). Pour l'urne rouge/bleu (état 1 = R, état 2 = B) :$$M = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$$Ligne 1 : depuis R, on va vers R avec proba 0,7 et vers B avec proba 0,3. Vérification : $0{,}7 + 0{,}3 = 1$. Ligne 2 : depuis B, on va vers R avec proba 0,4 et vers B avec proba 0,6.
Astuce. Une matrice stochastique a toutes ses entrées dans $[0,1]$ et chaque somme de ligne est égale à $1$. Ne pas confondre avec la somme des colonnes (qui peut être différente de 1).
Attention ! La convention lignes/colonnes est importante : la ligne $i$ décrit les transitions depuis l'état $i$. Certains livres utilisent la convention transposée (colonnes = départ) — bien vérifier l'convention utilisée.
3
Chaînes de Markov — définition et propriété sans mémoire
On modélise l'évolution d'un système aléatoire au cours du temps par une suite de variables aléatoires $(X_0, X_1, X_2, \ldots)$ à valeurs dans un ensemble fini d'états $\{E_1, \ldots, E_n\}$.
Définition — Chaîne de Markov. La suite $(X_k)_{k \geq 0}$ est une chaîne de Markov homogène si :
1° Les probabilités de transition $p_{ij} = P(X_{k+1} = E_j \mid X_k = E_i)$ ne dépendent pas de $k$ (homogénéité temporelle).
2° Propriété de Markov (sans mémoire) : pour tout $k \geq 1$,$$P(X_{k+1} = E_j \mid X_k = E_i, X_{k-1} = E_{i_{k-1}}, \ldots, X_0 = E_{i_0}) = P(X_{k+1} = E_j \mid X_k = E_i) = p_{ij}$$L'état futur ne dépend que de l'état présent, pas du passé.
1° Les probabilités de transition $p_{ij} = P(X_{k+1} = E_j \mid X_k = E_i)$ ne dépendent pas de $k$ (homogénéité temporelle).
2° Propriété de Markov (sans mémoire) : pour tout $k \geq 1$,$$P(X_{k+1} = E_j \mid X_k = E_i, X_{k-1} = E_{i_{k-1}}, \ldots, X_0 = E_{i_0}) = P(X_{k+1} = E_j \mid X_k = E_i) = p_{ij}$$L'état futur ne dépend que de l'état présent, pas du passé.
Exemple. La météo peut être modélisée ainsi : les états sont « Soleil » (S) et « Pluie » (P). Si aujourd'hui il fait soleil, demain il y a 80% de chance de soleil et 20% de pluie. Si aujourd'hui il pleut, demain il y a 50% de chance de soleil et 50% de pluie. Ceci définit une chaîne de Markov à 2 états (en supposant que la météo de demain ne dépend que de celle d'aujourd'hui).
Astuce. La propriété de Markov se résume par : « Le futur est indépendant du passé, conditionnellement au présent. »
4
Distribution d'état à l'instant n
On note la distribution initiale (à l'instant $k=0$) comme un vecteur ligne :
$$\pi^{(0)} = \bigl(P(X_0 = E_1),\; P(X_0 = E_2),\; \ldots,\; P(X_0 = E_n)\bigr)$$dont la somme des composantes vaut $1$.
Théorème — Distribution à l'instant $n$. Pour une chaîne de Markov homogène de matrice de transition $M$,$$\pi^{(n)} = \pi^{(0)} \cdot M^n$$où $\pi^{(n)}_j = P(X_n = E_j)$. Autrement dit, on multiplie le vecteur initial à droite par la $n$-ième puissance de la matrice de transition.
Calcul explicite. Reprenons l'urne (R, B), $M = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$.
Supposons $\pi^{(0)} = (1, 0)$ (on part de R). Après une étape :
$\pi^{(1)} = (1, 0) \cdot M = (0{,}7,\; 0{,}3)$.
Après deux étapes :
$\pi^{(2)} = (0{,}7,\; 0{,}3) \cdot M = (0{,}7 \times 0{,}7 + 0{,}3 \times 0{,}4,\; 0{,}7 \times 0{,}3 + 0{,}3 \times 0{,}6) = (0{,}49 + 0{,}12,\; 0{,}21 + 0{,}18) = (0{,}61,\; 0{,}39)$.
Supposons $\pi^{(0)} = (1, 0)$ (on part de R). Après une étape :
$\pi^{(1)} = (1, 0) \cdot M = (0{,}7,\; 0{,}3)$.
Après deux étapes :
$\pi^{(2)} = (0{,}7,\; 0{,}3) \cdot M = (0{,}7 \times 0{,}7 + 0{,}3 \times 0{,}4,\; 0{,}7 \times 0{,}3 + 0{,}3 \times 0{,}6) = (0{,}49 + 0{,}12,\; 0{,}21 + 0{,}18) = (0{,}61,\; 0{,}39)$.
Attention ! On multiplie $\pi^{(0)}$ à droite par $M$, ce qui correspond à la convention « ligne = état de départ ». Avec la convention transposée, on multiplierait à gauche par $M^T$.
Convergence de la probabilité d'être en état Rouge vers la valeur stationnaire $4/7 \approx 0{,}571$ à partir de l'état initial $R$ (courbe bleue) et comparaison avec la limite (pointillé).
5
Comportement asymptotique — état stationnaire
Sous certaines conditions (chaîne régulière : il existe un entier $k$ tel que $M^k$ n'a que des entrées strictement positives), la distribution $\pi^{(n)}$ converge vers une distribution stationnaire (ou limite) $\pi^*$ indépendante de $\pi^{(0)}$.
Définition — Distribution stationnaire. Un vecteur ligne $\pi^* = (\pi_1^*, \ldots, \pi_n^*)$ est une distribution stationnaire (ou invariante) de la chaîne de Markov de matrice $M$ si :$$\pi^* \cdot M = \pi^* \quad \text{et} \quad \sum_{i=1}^{n} \pi_i^* = 1$$
Méthode de résolution. Pour trouver $\pi^*$ :
- Écrire le système $\pi^* \cdot M = \pi^*$, soit $(\pi_1^*, \ldots, \pi_n^*) \cdot M = (\pi_1^*, \ldots, \pi_n^*)$.
- Ajouter la condition de normalisation $\pi_1^* + \pi_2^* + \cdots + \pi_n^* = 1$.
- Résoudre le système linéaire (remplacer une équation redondante par la normalisation).
Calcul pour l'urne (R, B). On pose $\pi^* = (a, b)$ avec $a + b = 1$.
Condition : $(a, b) \cdot \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix} = (a, b)$.
Première composante : $0{,}7a + 0{,}4b = a$, soit $-0{,}3a + 0{,}4b = 0$, d'où $b = \frac{3}{4}a$.
Avec $a + b = 1$ : $a + \frac{3}{4}a = 1$, soit $\frac{7}{4}a = 1$, d'où $a = \frac{4}{7}$, $b = \frac{3}{7}$.
L'état stationnaire est $\pi^* = \left(\frac{4}{7}, \frac{3}{7}\right) \approx (0{,}571;\; 0{,}429)$.
Condition : $(a, b) \cdot \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix} = (a, b)$.
Première composante : $0{,}7a + 0{,}4b = a$, soit $-0{,}3a + 0{,}4b = 0$, d'où $b = \frac{3}{4}a$.
Avec $a + b = 1$ : $a + \frac{3}{4}a = 1$, soit $\frac{7}{4}a = 1$, d'où $a = \frac{4}{7}$, $b = \frac{3}{7}$.
L'état stationnaire est $\pi^* = \left(\frac{4}{7}, \frac{3}{7}\right) \approx (0{,}571;\; 0{,}429)$.
Attention ! L'état stationnaire existe et est unique uniquement si la chaîne est irréductible (on peut atteindre tout état depuis tout état) et apériodique. Ces conditions sont souvent vérifiées dans les exemples du programme.
| Condition | Signification | Conséquence |
|---|---|---|
| Irréductibilité | Tout état est accessible depuis tout autre état | Il existe un unique état stationnaire |
| Apériodicité | La chaîne ne tourne pas en boucles de longueur fixe | Convergence vers l'état stationnaire |
| Régularité | $\exists k : M^k$ n'a que des entrées $\gt 0$ | Implique irréductibilité + apériodicité |
6
Exemples et modélisation
Les chaînes de Markov permettent de modéliser de nombreuses situations réelles. Voici deux exemples développés.
Exemple 1 — Modèle de fidélité client. Une enseigne suit chaque mois si un client achète (A) ou non (N). La matrice de transition est :$$M = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$$À long terme, quelle fraction des clients achète chaque mois ?
On résout $\pi \cdot M = \pi$ avec $\pi_A + \pi_N = 1$ : $0{,}8\pi_A + 0{,}5\pi_N = \pi_A$, d'où $0{,}5\pi_N = 0{,}2\pi_A$, soit $\pi_N = 0{,}4\pi_A$. Avec $\pi_A + \pi_N = 1$ : $\pi_A = \frac{1}{1{,}4} = \frac{5}{7} \approx 71{,}4\%$.
On résout $\pi \cdot M = \pi$ avec $\pi_A + \pi_N = 1$ : $0{,}8\pi_A + 0{,}5\pi_N = \pi_A$, d'où $0{,}5\pi_N = 0{,}2\pi_A$, soit $\pi_N = 0{,}4\pi_A$. Avec $\pi_A + \pi_N = 1$ : $\pi_A = \frac{1}{1{,}4} = \frac{5}{7} \approx 71{,}4\%$.
Exemple 2 — Génétique. Un gène peut être à l'état dominant (D) ou récessif (R). La matrice de transition entre générations est :$$M = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}3 & 0{,}7 \end{pmatrix}$$Au bout de nombreuses générations, l'état stationnaire $\pi^*$ vérifie $0{,}4\pi_D = 0{,}3\pi_R$ et $\pi_D + \pi_R = 1$, ce qui donne $\pi_D = \frac{3}{7}$, $\pi_R = \frac{4}{7}$.
Démarche de modélisation.
- Identifier les états possibles du système.
- Déterminer les probabilités de transition (à partir de données, de modèles, etc.).
- Vérifier que chaque somme de ligne vaut 1.
- Choisir la distribution initiale $\pi^{(0)}$.
- Calculer $\pi^{(n)} = \pi^{(0)} \cdot M^n$ pour les premières étapes.
- Calculer l'état stationnaire $\pi^*$ pour le comportement à long terme.
Convergence vers l'état stationnaire $\pi_A = 5/7 \approx 71{,}4\%$ pour les deux distributions initiales possibles (départ en état A ou N).
À retenir
- À retenir — Graphes probabilistes et chaînes de Markov :
- Un graphe probabiliste est un graphe orienté où chaque arc porte une probabilité de transition et la somme des probabilités sortant d'un sommet vaut 1.
- La matrice de transition $M$ a ses entrées dans $[0,1]$ et chaque somme de ligne vaut 1. La ligne $i$ décrit les transitions depuis l'état $i$.
- Propriété de Markov : l'état futur ne dépend que de l'état présent, pas du passé.
- La distribution à l'instant $n$ : $\pi^{(n)} = \pi^{(0)} \cdot M^n$.
- L'état stationnaire $\pi^*$ vérifie $\pi^* \cdot M = \pi^*$ et $\sum_i \pi^*_i = 1$ ; pour une chaîne régulière, $\pi^{(n)} \to \pi^*$ quelle que soit la distribution initiale.
Bloqué sur ce chapitre ?
Cours particuliers de maths expertes (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs