Maths expertes, Terminale • Exercices corrigés à Montréal

Fiche de révision : graphes et chaînes de Markov (maths expertes)

Q: Que compte le coefficient d'une puissance de la matrice d'adjacence ?

Le nombre de chemins de longueur égale à l'exposant entre les deux sommets correspondants, qu'on appelle aussi chaînes quand le graphe n'est pas orienté. Un chemin a le droit de repasser par un sommet déjà visité et de réemprunter une arête : c'est justement ce qui rend le comptage accessible par un simple produit de matrices.

Q: Dans quel sens multiplie-t-on une distribution par la matrice de transition ?

Dans la convention du programme français, la distribution s'écrit en ligne et se multiplie à droite : la distribution suivante est la distribution actuelle multipliée par la matrice. C'est cohérent avec le fait que chaque ligne de la matrice somme à un, ce qui garantit que le résultat reste une distribution.

Q: Pourquoi faut-il ajouter la condition de somme égale à un pour l'état stable ?

Parce que le système donné par l'égalité de la distribution et de son image est homogène : tout multiple d'une solution est encore solution. Il définit donc une direction, pas un point précis. La condition de normalisation choisit parmi tous ces multiples celui qui est une véritable loi de probabilité.

Q: Toute chaîne de Markov converge-t-elle vers un état stable ?

Non. La convergence est garantie quand tous les coefficients de transition sont strictement compris entre zéro et un. La matrice qui échange systématiquement les deux états est bien une matrice de transition, elle possède même une distribution invariante, et pourtant ses puissances alternent indéfiniment sans converger.

Q: La limite dépend-elle de la répartition de départ ?

Non, lorsque la convergence a lieu. L'écart à l'équilibre est multiplié à chaque étape par la même raison, de module inférieur à un, quel que soit le point de départ. La distribution initiale n'influence donc que la vitesse d'approche, jamais la limite atteinte.

Q: Que dit le lemme des poignées de main ?

Que la somme des degrés de tous les sommets vaut exactement le double du nombre d'arêtes, puisque chaque arête est comptée une fois à chacune de ses deux extrémités. Il en découle que le nombre de sommets de degré impair est toujours pair, ce qui permet de rejeter certains graphes comme impossibles.

Les graphes et les chaînes de Markov ferment l'option maths expertes, et ils réunissent tout ce qui précède : matrices, puissances, suites et probabilités. Le calcul y est court, la mise en place décide de tout : quelle matrice, dans quel sens, et avec quelle condition supplémentaire.

Cette fiche liste les erreurs qui reviennent, avec la phrase exacte qui les remet, la convention d'écriture des distributions, l'arbre des questions de graphes, les deux rédactions que le programme demande, comptage des chemins et graphe pondéré, et une chaîne de Markov à deux états décortiquée de la matrice de transition jusqu'à la démonstration de la convergence. L'option est évaluée en contrôle continu : les exemples sont au niveau des devoirs surveillés.

Marque ici la fiche comme lue ou mets-la en favori : un compte gratuit, sans mot de passe, retient tes fiches lues et tes favoris d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander la méthode ou l'exercice qui te manque. Crée ton espace, un courriel suffit.

Le fil du chapitre

Dans ce chapitre, la distribution s'écrit EN LIGNE et se propage à DROITE : $\pi_{n+1}=\pi_{n}M$ . Toutes les erreurs de calcul viennent d'avoir mis la distribution en colonne, et toutes les erreurs de raisonnement d'avoir cru la convergence automatique.

Ce chapitre fait partie de Maths expertes en Terminale

Pour s'entraîner Les exercices corrigés de ce chapitre, 17 exercices

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Les matrices Exercices

Remonter plus loin : la chaîne complète (10 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Les fonctions linéairesTroisième, Mathématiques
2Les fonctions affinesTroisième, Mathématiques
3Développer et factoriserTroisième, Mathématiques
4Équations, équations produit et inéquationsTroisième, Mathématiques
5Généralités sur les fonctionsSeconde, Mathématiques
6Fonctions affines et systèmesSeconde, Mathématiques
7Algorithmique et PythonSeconde, Mathématiques
8Les suites numériquesPremière, Mathématiques
9Suites et récurrenceMathématiques
10Les matrices

Notions couvertes

Graphe orienté
Matrice d'adjacence
Degré d'un sommet
Chaîne d'un graphe non orienté
Matrice de transition
Chaîne de Markov
Distribution de probabilité
Distribution invariante
État stable
Convergence des puissances
Chemin de longueur n
Graphe orienté pondéré

L'essentiel

Matrice d'adjacence : $M^{n}$ compte les chemins, sommets répétés compris

• $m_{ij}$ vaut $1$ si les sommets $i$ et $j$ sont reliés, $0$ sinon. Pour un graphe NON ORIENTÉ sans boucle, $M$ est SYMÉTRIQUE et sa diagonale est nulle.
• Le coefficient d'indice $(i\,;j)$ de $M^{n}$ est le nombre de CHEMINS de longueur $n$ allant de $i$ à $j$ ; dans un graphe non orienté, on dit aussi CHAÎNES.
• Un chemin a le droit de repasser par un sommet ou de réemprunter une arête. Ceux qui ne repassent jamais par un sommet s'appellent chemins élémentaires : le programme ne demande pas de les compter, et aucune puissance de matrice ne le fait.
• Lemme des poignées de main : la somme des degrés vaut $2m$ , où $m$ est le nombre d'ARÊTES. Le nombre de sommets de degré impair est donc toujours PAIR.

Cinq arêtes, quatre sommets de degrés

3

2

3

2

: leur somme vaut

10

, soit exactement le double du nombre d'arêtes. Deux sommets sont de degré impair, donc un nombre pair d'entre eux.

Le facteur $2$ du lemme vient de ce que chaque arête est comptée une fois à chacune de ses deux extrémités. C'est ce qui interdit un graphe à trois sommets tous de degré impair et à un nombre impair d'arêtes.

La distribution s'écrit en ligne et se propage à droite

• Une matrice de TRANSITION a des coefficients positifs, et chacune de ses LIGNES somme à $1$ . Ce sont les lignes, jamais les colonnes.
• La distribution $\pi_{n}$ s'écrit en LIGNE, et la relation est $\pi_{n+1}=\pi_{n}M$ : on multiplie à DROITE.
• Par récurrence immédiate, $\pi_{n}=\pi_{0}M^{n}$ .
• Le coefficient d'indice $(i\,;j)$ de $M^{n}$ est la probabilité d'être en $j$ au bout de $n$ étapes en partant de $i$ .

Chaque sommet porte les probabilités qui en PARTENT, et leur somme vaut

1

0{,}9

pour rester en

A

0{,}1

pour aller en

B

. C'est cette lecture par ligne qui impose la convention de multiplication à droite.

La convention ligne-à-droite est celle du programme français; d'autres pays écrivent les distributions en colonne et multiplient à gauche. Mélanger les deux donne des produits impossibles ou des résultats faux : il faut choisir celle du cours et s'y tenir.

L'état stable se cherche avec DEUX conditions

• Une distribution invariante vérifie $\pi M=\pi$ , ce qui donne un système linéaire.
• Ce système seul est INDÉTERMINÉ : tout multiple d'une solution reste solution. Il faut donc ajouter la condition « la somme des coordonnées vaut $1$ ».
• Pour deux états, avec $M=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$ , la distribution invariante est $\left(\frac{b}{a+b}\,;\frac{a}{a+b}\right)$ .
• Interprétation : plus la probabilité de QUITTER un état est faible, plus on y séjourne longtemps, et plus sa part à l'équilibre est grande.

La convergence n'est pas automatique

• Si $M=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$ avec $a$ et $b$ STRICTEMENT compris entre $0$ et $1$ , alors $\pi_{n}$ converge vers la distribution invariante, quelle que soit $\pi_{0}$ .
• L'écart à l'équilibre décroît géométriquement, de raison $1-a-b$ , ce qui explique la convergence exponentielle.
• Mais $M=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ est bien une matrice de transition, et ses puissances OSCILLENT indéfiniment entre deux valeurs.
• Une distribution invariante peut donc exister sans que la suite converge vers elle : les deux questions sont distinctes.

Le cas oscillant se reconnaît à ses coefficients extrêmes, $0$ ou $1$ : le système est alors déterministe et ne peut pas s'installer. C'est le contre-exemple que les sujets demandent d'exhiber.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Écrire la distribution en colonne et multiplier à gauche

toute la question, avec des probabilités qui ne somment plus à

1

Ce qu'il ne faut pas écrire

« $\pi_{n+1}=M\pi_{n}$ avec $\pi_{n}$ en colonne. »

Ce qu'il faut écrire

« Dans la convention du programme, $\pi_{n}$ est une matrice LIGNE et $\pi_{n+1}=\pi_{n}M$ : on multiplie à DROITE. C'est cohérent avec le fait que chaque ligne de $M$ somme à $1$ . »

Pourquoi : La somme à $1$ porte sur les LIGNES de $M$ : c'est ce qui garantit qu'une distribution ligne multipliée à droite reste une distribution. Avec l'autre convention il faudrait transposer la matrice, ce que l'énoncé ne fait pas.

2. Vérifier que les colonnes somment à 1

1 point, et une matrice valide rejetée

Ce qu'il ne faut pas écrire

« La matrice n'est pas une matrice de transition car sa première colonne somme à $1{,}1$ . »

Ce qu'il faut écrire

« Ce sont les LIGNES qui doivent sommer à $1$ : $0{,}9+0{,}1=1$ et $0{,}2+0{,}8=1$ . Les colonnes, elles, n'ont aucune raison de le faire. »

Pourquoi : Chaque ligne décrit toutes les possibilités de départ d'un même état : elles forment un système complet d'événements, d'où la somme $1$ . Une colonne rassemble des arrivées venues d'états différents, ce qui n'a aucune raison de faire $1$ .

3. Résoudre $\pi M=\pi$ sans la condition de somme

1 à 2 points, et une réponse qui n'est pas une distribution

Ce qu'il ne faut pas écrire

« Le système $\pi M=\pi$ donne $0{,}2y=0{,}1x$ , donc $\pi=(2\,;1)$ . »

Ce qu'il faut écrire

« Le système seul est INDÉTERMINÉ : $(2\,;1)$ , $(4\,;2)$ et $(0{,}2\,;0{,}1)$ le vérifient tous. Il faut ajouter $x+y=1$ , ce qui donne $\pi=\left(\frac{2}{3}\,;\frac{1}{3}\right)$ . »

Pourquoi : L'équation $\pi M=\pi$ est homogène : elle définit une DIRECTION, pas un point. La condition de normalisation choisit le représentant qui est effectivement une loi de probabilité.

4. Croire que toute chaîne de Markov converge

toute la question, sur un point de cours souvent demandé

Ce qu'il ne faut pas écrire

« Toute matrice de transition a des puissances qui convergent vers une matrice limite. »

Ce qu'il faut écrire

« C'est faux : $M=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ est une matrice de transition, mais $M^{n}$ vaut $M$ pour $n$ impair et $I$ pour $n$ pair : les puissances OSCILLENT et ne convergent pas. »

Deux distributions initiales opposées et pourtant la même limite : c'est le cas où la convergence a lieu. Avec des coefficients valant

0

1

, les deux courbes oscilleraient.

Pourquoi : À deux états, la convergence est garantie quand $a$ et $b$ sont strictement entre $0$ et $1$ : c'est une condition SUFFISANTE, pas nécessaire, puisqu'une chaîne à état absorbant converge aussi. Avec l'échange pur, la chaîne alterne mécaniquement sans jamais se stabiliser.

5. Croire qu'un chemin ne repasse jamais par un sommet

toute la question, avec un décompte trop petit

Ce qu'il ne faut pas écrire

« Le coefficient de $M^{3}$ compte les chemins de longueur $3$ , donc sans repasser par un sommet. »

Ce qu'il faut écrire

« $M^{k}$ compte TOUS les chemins de longueur $k$ , et un chemin peut repasser par un sommet et réemprunter une arête : l'aller-retour $A\to B\to A$ suivi de $A\to C$ est un chemin de longueur $3$ . »

Pourquoi : Le produit matriciel additionne sur tous les sommets intermédiaires, sans mémoire de ce qui a déjà été visité. « Sans repasser » définit un chemin ÉLÉMENTAIRE, notion hors programme qu'aucune puissance de matrice ne compte.

6. Confondre la somme des degrés et le nombre d'arêtes

1 point, avec un nombre d'arêtes doublé

Ce qu'il ne faut pas écrire

« La somme des degrés vaut $10$ , donc le graphe a $10$ arêtes. »

Ce qu'il faut écrire

« Lemme des poignées de main : la somme des degrés vaut $2m$ . Une somme de $10$ correspond donc à $m=5$ arêtes. »

Pourquoi : Chaque arête relie deux sommets et est donc comptée deux fois quand on additionne les degrés. C'est ce facteur $2$ qui force le nombre de sommets de degré impair à être pair.

7. Écrire une matrice d'adjacence non symétrique pour un graphe non orienté

1 à 2 points, et tous les comptages de chaînes deviennent faux

Ce qu'il ne faut pas écrire

« $m_{AB}=1$ mais $m_{BA}=0$ , puisque j'ai parcouru l'arête dans ce sens. »

Ce qu'il faut écrire

« Dans un graphe NON ORIENTÉ, une arête se parcourt dans les deux sens : $m_{AB}=m_{BA}=1$ . La matrice d'adjacence est donc SYMÉTRIQUE, et sa diagonale est nulle s'il n'y a pas de boucle. »

Pourquoi : La symétrie est la traduction matricielle du caractère non orienté. Dans un graphe orienté, en revanche, la matrice n'a aucune raison d'être symétrique, et c'est ce qui distingue les deux situations.

8. Faire dépendre l'état stable de la distribution initiale

1 à 2 points, sur la question d'interprétation

Ce qu'il ne faut pas écrire

« On part de $(1\,;0)$ , donc l'état stable sera plus proche de $A$ que si l'on partait de $(0\,;1)$ . »

Ce qu'il faut écrire

« Quand la convergence a lieu, la limite est la MÊME quelle que soit $\pi_{0}$ : c'est l'unique distribution invariante, ici $\left(\frac{2}{3}\,;\frac{1}{3}\right)$ . La distribution initiale ne change que la VITESSE d'approche. »

Pourquoi : L'écart à l'équilibre est multiplié par $1-a-b$ à chaque étape, quel que soit le point de départ. Il tend donc vers zéro dans tous les cas, et la limite ne garde aucune trace du départ.

9. Oublier de vérifier qu'une distribution somme à 1 après calcul

0,5 point, mais l'erreur se propage aux étapes suivantes

Ce qu'il ne faut pas écrire

« $\pi_{2}=(0{,}83\,;0{,}18)$ . »

Ce qu'il faut écrire

« La somme doit valoir exactement $1$ : ici $0{,}83+0{,}17=1$ , donc la seconde coordonnée est $0{,}17$ et non $0{,}18$ . »

Pourquoi : Une distribution de probabilité somme toujours à $1$ , et cette propriété se conserve à chaque multiplication par une matrice de transition. C'est le contrôle le plus rapide du chapitre, et il coûte une addition.

Quelle méthode choisir

Quelle question de graphe, quelle méthode

On repère d'abord si le graphe est orienté et s'il porte des probabilités, puis on lit ce que l'énoncé demande.

Si « écrire la matrice d'adjacence » → un $1$ par arête, dans les deux cases si le graphe est non orienté, en respectant l'ordre alphabétique des sommets
Si « combien de chemins (ou de chaînes) de longueur $k$ entre deux sommets » → calculer $M^{k}$ et lire le coefficient correspondant

Exemple : le coefficient $(A\,;C)$ de $M^{3}$ donne les chaînes de longueur $3$ de $A$ vers $C$
Si « combien d'arêtes » à partir des degrés → lemme des poignées de main : diviser par $2$ la somme des degrés
Si le graphe porte des probabilités sur ses flèches → matrice de TRANSITION, avec chaque ligne qui somme à $1$
Si « déterminer la distribution après $n$ étapes » → $\pi_{n}=\pi_{0}M^{n}$ , en multipliant toujours à droite

Pour un petit $n$ , il est plus rapide d'itérer $\pi_{n+1}=\pi_{n}M$ que de calculer la puissance.
Si « déterminer l'état stable » → résoudre $\pi M=\pi$ AVEC la condition que la somme des coordonnées vaut $1$

Une question sur les chaînes se répond par une puissance de matrice; une question sur le long terme se répond par un système. Les deux emploient la même matrice mais ne se traitent pas du tout de la même façon.

Comment démontrer une convergence à deux états

La démonstration est toujours la même, et les sujets la font construire question par question.

Si on cherche la distribution invariante → résoudre $\pi M=\pi$ avec la normalisation, ce qui donne $\left(\frac{b}{a+b}\,;\frac{a}{a+b}\right)$
Si on veut une relation de récurrence sur une seule coordonnée → écrire $p_{n+1}=(1-a)p_{n}+b(1-p_{n})=(1-a-b)p_{n}+b$ , une suite arithmético-géométrique
Si on veut la forme explicite → poser $q_{n}=p_{n}-\frac{b}{a+b}$ : la suite $(q_{n})$ est GÉOMÉTRIQUE de raison $1-a-b$

Exemple : $q_{n}=q_{0}(1-a-b)^{n}$ , donc $p_{n}=\frac{b}{a+b}+q_{0}(1-a-b)^{n}$
Si on veut conclure sur la limite → constater que $|1-a-b|<1$ dès que $a$ et $b$ sont strictement entre $0$ et $1$ , donc $q_{n}\to 0$
Si on veut montrer que la limite ne dépend pas de $\pi_{0}$ → remarquer que $q_{0}$ n'apparaît que dans un facteur qui tend vers $0$
Si on demande un contre-exemple → prendre $a=b=1$ : alors $1-a-b=-1$ , la raison n'est plus de module inférieur à $1$ , et la suite oscille

C'est exactement le traitement d'une suite arithmético-géométrique du tronc commun, appliqué à une probabilité. Reconnaître cette structure fait gagner la moitié des questions du problème.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Déterminer un état stable

Quand l'utiliser : La question centrale de tout exercice de chaîne de Markov, souvent formulée « à long terme ».

1 Noter $\pi=(x\,;y)$ la distribution cherchée, en LIGNE, et rappeler que $x+y=1$ .
2 Écrire le système $\pi M=\pi$ coordonnée par coordonnée, ce qui donne deux équations.
3 Constater que les deux équations sont ÉQUIVALENTES : c'est normal, le système est indéterminé.
4 Ajouter la condition de normalisation $x+y=1$ comme seconde équation effective.
5 Résoudre le système à deux équations et donner $\pi$ sous forme de fractions exactes.
6 VÉRIFIER que $\pi M=\pi$ par un produit, et que la somme des coordonnées vaut bien $1$ .

Phrase de conclusion

L'équation $\pi M=\pi$ donne $0{,}9x+0{,}2y=x$ , soit $0{,}2y=0{,}1x$ ; avec $x+y=1$ , il vient $x=\frac{2}{3}$ et $y=\frac{1}{3}$ , donc $\pi=\left(\frac{2}{3}\,;\frac{1}{3}\right)$ .

Le piège : Oublier la condition de normalisation et rendre $(2\,;1)$ . Ce couple vérifie bien le système, mais ce n'est pas une distribution de probabilité : la somme vaut $3$ .

Barème : 0,5 point pour l'écriture en ligne, 1 point pour le système, 1 point pour la condition de somme, 1 point pour la résolution et la vérification.

Démontrer la convergence par une suite auxiliaire

Quand l'utiliser : Le problème de synthèse : l'énoncé fait établir une récurrence, puis conclure sur la limite.

1 Noter $p_{n}$ la première coordonnée de $\pi_{n}$ , et remarquer que la seconde vaut $1-p_{n}$ .
2 Établir la récurrence : $p_{n+1}=(1-a)p_{n}+b(1-p_{n})=(1-a-b)p_{n}+b$ .
3 Reconnaître une suite ARITHMÉTICO-GÉOMÉTRIQUE et calculer son point fixe $\ell=\frac{b}{a+b}$ .
4 Poser $q_{n}=p_{n}-\ell$ et montrer que $(q_{n})$ est géométrique de raison $1-a-b$ .
5 En déduire $p_{n}=\ell+q_{0}(1-a-b)^{n}$ , puis conclure sur la limite en justifiant $|1-a-b|<1$ .
6 Remarquer que la limite ne dépend pas de $p_{0}$ , et l'écrire.

Phrase de conclusion

$(q_{n})$ étant géométrique de raison $1-a-b=0{,}7$ , avec $|0{,}7|<1$ , elle tend vers $0$ ; donc $p_{n}$ tend vers $\frac{2}{3}$ , et ce quelle que soit la distribution initiale.

Le piège : Conclure à la convergence sans justifier que la raison est de module strictement inférieur à $1$ . C'est exactement le point où le contre-exemple oscillant tombe en défaut, et c'est donc là que le barème place le point.

Barème : 1 point pour la récurrence, 1 point pour le point fixe, 1 point pour la suite géométrique, 1 point pour la limite justifiée.

Démontrer que $M^{n}$ compte les chemins de longueur $n$

Quand l'utiliser : Démonstration exigible du programme, souvent demandée sur un graphe donné avant le calcul de M au carré ou au cube.

1 Nommer la propriété : « pour tous $i$ et $j$ , le coefficient $(i\,;j)$ de $M^{n}$ est le nombre de chemins de longueur $n$ de $i$ vers $j$ ».
2 Initialisation : un chemin de longueur $1$ est un arc, compté par $m_{ij}$ .
3 Hérédité : découper un chemin de longueur $n+1$ en un chemin de longueur $n$ de $i$ vers $k$ suivi du DERNIER arc $k\to j$ .
4 Compter pour $k$ fixé, $\left(M^{n}\right)_{ik}m_{kj}$ , puis sommer sur $k$ : c'est le coefficient $(i\,;j)$ de $M^{n}M$ .
5 Conclure par le principe de récurrence.

Phrase de conclusion

Les chemins de longueur $n+1$ de $i$ vers $j$ se rangent selon leur avant-dernier sommet $k$ , d'où $\sum_{k}\left(M^{n}\right)_{ik}m_{kj}=\left(M^{n+1}\right)_{ij}$ chemins.

Le piège : Oublier de dire que le découpage selon l'avant-dernier sommet est UNIQUE : c'est ce qui garantit qu'aucun chemin n'est compté deux fois.

Barème : 0,5 point pour l'initialisation, 2 points pour le découpage et la somme, 0,5 point pour la conclusion.

Construire le graphe pondéré d'une chaîne de Markov

Quand l'utiliser : L'énoncé décrit les transitions en phrases et demande le graphe, puis la matrice.

1 Placer un sommet par état, dans l'ordre imposé par l'énoncé.
2 Pour chaque état $i$ , traduire chaque phrase par un arc ISSU de $i$ , portant la probabilité ; « il y reste » donne une BOUCLE.
3 Compléter la probabilité manquante par $1$ moins la somme des autres : les poids issus d'un sommet somment à $1$ .
4 Ne pas dessiner d'arc de poids nul.
5 Écrire la matrice ligne par ligne : la ligne $i$ recopie les arcs issus de $i$ .

Phrase de conclusion

Depuis $C$ : $C\to P$ ( $0{,}25$ ), la boucle $C\to C$ ( $0{,}25$ ) et $C\to L$ ( $1-0{,}25-0{,}25=0{,}5$ ).

Le piège : Oublier les boucles : rester dans le même état est une transition, et la ligne de la matrice ne somme plus à 1.

Barème : 1 point pour les arcs et les boucles, 1 point pour les poids, 1 point pour la matrice cohérente avec le graphe.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Vérifier que chaque ligne de la matrice somme à 1

C'est la définition d'une matrice de transition. Une ligne qui ne somme pas à $1$ signale une probabilité mal lue sur le graphe, ou une flèche oubliée.

$0{,}9+0{,}1=1$ et $0{,}2+0{,}8=1$ : la matrice est valide. Les colonnes, elles, donnent $1{,}1$ et $0{,}9$ , ce qui est normal.
Contrôler que chaque distribution somme à 1

Après chaque multiplication, additionner les coordonnées. Le résultat doit valoir exactement $1$ , propriété conservée par toute matrice de transition.

$0{,}83+0{,}17=1$ : la distribution $\pi_{2}$ est valide. Une somme de $1{,}01$ révèle une erreur de produit.
Réinjecter l'état stable dans l'équation

Le produit $\pi M$ doit redonner $\pi$ exactement, coordonnée par coordonnée. Deux produits de deux termes suffisent.

$0{,}9\times\frac{2}{3}+0{,}2\times\frac{1}{3}=0{,}6+0{,}0667=\frac{2}{3}$ : l'état stable est confirmé.
Vérifier le lemme des poignées de main

La somme des degrés doit être PAIRE et valoir deux fois le nombre d'arêtes. Une somme impaire est impossible, donc un degré a été mal compté.

Degrés $3$ , $2$ , $3$ et $2$ : somme $10$ , donc $5$ arêtes, et deux sommets de degré impair, ce qui est bien un nombre pair.
Tester la convergence sur les coefficients extrêmes

Si un coefficient de la matrice vaut $0$ ou $1$ , la convergence n'est plus garantie. Il faut alors calculer les premières puissances pour trancher.

$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ : les puissances alternent entre $M$ et $I$ , la suite ne converge pas.

L'exercice type décortiqué

Une chaîne de Markov à deux états, comme en devoir surveillé

Un abonné dispose de deux formules $A$ et $B$ . Chaque mois, un abonné en $A$ y reste avec la probabilité $0{,}9$ , et un abonné en $B$ passe en $A$ avec la probabilité $0{,}2$ . Au départ, tous les abonnés sont en $A$ , soit $\pi_{0}=(1\,;0)$ .

1. Écrire la matrice de transition et vérifier qu'elle en est bien une. 2. Calculer $\pi_{1}$ et $\pi_{2}$ . 3. Déterminer la distribution invariante. 4. Établir une relation de récurrence sur $p_{n}$ et en déduire la limite. 5. Donner un exemple de matrice de transition dont les puissances ne convergent pas.

Étape 1

$M=\begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}2 & 0{,}8 \end{pmatrix}$ . Chaque ligne somme à $1$ : $0{,}9+0{,}1=1$ et $0{,}2+0{,}8=1$ , et tous les coefficients sont positifs. C'est bien une matrice de transition.

Pourquoi

Les deux vérifications, positivité et somme des LIGNES, valent un demi-point chacune. La ligne $i$ décrit tout ce qui peut arriver à un abonné qui est en état $i$ : c'est un système complet d'événements.

Étape 2

$\pi_{1}=\pi_{0}M=(1\,;0)M=(0{,}9\,;0{,}1)$ , et la somme vaut bien $1$ .

Pourquoi

On multiplie la LIGNE par la matrice, à droite. Partir de $(1\,;0)$ revient à lire la première ligne de $M$ , ce qui donne un contrôle immédiat.

Étape 3

$\pi_{2}=\pi_{1}M=(0{,}9\times 0{,}9+0{,}1\times 0{,}2\,;\ 0{,}9\times 0{,}1+0{,}1\times 0{,}8)=(0{,}81+0{,}02\,;\ 0{,}09+0{,}08)=(0{,}83\,;0{,}17)$ .

Pourquoi

La somme vaut $1$ , ce qui valide le produit. Itérer $\pi_{n+1}=\pi_{n}M$ est plus rapide que de calculer $M^{2}$ quand seules les deux premières étapes sont demandées.

Étape 4

Distribution invariante $\pi=(x\,;y)$ : la première coordonnée de $\pi M$ donne $0{,}9x+0{,}2y=x$ , soit $0{,}2y=0{,}1x$ , c'est-à-dire $x=2y$ . Avec $x+y=1$ , on obtient $y=\frac{1}{3}$ et $x=\frac{2}{3}$ .

Pourquoi

La seconde équation du système est équivalente à la première : c'est ce qui rend la condition de normalisation indispensable. Le signaler montre qu'on a compris pourquoi elle est là.

Étape 5

Vérification : $0{,}9\times\frac{2}{3}+0{,}2\times\frac{1}{3}=\frac{1{,}8+0{,}2}{3}=\frac{2}{3}$ , et $0{,}1\times\frac{2}{3}+0{,}8\times\frac{1}{3}=\frac{0{,}2+0{,}8}{3}=\frac{1}{3}$ . La distribution est bien invariante.

Pourquoi

Deux produits de deux termes valident la question précédente. Une distribution invariante qui ne se reproduit pas signale une erreur de système ou de normalisation.

Étape 6

Récurrence : en notant $p_{n}$ la proportion en $A$ , $p_{n+1}=0{,}9p_{n}+0{,}2(1-p_{n})=0{,}7p_{n}+0{,}2$ . C'est une suite arithmético-géométrique de point fixe $\ell=\frac{0{,}2}{0{,}3}=\frac{2}{3}$ .

Pourquoi

On retrouve le point fixe déjà obtenu par le système : deux méthodes, un seul résultat. La proportion en $B$ n'est pas une seconde inconnue, elle vaut $1-p_{n}$ .

Étape 7

En posant $q_{n}=p_{n}-\frac{2}{3}$ : $q_{n+1}=0{,}7q_{n}$ , donc $q_{n}=q_{0}\times 0{,}7^{n}$ avec $q_{0}=\frac{1}{3}$ . Ainsi $p_{n}=\frac{2}{3}+\frac{1}{3}\times 0{,}7^{n}$ .

Pourquoi

Comme $|0{,}7|<1$ , la suite $(q_{n})$ tend vers $0$ et $p_{n}$ tend vers $\frac{2}{3}$ . Le facteur $q_{0}$ contient tout ce qui dépend du départ, et il est multiplié par une quantité qui s'annule.

Étape 8

Contre-exemple : $N=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ est une matrice de transition, mais $N^{n}=N$ pour $n$ impair et $N^{n}=I$ pour $n$ pair. Partant de $(1\,;0)$ , la distribution alterne entre $(1\,;0)$ et $(0\,;1)$ : elle ne converge pas.

Pourquoi

Les coefficients valent $0$ et $1$ , donc la raison $1-a-b$ vaut $-1$ et n'est plus de module strictement inférieur à $1$ . La condition du théorème n'est pas une précaution, c'est exactement ce qui est en jeu.

Conclusion rédigée

La matrice de transition est valide, la distribution passe de $(1\,;0)$ à $(0{,}9\,;0{,}1)$ puis $(0{,}83\,;0{,}17)$ , et converge vers l'unique distribution invariante $\left(\frac{2}{3}\,;\frac{1}{3}\right)$ , quelle que soit la répartition de départ; cette convergence tient à ce que la raison $0{,}7$ est de module inférieur à $1$ , ce qui cesse d'être vrai pour la matrice d'échange pur.

L'erreur classique sur cet exercice : Rendre $(2\,;1)$ comme distribution invariante. Ce couple vérifie bien le système $\pi M=\pi$ , mais sa somme vaut $3$ : ce n'est pas une loi de probabilité, et la condition de normalisation a été oubliée.

À savoir par cœur

• $M^{k}$ compte les CHEMINS de longueur $k$ , appelés chaînes dans un graphe non orienté : on a le droit de repasser par un sommet.
• Lemme des poignées de main : somme des degrés $=2m$ . Le nombre de sommets de degré impair est PAIR.
• Matrice d'adjacence d'un graphe non orienté : SYMÉTRIQUE, diagonale nulle sans boucle.
• Matrice de transition : coefficients positifs, chaque LIGNE somme à $1$ . Pas les colonnes.
• Distribution en LIGNE, multiplication à DROITE : $\pi_{n+1}=\pi_{n}M$ et $\pi_{n}=\pi_{0}M^{n}$ .
• État stable : $\pi M=\pi$ ET somme des coordonnées égale à $1$ . Sans la seconde condition, le système est indéterminé.
• À deux états, $\pi=\left(\frac{b}{a+b}\,;\frac{a}{a+b}\right)$ , et l'écart décroît en $(1-a-b)^{n}$ .
• La convergence n'est PAS automatique : $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ oscille indéfiniment.
• Quand la convergence a lieu, la limite ne dépend PAS de la distribution initiale.

Questions fréquentes

Que compte le coefficient d'une puissance de la matrice d'adjacence ?

Le nombre de chemins de longueur égale à l'exposant entre les deux sommets correspondants, qu'on appelle aussi chaînes quand le graphe n'est pas orienté. Un chemin a le droit de repasser par un sommet déjà visité et de réemprunter une arête : c'est justement ce qui rend le comptage accessible par un simple produit de matrices.

Dans quel sens multiplie-t-on une distribution par la matrice de transition ?

Dans la convention du programme français, la distribution s'écrit en ligne et se multiplie à droite : la distribution suivante est la distribution actuelle multipliée par la matrice. C'est cohérent avec le fait que chaque ligne de la matrice somme à un, ce qui garantit que le résultat reste une distribution.

Pourquoi faut-il ajouter la condition de somme égale à un pour l'état stable ?

Parce que le système donné par l'égalité de la distribution et de son image est homogène : tout multiple d'une solution est encore solution. Il définit donc une direction, pas un point précis. La condition de normalisation choisit parmi tous ces multiples celui qui est une véritable loi de probabilité.

Toute chaîne de Markov converge-t-elle vers un état stable ?

Non. La convergence est garantie quand tous les coefficients de transition sont strictement compris entre zéro et un. La matrice qui échange systématiquement les deux états est bien une matrice de transition, elle possède même une distribution invariante, et pourtant ses puissances alternent indéfiniment sans converger.

La limite dépend-elle de la répartition de départ ?

Non, lorsque la convergence a lieu. L'écart à l'équilibre est multiplié à chaque étape par la même raison, de module inférieur à un, quel que soit le point de départ. La distribution initiale n'influence donc que la vitesse d'approche, jamais la limite atteinte.

Que dit le lemme des poignées de main ?

Que la somme des degrés de tous les sommets vaut exactement le double du nombre d'arêtes, puisque chaque arête est comptée une fois à chacune de ses deux extrémités. Il en découle que le nombre de sommets de degré impair est toujours pair, ce qui permet de rejeter certains graphes comme impossibles.

Passer à la pratique

Exercices corrigés : Graphes et chaînes de Markov

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

17 exercices corrigés
170 points
255 minutes

Faire les exercices

Il manque quelque chose dans cette fiche ? Une méthode, un piège, un exercice pour l'appliquer, une erreur repérée : dis-le-moi, je lis chaque demande.

L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace. Pas envie de créer un compte ? Écris-moi directement.

Fiche précédente Les matrices

© Ahmed Squalli Houssaini. Fiche publiée sur www.letuteurscientifique.ca/fiches/expertes-graphes-markov. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Toutes les fiches Tous les exercices Maths expertes Tuteur Terminale

Vous cherchez un tuteur de maths expertes à Montréal ?

Contactez-moi pour une première séance. On reprend les démonstrations et les pièges du chapitre, puis on les met à l'épreuve sur des exercices au niveau des devoirs surveillés du Lycée Marie de France et du Collège Stanislas.

Me contacter WhatsApp

Site par Studio Squalli

Fiche de révision : graphes et chaînes de Markov (maths expertes)

L'essentiel

Matrice d'adjacence : MnM^{n}Mn compte les chemins, sommets répétés compris

La distribution s'écrit en ligne et se propage à droite

L'état stable se cherche avec DEUX conditions

La convergence n'est pas automatique

Les pièges qui coûtent des points

1. Écrire la distribution en colonne et multiplier à gauche

2. Vérifier que les colonnes somment à 1

3. Résoudre πM=π\pi M=\piπM=π sans la condition de somme

4. Croire que toute chaîne de Markov converge

5. Croire qu'un chemin ne repasse jamais par un sommet

6. Confondre la somme des degrés et le nombre d'arêtes

7. Écrire une matrice d'adjacence non symétrique pour un graphe non orienté

8. Faire dépendre l'état stable de la distribution initiale

9. Oublier de vérifier qu'une distribution somme à 1 après calcul

Quelle méthode choisir

Quelle question de graphe, quelle méthode

Comment démontrer une convergence à deux états

La rédaction attendue

Déterminer un état stable

Démontrer la convergence par une suite auxiliaire

Démontrer que MnM^{n}Mn compte les chemins de longueur nnn

Construire le graphe pondéré d'une chaîne de Markov

Vérifier avant de rendre

L'exercice type décortiqué

Une chaîne de Markov à deux états, comme en devoir surveillé

À savoir par cœur

Questions fréquentes

Que compte le coefficient d'une puissance de la matrice d'adjacence ?

Dans quel sens multiplie-t-on une distribution par la matrice de transition ?

Pourquoi faut-il ajouter la condition de somme égale à un pour l'état stable ?

Toute chaîne de Markov converge-t-elle vers un état stable ?

La limite dépend-elle de la répartition de départ ?

Que dit le lemme des poignées de main ?

Exercices corrigés : Graphes et chaînes de Markov

Voir aussi

Vous cherchez un tuteur de maths expertes à Montréal ?

Matrice d'adjacence : $M^{n}$ compte les chemins, sommets répétés compris

3. Résoudre $\pi M=\pi$ sans la condition de somme

Démontrer que $M^{n}$ compte les chemins de longueur $n$