Maths Expertes · Math@mine
Les météorologues modélisent le temps par une chaîne de Markov : si aujourd’hui est beau, demain est beau avec probabilité 0,8 et pluvieux avec 0,2 ; si pluvieux, demain est beau avec 0,4 et pluvieux avec 0,6.
Euler (1736) résout le problème des ponts de Königsberg — peut-on traverser les sept ponts de la ville en ne passant qu’une fois sur chacun ? — en inventant la théorie des graphes. Al-Kindi (IXe siècle) utilise implicitement des graphes de connexions dans son analyse fréquentielle de textes chiffrés.
Andreï Markov (début XXe siècle) développe ses chaînes pour modéliser l’alternance consonnes-voyelles dans la langue russe — un problème linguistique qui débouche sur une théorie probabiliste fondamentale, aujourd’hui au cœur des moteurs de recherche et de l’intelligence artificielle.
Reprenons la météo de l’introduction. On note \(T = \begin{pmatrix}0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6\end{pmatrix}\) la matrice de transition (ligne 1 = beau, ligne 2 = pluie).
Un graphe orienté \(G = (S, A)\) est un ensemble de sommets \(S\) reliés par des arcs orientés \(A \subseteq S \times S\).
On note \(s_i \to s_j\) s’il existe un arc du sommet \(s_i\) vers le sommet \(s_j\).
Arcs : \(1\to2\), \(1\to3\), \(2\to3\), \(2\to4\), \(3\to4\), \(4\to4\) (boucle).
La matrice d’adjacence d’un graphe à \(n\) sommets est la matrice \(M = (m_{ij})_{1\le i,j\le n}\) où :
\(m_{ij} = \begin{cases}1 & \text{si } s_i \to s_j \\ 0 & \text{sinon}\end{cases}\)
Pour le graphe ci-dessus (sommets 1, 2, 3, 4) :
\(M = \begin{pmatrix}0&1&1&0\\0&0&1&1\\0&0&0&1\\0&0&0&1\end{pmatrix}\)
Ligne \(i\) = arcs partant de \(s_i\). Colonne \(j\) = arcs arrivant en \(s_j\).
Le coefficient \((M^k)_{ij}\) compte le nombre de chemins de longueur \(k\) allant de \(s_i\) vers \(s_j\).
Initialisation (\(k = 1\)). \(M_{ij}\) vaut 1 s’il existe un arc \(s_i \to s_j\), 0 sinon. Or un chemin de longueur 1 de \(s_i\) à \(s_j\) est exactement un arc \(s_i \to s_j\). Donc \(M_{ij}\) compte bien les chemins de longueur 1.
Hérédité. Supposons que \((M^k)_{ij}\) compte les chemins de longueur \(k\) de \(s_i\) à \(s_j\). Par définition du produit matriciel :
\((M^{k+1})_{ij} = (M^k \cdot M)_{ij} = \sum_{\ell=1}^{n} (M^k)_{i\ell} \cdot M_{\ell j}.\)
Interprétation : un chemin de longueur \(k+1\) de \(s_i\) à \(s_j\) se décompose de façon unique en un chemin de longueur \(k\) de \(s_i\) à un sommet intermédiaire \(s_\ell\) suivi d' un arc \(s_\ell \to s_j\).
Pour chaque \(\ell\), le nombre de tels chemins est \((M^k)_{i\ell} \times M_{\ell j}\) (par hypothèse de récurrence et initialisation). En sommant sur \(\ell\), on obtient exactement \((M^{k+1})_{ij}\). ∎
Avec la matrice ci-dessus, \((M^2)_{14}\) compte les chemins de longueur 2 de 1 vers 4 : il y en a 2 (\(1\to2\to4\) et \(1\to3\to4\)).
Un graphe probabiliste est un graphe orienté où chaque arc \(s_i \to s_j\) porte un poids \(p_{ij} \in [0,1]\) tel que pour chaque sommet \(s_i\) :
\(\sum_{j=1}^n p_{ij} = 1\)
On dit que \(p_{ij}\) est la probabilité de transition de \(s_i\) vers \(s_j\).
Matrice de transition : \(T = \begin{pmatrix}0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6\end{pmatrix}\) où la ligne \(i\) représente les probabilités depuis l’état \(i\).
Vérification : chaque ligne somme à 1 : \(0{,}7 + 0{,}3 = 1\), \(0{,}4 + 0{,}6 = 1\). ✓
Une matrice \(T\) à coefficients dans \([0,1]\) est dite stochastique (ou matrice de transition) si la somme de chaque ligne vaut 1.
Une suite de variables aléatoires \((X_n)_{n\ge 0}\) à valeurs dans \(\{s_1,\ldots,s_k\}\) est une chaîne de Markov de matrice de transition \(T\) si, pour tout \(n\) et tous états \(i, j\) :
\(\mathbb{P}(X_{n+1}=s_j \mid X_n = s_i) = p_{ij}\)
La probabilité du prochain état ne dépend que de l’état actuel, pas du passé : c’est la propriété de Markov (absence de mémoire).
À l’instant \(n\), la distribution de probabilité est le vecteur ligne :
\(\pi_n = \bigl(\mathbb{P}(X_n=s_1),\ \ldots,\ \mathbb{P}(X_n=s_k)\bigr)\)
où chaque coordonnée est la probabilité d’être dans l’état correspondant à l’instant \(n\).
Si \(\pi_0\) est la distribution initiale et \(T\) la matrice de transition, alors :
\(\pi_n = \pi_0 \cdot T^n\)
La distribution à l’instant \(n\) est obtenue en multipliant la distribution initiale par la \(n\)-ième puissance de \(T\).
Initialisation : Pour \(n=0\), \(\pi_0 = \pi_0 \cdot T^0 = \pi_0 \cdot I = \pi_0\). ✓
Hérédité : Si \(\pi_n = \pi_0 T^n\), alors :
\(\mathbb{P}(X_{n+1}=s_j) = \sum_i \mathbb{P}(X_{n+1}=s_j \mid X_n=s_i)\,\mathbb{P}(X_n=s_i) = \sum_i \pi_n(i)\, p_{ij}\)
En notation matricielle : \(\pi_{n+1} = \pi_n \cdot T = \pi_0 T^n \cdot T = \pi_0 T^{n+1}\). ✓
Si aujourd’hui il fait soleil, \(\pi_0 = (1, 0)\). Calculer la distribution à \(n=2\).
\(\pi_2 = \pi_0 \cdot T^2 = (1,0)\begin{pmatrix}0{,}7&0{,}3\\0{,}4&0{,}6\end{pmatrix}^2\)
\(T^2 = \begin{pmatrix}0{,}49+0{,}12 & 0{,}21+0{,}18 \\ 0{,}28+0{,}24 & 0{,}12+0{,}36\end{pmatrix} = \begin{pmatrix}0{,}61 & 0{,}39 \\ 0{,}52 & 0{,}48\end{pmatrix}\)
\(\pi_2 = (0{,}61,\ 0{,}39)\) : après 2 jours, il y a 61 % de chance de soleil.
Un vecteur ligne \(\pi = (\pi_1, \ldots, \pi_k)\) est une distribution stationnaire de la chaîne de Markov si :
La condition \(\pi T = \pi\) signifie que \(\pi\) est un vecteur propre à gauche de \(T\) pour la valeur propre 1. Toute matrice stochastique a 1 comme valeur propre.
Les notions de valeur propre et de vecteur propre sont définies au chapitre 6, section 6.6 (Hors programme — Valeurs propres et diagonalisation). Elles ne sont pas exigibles au programme, mais eclairent le phénomène de stationnarité.
Pour trouver \(\pi = (\pi_1, \pi_2)\) pour une chaîne à 2 états :
On cherche \((\pi_S, \pi_P)\) avec \(\pi_S + \pi_P = 1\) et \((\pi_S, \pi_P)\begin{pmatrix}0{,}7&0{,}3\\0{,}4&0{,}6\end{pmatrix} = (\pi_S, \pi_P)\).
Première équation : \(0{,}7\pi_S + 0{,}4\pi_P = \pi_S\), soit \(-0{,}3\pi_S + 0{,}4\pi_P = 0\), soit \(\pi_P = \frac{3}{4}\pi_S\).
Avec \(\pi_S + \pi_P = 1\) : \(\pi_S + \frac{3}{4}\pi_S = 1\), donc \(\frac{7}{4}\pi_S = 1\), donc \(\pi_S = \frac{4}{7}\) et \(\pi_P = \frac{3}{7}\).
Distribution stationnaire : \(\pi = \left(\dfrac{4}{7},\ \dfrac{3}{7}\right) \approx (0{,}571,\ 0{,}429)\).
À long terme, il y a soleil environ 57 % du temps, quelle que soit la météo de départ.
Si une chaîne de Markov est irréductible et apériodique, alors :
Résultat admis. Ce théorème (appelé théorème de Perron-Frobenius ou théorème ergodique) est admis en Maths Expertes. Sa démonstration rigoureuse fait appel à la théorie spectrale des matrices positives et dépasse le cadre du lycée.
Les idées ci-dessous utilisent des notions (valeur propre, vecteur propre, diagonalisation, espace propre) définies au chapitre 6, section 6.6 (Hors programme). Elles ne sont pas exigibles, mais donnent l’intuition de la convergence.
Idée (cas à 2 états, par diagonalisation). On peut vérifier la convergence dans le cas simple d’une matrice \(T = \begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}\) avec \(0 < a, b < 1\). Les valeurs propres de \(T\) sont \(1\) et \(1-a-b\), et \(|1-a-b| < 1\). Par diagonalisation (ch6 §6.6), \(T^n\) se décompose en une partie constante (associée à la valeur propre \(1\), qui donne \(\pi\)) et une partie qui décroît géométriquement comme \((1-a-b)^n \to 0\). D’où \(\pi_0 T^n \to \pi\).
Idée générale. Pour une matrice stochastique irréductible et apériodique, on montre que \(1\) est valeur propre simple et dominante (toutes les autres valeurs propres \(\lambda\) vérifient \(|\lambda| < 1\)). L’espace propre associé à \(1\) fournit l’unique distribution stationnaire, et \(T^n\) converge vers le projecteur sur cet espace. ∎
On modélise le web comme un graphe orienté : les sommets sont des pages, les arcs sont des hyperliens. Un internaute qui navigue aléatoirement en suivant les liens suit une chaîne de Markov.
La distribution stationnaire \(\pi\) donne le PageRank de chaque page : \(\pi_i\) est la probabilité qu’un internaute se trouve sur la page \(i\) après une longue navigation aléatoire.
Google utilise une variante pondérée : l’internaute a une probabilité \(\alpha = 0{,}85\) de suivre un lien, et \(1-\alpha = 0{,}15\) de téléporter vers une page aléatoire.
Chaque mois, un client utilise l’application A ou B. La matrice de transition est :
\(T = \begin{pmatrix}0{,}8 & 0{,}2 \\ 0{,}3 & 0{,}7\end{pmatrix}\) (ligne = état actuel, colonne = état suivant)
Distribution stationnaire : en résolvant \(\pi T = \pi\), on trouve \(\pi = (0{,}6,\ 0{,}4)\). À long terme, A capte 60 % du marché.
On considère un graphe orienté à 4 sommets \(S_1, S_2, S_3, S_4\). Programmer les fonctions mat_mul et mat_add pour les matrices (listes de listes), puis :
Rappel : le coefficient \((i,j)\) de \(M^k\) compte le nombre de chemins de longueur \(k\) de \(S_i\) vers \(S_j\). Si \(C_{ij} > 0\), il existe un chemin de \(S_i\) vers \(S_j\).
On modélise la météo par une chaîne de Markov à deux états (Soleil, Pluie) avec la matrice de transition \(T = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}\). Écrire :
vec_mat(v, T) : calcule le produit \(\pi \cdot T\) d’un vecteur ligne par une matriceRappel : \(\pi_{n+1} = \pi_n \cdot T\). La distribution stationnaire \(\pi^*\) vérifie \(\pi^* T = \pi^*\).
Écrire une fonction distribution_stationnaire(T, iterations=1000) qui calcule la distribution stationnaire d’une chaîne de Markov par itération de puissance :
Tester sur trois exemples : la météo \(2 \times 2\), un partage de marché \(2 \times 2\), et une chaîne à 3 états.
Rappel : la distribution stationnaire est l’unique vecteur \(\pi^*\) tel que \(\pi^* T = \pi^*\) et \(\sum \pi^*_i = 1\). L’itération converge pour toute matrice de transition irréductible et apériodique.
Simuler une chaîne de Markov (météo) sur 10 000 jours par la méthode de Monte Carlo :
transition(etat, T) qui tire au hasard l’état suivant selon la ligne \(T[\text{etat}]\) de la matrice de transitionRappel Python : random.random() renvoie un flottant dans \([0, 1[\). Pour tirer selon une loi discrète, on utilise les sommes cumulées des probabilités. random.seed(42) fixe la graine pour la reproductibilité.
Implémenter une version simplifiée de l’algorithme PageRank de Google sur un réseau de 4 pages web :
Rappel : le facteur d’amortissement \(\alpha\) modélise la probabilité qu’un internaute suive un lien (plutôt que de choisir une page au hasard). \(J\) est la matrice dont tous les coefficients valent 1.
Observe comment le vecteur de distribution converge vers la distribution stationnaire en multipliant par la matrice de transition.
| Notion | Définition / Formule | Piège à éviter |
|---|---|---|
| Graphe | Ensemble de sommets reliés par des arêtes (non orienté) ou des arcs (orienté) | Ne pas confondre arête et arc |
| Matrice d’adjacence \(M\) | \(m_{ij} = 1\) si arête (ou arc) de \(i\) à \(j\), 0 sinon | Symétrique seulement si le graphe est non orienté |
| Chaîne de longueur \(k\) | Le coefficient \((i,j)\) de \(M^k\) donne le nombre de chemins de longueur \(k\) de \(i\) à \(j\) | Bien vérifier la convention ligne/colonne |
| Matrice de transition \(T\) | \(t_{ij} = P(j \to i)\), chaque colonne a une somme égale à 1 | Attention au sens lignes/colonnes selon la convention choisie |
| État stable \(\pi\) | \(T\pi = \pi\) et \(\displaystyle\sum_i \pi_i = 1\) | Ne pas oublier la condition de normalisation \(\sum \pi_i = 1\) |
\(T^2 = \begin{pmatrix}0{,}72 & 0{,}28 \\ 0{,}56 & 0{,}44\end{pmatrix}\). Le coefficient (1,1) = 0,72 est la probabilité qu’il fasse beau dans 2 jours sachant qu’il fait beau aujourd’hui.
En calculant les puissances successives, on observe que \(T^n\) converge vers \(\begin{pmatrix}2/3 & 1/3 \\ 2/3 & 1/3\end{pmatrix}\). Toutes les lignes deviennent identiques ! À long terme, il fait beau \(2/3\) du temps, quelle que soit la météo initiale. C’est la distribution stationnaire — notion que nous étudierons dans ce chapitre.
Graphes et Markov : teste d’abord ton intuition.
« Dans une matrice d’adjacence, la somme de chaque ligne vaut toujours 1. »
Cette affirmation est-elle correcte ?
C’est vrai pour une matrice stochastique (matrice de transition), pas pour une matrice d’adjacence. Dans une matrice d’adjacence, les coefficients sont 0 ou 1, et la somme d’une ligne donne le nombre de successeurs du sommet.
Mini-test : un sommet a 3 arcs sortants. La somme de sa ligne dans la matrice d’adjacence est :
Voir section 1
« Pour trouver la distribution stationnaire, on résout \(T \cdot \pi = \pi\) (matrice × vecteur colonne). »
Cette formulation est-elle correcte ?
Ça dépend de la convention ! Si \(T\) est construite avec les probabilités en ligne (convention du cours), alors \(\pi\) est un vecteur ligne et on écrit \(\pi \cdot T = \pi\). Si on utilise la convention « en colonne » (certains manuels), c’est \(T \cdot \pi = \pi\).
Mélanger les deux conventions donne un résultat faux.
Mini-test : dans notre convention (probas en ligne), \(\pi\) est :
Voir section 4
« Toute chaîne de Markov converge vers une distribution stationnaire. »
Cette affirmation est-elle vraie ?
Non ! Il faut que la chaîne soit irréductible (on peut passer de tout état à tout état) et apériodique (les retours à un état ne se font pas à intervalles réguliers fixes).
Contre-exemple : \(T = \begin{pmatrix}0&1\\1&0\end{pmatrix}\). On alterne entre les deux états sans jamais converger : \(T^{2k} = I\) et \(T^{2k+1} = T\).
Mini-test : la chaîne \(T = \begin{pmatrix}0&1\\1&0\end{pmatrix}\) est :
Voir section 4
« Le coefficient \((i,j)\) de \(M^k\) donne le nombre de chemins de longueur \(k\) de \(j\) vers \(i\). »
L’ordre est-il correct ?
C’est dans l’autre sens : le coefficient \((i,j)\) de \(M^k\) donne le nombre de chemins de longueur \(k\) de \(i\) vers \(j\) (ligne = départ, colonne = arrivée).
Mini-test : \((M^3)_{2,4} = 5\). Il y a 5 chemins de longueur 3 :
Voir section 1
« La distribution stationnaire change selon l’état de départ. »
Cette affirmation est-elle vraie ?
Pour une chaîne irréductible et apériodique, la distribution stationnaire est unique et indépendante de l’état initial. C’est ce qu’on observe avec la météo : qu’il fasse beau ou qu’il pleuve aujourd’hui, à long terme la proportion est toujours 2/3 beau, 1/3 pluie.
Mini-test : on démarre par temps pluvieux au lieu de beau. À long terme :
Voir section 4
« Dans une matrice de transition (stochastique), la somme des coefficients de chaque ligne vaut 1. »
Cette propriété est-elle vraie ?
C’est vrai ! Chaque ligne d’une matrice stochastique contient les probabilités de transition depuis un état donné vers tous les états possibles. Comme ce sont des probabilités qui couvrent tous les cas, leur somme vaut nécessairement 1.
Ne pas confondre avec la matrice d’adjacence (piège 1) où la somme donne le nombre de successeurs.
Mini-test : \(T = \begin{pmatrix}0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6\end{pmatrix}\). Est-elle stochastique ?
Voir section 2