Graphes et chaînes de Markov
Cours
Un réseau social, un plan de métro, Internet : tout cela se dessine avec des points reliés par des traits, c'est-à-dire un graphe. Pour classer les pages web, les premiers moteurs de recherche imaginaient un internaute qui clique au hasard de lien en lien, et regardaient où il passe le plus souvent : c'est une chaîne de Markov. Le même outil sert à prévoir la météo, l'évolution d'un marché ou le texte suggéré par ton téléphone. Avec ce chapitre, tu sauras :
- décrire un graphe (sommets, arêtes, degrés, chaînes) et le coder par une matrice ;
- compter les chemins d'une longueur donnée avec les puissances d'une matrice ;
- modéliser une évolution aléatoire par une chaîne de Markov ;
- trouver la distribution invariante et prévoir l'évolution à long terme.
1 Graphes : le vocabulaire
On représente des objets par des points et les liens entre eux par des traits.
Un graphe (non orienté) est formé de sommets et d'arêtes qui relient deux sommets.
- L'ordre du graphe est son nombre de sommets. Deux sommets reliés par une arête sont adjacents.
- Le degré d'un sommet est le nombre d'arêtes qui en partent.
- Une chaîne est une suite de sommets dont deux consécutifs sont adjacents ; sa longueur est son nombre d'arêtes. Une chaîne qui revient à son point de départ sans repasser par la même arête est un cycle.
- Le graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne. Il est complet si tous ses sommets sont adjacents deux à deux.
La somme des degrés des sommets d'un graphe est égale au double du nombre d'arêtes.
L'idée en une phrase : chaque arête est comptée deux fois, une fois par extrémité.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Compter autrement. Additionner les degrés revient à compter, pour chaque sommet, les arêtes qui le touchent.
Étape 2 — Chaque arête deux fois. Une arête touche exactement deux sommets : elle est comptée deux fois. La somme vaut donc \(2 \times\) (nombre d'arêtes) ✓.
Étape 1 — Les degrés. \(A\) : \(2\) ; \(B\) : \(3\) ; \(C\) : \(3\) ; \(D\) : \(3\) ; \(E\) : \(1\).
Étape 2 — Vérifier le lemme. \(2 + 3 + 3 + 3 + 1 = 12 = 2 \times 6\) : il y a bien \(6\) arêtes ✓.
Étape 3 — Chaînes et cycles. \(A - B - D - E\) est une chaîne de longueur \(3\) ; \(A - B - C - A\) est un cycle de longueur \(3\). Le graphe est connexe, mais pas complet (\(A\) et \(D\) ne sont pas adjacents).
- ❌ Confondre l'ordre (nombre de sommets) et le nombre d'arêtes.
- ❌ « Un graphe peut avoir des degrés \(3, 3, 3, 3, 1\). » ✅ La somme \(13\) est impaire : c'est impossible.
Combien d'arêtes possède le graphe complet à \(4\) sommets ?
Voir la réponseMasquer la réponse
Chaque sommet est de degré \(3\), donc \(4 \times 3 = 12 = 2 \times 6\) : \(6\) arêtes.
Ordre = nombre de sommets ; degré = nombre d'arêtes issues d'un sommet ; somme des degrés \(= 2 \times\) nombre d'arêtes.
2 Matrice d'adjacence et nombre de chemins
Pour qu'un ordinateur « voie » un graphe, on le code par une matrice. Les puissances de cette matrice comptent alors les chemins.
Dans un graphe orienté, les liens sont des arcs à sens unique, dessinés par des flèches. Un chemin suit les arcs dans leur sens. La matrice d'adjacence d'un graphe à \(n\) sommets numérotés \(1\) à \(n\) est la matrice carrée \(M\) où \(m_{ij}\) est le nombre d'arcs (ou d'arêtes) allant de \(i\) à \(j\). Pour un graphe non orienté, \(M\) est symétrique.
Le coefficient \((i, j)\) de \(M^n\) est le nombre de chemins de longueur \(n\) allant du sommet \(i\) au sommet \(j\).
L'idée en une phrase : un chemin de longueur \(2\) de \(i\) à \(j\) passe par un sommet intermédiaire \(k\).
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Compter par l'intermédiaire. Pour chaque \(k\), il y a \(m_{ik} \times m_{kj}\) chemins \(i \to k \to j\).
Étape 2 — Additionner. Le total est \(m_{i1}m_{1j} + \cdots + m_{in}m_{nj}\) : c'est exactement le coefficient \((i, j)\) de \(M^2\) ✓. Le cas général se démontre par récurrence de la même façon (exercice 29).
Étape 1 — La matrice. \(M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}\) (ligne = départ, colonne = arrivée).
Étape 2 — Le carré. \(M^2 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}\).
Étape 3 — Lire. Le coefficient \((1, 1)\) vaut \(1\) : un seul chemin de longueur \(2\) de \(1\) à \(1\), c'est \(1 \to 3 \to 1\). Le coefficient \((1, 2)\) vaut \(0\) : aucun chemin de longueur \(2\) de \(1\) à \(2\).
🔍 Vérification : de \(1\), on va en \(2\) ou \(3\) ; de là, on atteint \(3\) (depuis \(2\)) ou \(1\) (depuis \(3\)), jamais \(2\) ✓.
- ❌ Inverser lignes et colonnes dans un graphe orienté. ✅ Ligne = sommet de départ, colonne = sommet d'arrivée.
- ❌ Croire que \(M^n\) donne la longueur du plus court chemin. ✅ Il compte les chemins de longueur exactement \(n\).
Dans le graphe de la partie 1, que vaut le coefficient \((A, A)\) de \(M^2\) ?
Voir la réponseMasquer la réponse
Il compte les chaînes \(A - k - A\), soit le degré de \(A\) : \(2\).
\(m_{ij}\) = nombre d'arcs de \(i\) vers \(j\) ; \((M^n)_{ij}\) = nombre de chemins de longueur \(n\) de \(i\) à \(j\).
3 Chaînes de Markov
Quand on passe d'un état à un autre au hasard, avec des probabilités qui ne dépendent que de l'état présent, on parle de chaîne de Markov.
Une chaîne de Markov est une suite de variables aléatoires \((X_n)\) à valeurs dans un ensemble d'états, telle que la probabilité de passer de l'état \(i\) à l'état \(j\) ne dépend ni de \(n\) ni du passé : on la note \(p_{ij}\).
- La matrice de transition \(P\) a pour coefficients les \(p_{ij}\) ; la somme de chaque ligne vaut \(1\).
- Le graphe probabiliste associé a un arc de \(i\) vers \(j\), pondéré par \(p_{ij}\), dès que \(p_{ij} > 0\).
- La distribution à l'étape \(n\) est la matrice ligne \(\pi_n\) des probabilités d'être dans chaque état.
Pour tout entier \(n\), \(\pi_{n+1} = \pi_nP\), et donc \(\pi_n = \pi_0P^n\).
L'idée en une phrase : c'est la formule des probabilités totales.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — Une coordonnée. \(P(X_{n+1} = j) = \sum_i P(X_n = i) \times P_{X_n = i}(X_{n+1} = j) = \sum_i (\pi_n)_i \, p_{ij}\).
Étape 2 — Reconnaître un produit. C'est le produit de la ligne \(\pi_n\) par la colonne \(j\) de \(P\) ✓. Puis, par récurrence, \(\pi_n = \pi_0P^n\), comme pour une suite géométrique.
S'il fait beau, il fait beau le lendemain avec probabilité \(0{,}8\) ; s'il pleut, il fait beau le lendemain avec probabilité \(0{,}4\). Aujourd'hui (jour \(0\)), il fait beau.
Étape 1 — La matrice. États dans l'ordre (B, P) : \(P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}4 & 0{,}6 \end{pmatrix}\), et \(\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}\).
Étape 2 — Demain. \(\pi_1 = \pi_0P = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}\).
Étape 3 — Après-demain. \(\pi_2 = \pi_1P = \begin{pmatrix} 0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}4 & 0{,}8 \times 0{,}2 + 0{,}2 \times 0{,}6 \end{pmatrix} = \begin{pmatrix} 0{,}72 & 0{,}28 \end{pmatrix}\).
🔍 Vérification : \(0{,}72 + 0{,}28 = 1\) ✓.
- ❌ Écrire \(\pi_{n+1} = P\pi_n\). ✅ \(\pi_n\) est une matrice ligne : elle se place à gauche, \(\pi_{n+1} = \pi_nP\).
- ❌ Faire la somme des colonnes égale à \(1\). ✅ Ce sont les lignes : de chaque état, on va forcément quelque part.
Calcule \(\pi_3\) dans l'exemple de la météo.
Voir la réponseMasquer la réponse
\(\pi_3 = \begin{pmatrix} 0{,}72 \times 0{,}8 + 0{,}28 \times 0{,}4 & 0{,}72 \times 0{,}2 + 0{,}28 \times 0{,}6 \end{pmatrix} = \begin{pmatrix} 0{,}688 & 0{,}312 \end{pmatrix}\).
\(p_{ij}\) = probabilité de passer de \(i\) à \(j\) ; lignes de somme \(1\) ; \(\pi_{n+1} = \pi_nP\) et \(\pi_n = \pi_0P^n\).
4 Distribution invariante
Certaines distributions ne changent plus d'une étape à l'autre : le système est alors en équilibre.
Une distribution \(\pi\) (matrice ligne à coefficients positifs de somme \(1\)) est invariante si \(\pi P = \pi\).
Pour \(P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix}\) avec \(a + b > 0\), l'unique distribution invariante est \[\pi = \begin{pmatrix} \dfrac{b}{a + b} & \dfrac{a}{a + b} \end{pmatrix}.\]
L'idée en une phrase : on résout \(\pi P = \pi\) avec \(x + y = 1\).
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — L'équation. \(\pi = \begin{pmatrix} x & y \end{pmatrix}\) : la première coordonnée de \(\pi P = \pi\) donne \((1 - a)x + by = x\), soit \(ax = by\).
Étape 2 — Avec \(x + y = 1\). \(ax = b(1 - x)\), donc \(x = \dfrac{b}{a + b}\) et \(y = \dfrac{a}{a + b}\) ✓.
Étape 1 — Les paramètres. \(a = 0{,}2\) (beau → pluie) et \(b = 0{,}4\) (pluie → beau).
Étape 2 — La formule. \(\pi = \begin{pmatrix} \dfrac{0{,}4}{0{,}6} & \dfrac{0{,}2}{0{,}6} \end{pmatrix} = \begin{pmatrix} \dfrac{2}{3} & \dfrac{1}{3} \end{pmatrix}\).
🔍 Vérification : \(\dfrac{2}{3} \times 0{,}8 + \dfrac{1}{3} \times 0{,}4 = \dfrac{1{,}6 + 0{,}4}{3} = \dfrac{2}{3}\) ✓.
On résout le système \(\pi P = \pi\), \(\pi_1 + \pi_2 + \pi_3 = 1\) (à la main ou avec les matrices du chapitre précédent).
- ❌ Oublier la condition « somme \(= 1\) ». ✅ Sans elle, \(\pi P = \pi\) a une infinité de solutions proportionnelles.
Trouve la distribution invariante de \(P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7 \end{pmatrix}\).
Voir la réponseMasquer la réponse
\(a = 0{,}1\), \(b = 0{,}3\) : \(\pi = \begin{pmatrix} 0{,}75 & 0{,}25 \end{pmatrix}\).
\(\pi\) invariante \(\iff \pi P = \pi\) et somme \(1\) ; deux états : \(\pi = \left(\dfrac{b}{a + b} \;\; \dfrac{a}{a + b}\right)\).
5 Évolution à long terme
Que devient la distribution après beaucoup d'étapes ? Dans de nombreux cas, elle se rapproche de la distribution invariante, quel que soit le départ.
Avec les notations de la partie 4, si \(0 < a + b < 2\), alors pour toute distribution initiale, \(\pi_n\) converge vers la distribution invariante \(\pi\).
L'idée en une phrase : la première coordonnée \(x_n\) suit une suite arithmético-géométrique.
Voir la démonstration pas à pasMasquer la démonstration
Étape 1 — La relation. \(x_{n+1} = (1 - a)x_n + b(1 - x_n) = (1 - a - b)x_n + b\).
Étape 2 — L'écart à l'équilibre. Avec \(x = \dfrac{b}{a + b}\), on vérifie \(x_{n+1} - x = (1 - a - b)(x_n - x)\) : l'écart est géométrique de raison \(1 - a - b\). Comme \(-1 < 1 - a - b < 1\), il tend vers \(0\) ✓.
Étape 1 — La suite. \(x_n\) = probabilité qu'il fasse beau le jour \(n\) : \(x_{n+1} = 0{,}4x_n + 0{,}4\), avec \(x_0 = 1\).
Étape 2 — La formule. \(x_n - \dfrac{2}{3} = 0{,}4^n\left(1 - \dfrac{2}{3}\right)\), donc \(x_n = \dfrac{2}{3} + \dfrac{1}{3} \times 0{,}4^n\).
Conclusion : \(0{,}4^n \to 0\), donc \(x_n \to \boxed{\dfrac{2}{3}}\) : à long terme, il fait beau deux jours sur trois.
🔍 Vérification : \(x_2 = \dfrac{2}{3} + \dfrac{0{,}16}{3} = \dfrac{2{,}16}{3} = 0{,}72\) ✓ (partie 3).
On admet que si une puissance \(P^k\) a tous ses coefficients strictement positifs, \(\pi_n\) converge vers l'unique distribution invariante. À la calculatrice, les lignes de \(P^n\) se rapprochent toutes de \(\pi\).
- ❌ « \(\pi_n\) converge toujours. » ✅ Si \(a = b = 1\), le système alterne entre les deux états sans jamais se stabiliser (voir aussi l'exercice 26).
Avec la météo, s'il pleut au jour \(0\) (\(x_0 = 0\)), donne \(x_n\).
Voir la réponseMasquer la réponse
\(x_n = \dfrac{2}{3} + \left(0 - \dfrac{2}{3}\right) \times 0{,}4^n = \dfrac{2}{3} - \dfrac{2}{3} \times 0{,}4^n\), qui tend aussi vers \(\dfrac{2}{3}\).
Deux états avec \(0 < a + b < 2\) : \(\pi_n \to \pi\), quel que soit \(\pi_0\) ; l'écart à l'équilibre est géométrique de raison \(1 - a - b\).
Pour aller plus loin
Contenu facultatif, non exigible.
(hors programme) : l'algorithme PageRank calcule la distribution invariante d'une chaîne de Markov dont les états sont des milliards de pages web ; on la trouve en calculant \(\pi_0P^n\) pour \(n\) grand plutôt qu'en résolvant le système (exercice 25, avec trois pages).
Les maths cachées · Le classement des pages webComment un moteur de recherche choisit-il la première page ?Voir la réponse et l’essai ▾Refermer ▴
Imagine un internaute qui navigue au hasard : sur chaque page, il clique sur l'un des liens, choisi au hasard. Les pages où il passe le plus souvent sont les plus « importantes ». C'est l'idée du classement PageRank, imaginé à la fin des années 1990 pour un moteur de recherche.
Quatre pages. La page A a des liens vers B et C ; B vers C ; C vers A ; D vers A et C. Aucune page n'a de lien vers D. La matrice de transition (pages dans l'ordre A, B, C, D) est :
\[P = \begin{pmatrix} 0 & 0{,}5 & 0{,}5 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0{,}5 & 0 & 0{,}5 & 0 \end{pmatrix}\]
La distribution invariante. On résout \(\pi P = \pi\), avec une somme égale à \(1\) : on trouve \(\pi = \begin{pmatrix} 0{,}4 & 0{,}2 & 0{,}4 & 0 \end{pmatrix}\). A et C sont à égalité, et D n'est jamais visitée.
L'internaute qui se lasse. En vrai, l'internaute finit par taper une autre adresse. On suppose donc qu'à chaque étape, il clique sur un lien avec la probabilité \(0{,}85\), et qu'il va sur une page au hasard avec la probabilité \(0{,}15\). La nouvelle distribution invariante vaut environ :
| Page | A | B | C | D |
|---|---|---|---|---|
| Probabilité | \(0{,}380\) | \(0{,}199\) | \(0{,}384\) | \(0{,}0375\) |
C passe devant A : elle reçoit des liens de trois pages (A, B et D), alors que A n'en reçoit que de deux. Et D n'est plus à zéro.
, on ne résout pas le système. On part d'une distribution quelconque et on calcule \(\pi_0 P\), \(\pi_0 P^2\), \(\pi_0 P^3\)… : comme dans le cours, la distribution se rapproche de la distribution invariante.
C'est le principe d'origine. Aujourd'hui, les moteurs de recherche combinent des centaines d'autres critères.
Quiz du cours
Tu as lu le cours ? Vérifie en 8 questions que tu as retenu l’essentiel. Chaque réponse est corrigée tout de suite, sans chronomètre.
Un graphe a des sommets de degrés \(3, 3, 2, 2, 2\). Combien a-t-il d'arêtes ?
Réponse attendue : \(6\)
Lemme des poignées de main : la somme des degrés, \(12\), vaut le double du nombre d'arêtes.
Vrai ou faux : il existe un graphe dont les sommets ont pour degrés \(3, 3, 3, 3, 1\).
La somme des degrés, \(13\), est impaire : elle ne peut pas être le double d'un nombre d'arêtes.
Que représente le coefficient \((i, j)\) de \(M^3\), où \(M\) est la matrice d'adjacence d'un graphe ?
Les puissances de la matrice d'adjacence comptent les chemins de longueur donnée.
Revoir dans le cours : 2. Matrice d'adjacence et nombre de chemins
Vrai ou faux : dans une matrice de transition, la somme de chaque ligne vaut \(1\).
La ligne \(i\) donne les probabilités de passer de l'état \(i\) à chacun des états : leur somme vaut \(1\).
Pour une chaîne de Markov de matrice de transition \(P\), la distribution \(\pi_{n+1}\) vaut :
\(\pi_n\) est une matrice ligne : elle se place à gauche de \(P\).
Météo : \(P = \begin{pmatrix} 0{,}8 & 0{,}2 \ 0{,}4 & 0{,}6 \end{pmatrix}\) et \(\pi_1 = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}\). Quelle est la première coordonnée de \(\pi_2\) ?
Réponse attendue : \(0{,}72\)
\(0{,}8 \times 0{,}8 + 0{,}2 \times 0{,}4 = 0{,}64 + 0{,}08 = 0{,}72\).
Quelle est la première coordonnée de la distribution invariante de \(P = \begin{pmatrix} 0{,}9 & 0{,}1 \ 0{,}3 & 0{,}7 \end{pmatrix}\) ?
Réponse attendue : \(0{,}75\)
Avec \(a = 0{,}1\) et \(b = 0{,}3\) : \(\dfrac{b}{a + b} = \dfrac{0{,}3}{0{,}4} = 0{,}75\).
Vrai ou faux : pour une chaîne à deux états avec \(0 < a + b < 2\), la distribution \(\pi_n\) converge vers la distribution invariante, quel que soit \(\pi_0\).
L'écart à l'équilibre est géométrique de raison \(1 - a - b\), comprise strictement entre \(-1\) et \(1\).
À revoir dans le cours :
Fiche mémo
L’essentiel du chapitre, à relire avant un contrôle.
L'essentiel
| Notion | À savoir |
|---|---|
| Graphe | sommets, arêtes ; ordre = nombre de sommets ; degré d'un sommet |
| Poignées de main | somme des degrés \(= 2 \times\) nombre d'arêtes |
| Chaîne, cycle | longueur = nombre d'arêtes ; connexe ; complet (\(n\) sommets : \(\dfrac{n(n - 1)}{2}\) arêtes) |
| Matrice d'adjacence | \(m_{ij}\) = arcs de \(i\) vers \(j\) ; symétrique si non orienté |
| Chemins | \((M^n)_{ij}\) = nombre de chemins de longueur \(n\) de \(i\) à \(j\) |
| Chaîne de Markov | \(P\) : lignes de somme \(1\) ; \(\pi_{n+1} = \pi_nP\), \(\pi_n = \pi_0P^n\) |
| Invariante | \(\pi P = \pi\), somme \(1\) ; deux états : \(\left(\dfrac{b}{a + b} \;\; \dfrac{a}{a + b}\right)\) |
| Long terme | deux états, \(0 < a + b < 2\) : \(\pi_n \to \pi\) |
Pièges à éviter
- Ligne = départ, colonne = arrivée.
- \(\pi_n\) est une matrice ligne : \(\pi_{n+1} = \pi_nP\), pas \(P\pi_n\).
- Une distribution invariante n'est pas toujours une limite (cas périodique).
Contrôle demain ? Prépare ton plan de révision de 30 minutes sur ce chapitre →
Niveau 1Facile (Exercices 1 à 11)
Pour le graphe de la partie 1 du cours, donne l'ordre, le degré de chaque sommet et la liste des sommets adjacents à \(C\).
Voir la correction›
lire la figure.
Ordre \(5\). Degrés : \(A\) : \(2\), \(B\) : \(3\), \(C\) : \(3\), \(D\) : \(3\), \(E\) : \(1\). Sommets adjacents à \(C\) : \(A\), \(B\) et \(D\).
🔍 Vérification : la somme des degrés vaut \(12 = 2 \times 6\) ✓
Les sommets d'un graphe ont pour degrés \(3, 3, 2, 2, 2\). Combien a-t-il d'arêtes ?
Voir la correction›
lemme des poignées de main.
\(3 + 3 + 2 + 2 + 2 = 12 = 2 \times 6\) : \(\boxed{6 \text{ arêtes}}\).
🔍 Vérification : \(12\) est pair, le graphe est donc possible ✓
Existe-t-il un graphe à \(5\) sommets de degrés \(3, 3, 3, 3, 1\) ? Justifie.
Voir la correction›
parité de la somme des degrés.
\(3 + 3 + 3 + 3 + 1 = 13\) est impair, alors qu'il devrait valoir le double du nombre d'arêtes : impossible.
🔍 Vérification : il y a \(5\) sommets de degré impair, un nombre impair (exercice 12) ✓
Combien d'arêtes ont les graphes complets à \(4\), \(5\) et \(10\) sommets ? Donne une formule pour \(n\) sommets.
Voir la correction›
chaque sommet est relié aux \(n - 1\) autres.
La somme des degrés vaut \(n(n - 1)\), donc il y a \(\dfrac{n(n - 1)}{2}\) arêtes : \(6\), \(10\) et \(45\).
🔍 Vérification : \(\dfrac{10 \times 9}{2} = 45\) ✓
Écris la matrice d'adjacence du graphe de la partie 1 (sommets dans l'ordre \(A, B, C, D, E\)). Pourquoi est-elle symétrique ?
Voir la correction›
\(1\) si adjacents, \(0\) sinon.
\(M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}\). Elle est symétrique car une arête relie \(i\) à \(j\) et \(j\) à \(i\).
🔍 Vérification : la somme de chaque ligne est le degré du sommet ✓
Dans le graphe de la partie 1 :
a) donne une chaîne de longueur \(3\) de \(A\) à \(E\) ;
b) trouve un cycle de longueur \(4\).
Voir la correction›
suivre les arêtes.
a) \(A - B - D - E\) (ou \(A - C - D - E\)).
b) \(A - B - D - C - A\) : arêtes \(AB\), \(BD\), \(DC\), \(CA\).
🔍 Vérification : \((M^3)_{AE} = 2\) : il y a exactement deux chaînes de longueur \(3\) de \(A\) à \(E\) ✓
Un graphe orienté a pour matrice d'adjacence \(\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\). Donne la liste de ses arcs.
Voir la correction›
\(m_{ij} = 1\) : arc de \(i\) vers \(j\).
Arcs : \(1 \to 2\), \(2 \to 3\), \(3 \to 1\) et \(3 \to 2\).
🔍 Vérification : la matrice contient quatre \(1\), il y a quatre arcs ✓
Chaque mois, \(90\,\%\) des clients de l'opérateur X restent chez X et \(10\,\%\) passent chez Y ; \(30\,\%\) des clients de Y passent chez X et les autres restent. Écris la matrice de transition (états dans l'ordre X, Y).
Voir la correction›
ligne = état de départ.
\(P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}3 & 0{,}7 \end{pmatrix}\).
🔍 Vérification : chaque ligne a pour somme \(1\) ✓
Lesquelles de ces matrices sont des matrices de transition ? \(P_1 = \begin{pmatrix} 0{,}5 & 0{,}5 \\ 0{,}2 & 0{,}8 \end{pmatrix}\), \(P_2 = \begin{pmatrix} 0{,}6 & 0{,}3 \\ 0{,}4 & 0{,}7 \end{pmatrix}\), \(P_3 = \begin{pmatrix} 1 & 0 \\ 0{,}5 & 0{,}5 \end{pmatrix}\).
Voir la correction›
coefficients positifs et lignes de somme \(1\).
\(P_1\) : oui. \(P_2\) : non (première ligne : \(0{,}9\)). \(P_3\) : oui (l'état 1 est « absorbant »).
🔍 Vérification : dans \(P_2\), ce sont les colonnes qui font \(1\) : piège classique ✓
Avec la matrice de l'exercice 8 et \(\pi_0 = \begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}\), calcule \(\pi_1\).
Voir la correction›
\(\pi_1 = \pi_0P\).
\(\pi_1 = \begin{pmatrix} 0{,}45 + 0{,}15 & 0{,}05 + 0{,}35 \end{pmatrix} = \boxed{\begin{pmatrix} 0{,}6 & 0{,}4 \end{pmatrix}}\).
🔍 Vérification : \(0{,}6 + 0{,}4 = 1\) ✓
Trouve la distribution invariante de la chaîne de l'exercice 8. Interprète.
Voir la correction›
formule à deux états.
\(a = 0{,}1\), \(b = 0{,}3\) : \(\pi = \begin{pmatrix} 0{,}75 & 0{,}25 \end{pmatrix}\). À long terme, l'opérateur X aura \(75\,\%\) des clients.
🔍 Vérification : \(0{,}75 \times 0{,}9 + 0{,}25 \times 0{,}3 = 0{,}675 + 0{,}075 = 0{,}75\) ✓
Niveau 2Intermédiaire (Exercices 12 à 24)
a) Démontre le lemme des poignées de main.
b) Déduis-en que le nombre de sommets de degré impair est toujours pair.
Voir la correction›
chaque arête compte deux fois ; somme paire.
a) Voir la partie 1 du cours.
b) La somme des degrés est paire. Les degrés pairs donnent une somme paire ; il faut donc que la somme des degrés impairs soit paire, ce qui impose un nombre pair de termes impairs ✓.
🔍 Vérification : graphe de la partie 1 : \(B\), \(C\), \(D\), \(E\) sont de degré impair, soit \(4\) sommets ✓
À une soirée, \(7\) personnes peuvent-elles serrer chacune la main d'exactement \(3\) autres ? Et \(8\) personnes ?
Voir la correction›
lemme des poignées de main.
\(7 \times 3 = 21\) est impair : impossible. Avec \(8\) personnes, \(8 \times 3 = 24 = 2 \times 12\) : c'est possible (par exemple, les sommets d'un cube et ses \(12\) arêtes).
🔍 Vérification : un cube a \(8\) sommets de degré \(3\) ✓
On reprend le graphe orienté de la partie 2.
a) Calcule \(M^3\).
b) Combien y a-t-il de chemins de longueur \(3\) de \(2\) à \(1\) ? Écris-les.
Voir la correction›
\(M^3 = M^2M\), puis lire le coefficient.
a) \(M^3 = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}\).
b) Le coefficient \((2, 1)\) vaut \(0\) : aucun chemin de longueur \(3\) de \(2\) à \(1\). En effet, depuis \(2\) : \(2 \to 3 \to 1 \to 2\) ou \(2 \to 3 \to 1 \to 3\), jamais en \(1\).
🔍 Vérification : le coefficient \((2, 2)\) vaut \(1\) : c'est le chemin \(2 \to 3 \to 1 \to 2\) ✓
Pour un graphe non orienté de matrice \(M\), montre que le coefficient \((i, i)\) de \(M^2\) est le degré du sommet \(i\). Vérifie avec le graphe de la partie 1.
Voir la correction›
\((M^2)_{ii} = \sum_k m_{ik}m_{ki}\).
Comme \(M\) est symétrique, \(m_{ik}m_{ki} = m_{ik}^2 = m_{ik}\) (qui vaut \(0\) ou \(1\)). La somme compte les voisins de \(i\) : c'est son degré. La diagonale de \(M^2\) vaut \((2, 3, 3, 3, 1)\), les degrés de \(A\) à \(E\) ✓.
🔍 Vérification : \((M^2)_{AA} = 2\) : les chaînes \(A - B - A\) et \(A - C - A\) ✓
Un graphe a \(4\) sommets et deux arêtes : \(1 - 2\) et \(3 - 4\).
a) Écris sa matrice d'adjacence \(M\) et calcule \(M^2\) et \(M^3\).
b) Explique pourquoi le coefficient \((1, 3)\) de \(M^n\) est toujours nul.
Voir la correction›
les chemins restent dans leur « morceau ».
a) \(M = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\), \(M^2 = I_4\) et \(M^3 = M\).
b) Aucune chaîne ne relie \(1\) à \(3\) : le nombre de chemins de longueur \(n\) de \(1\) à \(3\) est toujours \(0\). Le graphe n'est pas connexe.
🔍 Vérification : \(M^n\) vaut \(I_4\) ou \(M\), et le coefficient \((1, 3)\) est nul dans les deux ✓
On reprend la météo du cours avec \(\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}\). Calcule \(\pi_1\), \(\pi_2\) et \(\pi_3\).
Voir la correction›
multiplier par \(P\) à chaque étape.
\(\pi_1 = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}\), \(\pi_2 = \begin{pmatrix} 0{,}72 & 0{,}28 \end{pmatrix}\), \(\pi_3 = \begin{pmatrix} 0{,}688 & 0{,}312 \end{pmatrix}\).
🔍 Vérification : formule de la partie 5 : \(\dfrac{2}{3} + \dfrac{0{,}064}{3} = 0{,}688\) ✓
\(P = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \\ 0{,}25 & 0{,}5 & 0{,}25 \\ 0 & 0{,}5 & 0{,}5 \end{pmatrix}\) et \(\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}\).
a) Calcule \(\pi_1\) et \(\pi_2\).
b) Vérifie que \(\pi = \begin{pmatrix} 0{,}25 & 0{,}5 & 0{,}25 \end{pmatrix}\) est invariante.
Voir la correction›
\(\pi_{n+1} = \pi_nP\), puis \(\pi P = \pi\).
a) \(\pi_1 = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \end{pmatrix}\) et \(\pi_2 = \begin{pmatrix} 0{,}25 + 0{,}125 & 0{,}25 + 0{,}25 & 0{,}125 \end{pmatrix} = \begin{pmatrix} 0{,}375 & 0{,}5 & 0{,}125 \end{pmatrix}\).
b) \(\pi P = \begin{pmatrix} 0{,}125 + 0{,}125 & 0{,}125 + 0{,}25 + 0{,}125 & 0{,}125 + 0{,}125 \end{pmatrix} = \begin{pmatrix} 0{,}25 & 0{,}5 & 0{,}25 \end{pmatrix}\) ✓.
🔍 Vérification : les coefficients de \(\pi_2\) ont pour somme \(1\) ✓
On reprend la météo : \(x_n\) est la probabilité qu'il fasse beau le jour \(n\), avec \(x_0 = 1\).
a) Montre que \(x_{n+1} = 0{,}4x_n + 0{,}4\).
b) Montre que \(y_n = x_n - \dfrac{2}{3}\) est géométrique et déduis-en \(x_n\), puis sa limite.
Voir la correction›
probabilités totales, puis suite auxiliaire.
a) \(x_{n+1} = 0{,}8x_n + 0{,}4(1 - x_n) = 0{,}4x_n + 0{,}4\).
b) \(y_{n+1} = 0{,}4x_n + 0{,}4 - \dfrac{2}{3} = 0{,}4\left(x_n - \dfrac{2}{3}\right) = 0{,}4y_n\) : géométrique de raison \(0{,}4\), \(y_0 = \dfrac{1}{3}\). Donc \(x_n = \dfrac{2}{3} + \dfrac{1}{3} \times 0{,}4^n \to \boxed{\dfrac{2}{3}}\).
🔍 Vérification : \(0{,}4 - \dfrac{2}{3} \times (1 - 0{,}4) = 0{,}4 - 0{,}4 = 0\) : le calcul de \(y_{n+1}\) est correct ✓
Démontre que \(\pi = \begin{pmatrix} \dfrac{b}{a + b} & \dfrac{a}{a + b} \end{pmatrix}\) est invariante pour \(P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix}\), en vérifiant les deux coordonnées de \(\pi P\).
Voir la correction›
calculer \(\pi P\).
Première coordonnée : \(\dfrac{b(1 - a) + ab}{a + b} = \dfrac{b}{a + b}\) ✓. Seconde : \(\dfrac{ba + a(1 - b)}{a + b} = \dfrac{a}{a + b}\) ✓. Et \(\dfrac{b}{a + b} + \dfrac{a}{a + b} = 1\).
🔍 Vérification : météo, \(a = 0{,}2\), \(b = 0{,}4\) : \(\left(\dfrac{2}{3} \;\; \dfrac{1}{3}\right)\) ✓
Une souris change de pièce chaque minute : de chacune des trois pièces, elle va dans l'une des deux autres avec la même probabilité. Elle part de la pièce \(1\).
a) Écris la matrice de transition.
b) Calcule \(\pi_1\) et \(\pi_2\).
c) Trouve la distribution invariante.
Voir la correction›
de chaque pièce, probabilité \(\dfrac{1}{2}\) vers chacune des deux autres.
a) \(P = \begin{pmatrix} 0 & 0{,}5 & 0{,}5 \\ 0{,}5 & 0 & 0{,}5 \\ 0{,}5 & 0{,}5 & 0 \end{pmatrix}\).
b) \(\pi_1 = \begin{pmatrix} 0 & 0{,}5 & 0{,}5 \end{pmatrix}\) et \(\pi_2 = \begin{pmatrix} 0{,}5 & 0{,}25 & 0{,}25 \end{pmatrix}\).
c) Par symétrie, \(\pi = \begin{pmatrix} \dfrac{1}{3} & \dfrac{1}{3} & \dfrac{1}{3} \end{pmatrix}\) : chaque coordonnée de \(\pi P\) vaut \(\dfrac{1}{2}\left(\dfrac{1}{3} + \dfrac{1}{3}\right) = \dfrac{1}{3}\) ✓.
🔍 Vérification : \(\pi_2\) a pour somme \(1\) ✓
On écrit des mots avec les lettres \(a\) et \(b\), sans jamais deux \(b\) de suite. On note \(W = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) la matrice du graphe « lettre suivante possible » (ordre \(a\), \(b\)).
a) Explique la matrice \(W\).
b) Calcule \(W^3\) et déduis-en le nombre de mots de \(4\) lettres. Vérifie en les écrivant.
Voir la correction›
un mot de \(4\) lettres est un chemin de longueur \(3\).
a) Après \(a\), on peut écrire \(a\) ou \(b\) (ligne \(1\ 1\)) ; après \(b\), seulement \(a\) (ligne \(1\ 0\)).
b) \(W^3 = \begin{pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix}\). Le nombre de mots est la somme des coefficients : \(3 + 2 + 2 + 1 = \boxed{8}\) : \(aaaa\), \(aaab\), \(aaba\), \(abaa\), \(abab\), \(baaa\), \(baab\), \(baba\).
🔍 Vérification : on retrouve la suite de Fibonacci (\(W\) est la matrice du chapitre 8) ✓
Avec la météo, calcule \(P^2\). Que représente son coefficient en bas à gauche ?
Voir la correction›
\((P^2)_{ij}\) = probabilité d'aller de \(i\) à \(j\) en deux étapes.
\(P^2 = \begin{pmatrix} 0{,}72 & 0{,}28 \\ 0{,}56 & 0{,}44 \end{pmatrix}\). Le coefficient \(0{,}56\) est la probabilité qu'il fasse beau dans deux jours sachant qu'il pleut aujourd'hui.
🔍 Vérification : \(0{,}4 \times 0{,}8 + 0{,}6 \times 0{,}4 = 0{,}32 + 0{,}24 = 0{,}56\) ✓
Avec la météo, compare \(x_3\) selon qu'il fait beau ou qu'il pleut au jour \(0\).
Voir la correction›
formule de la partie 5.
Beau au départ : \(x_3 = 0{,}688\). Pluie au départ : \(x_3 = \dfrac{2}{3} - \dfrac{2}{3} \times 0{,}064 = 0{,}624\). L'écart (\(0{,}064 = 0{,}4^3\)) diminue chaque jour : le point de départ est vite « oublié ».
🔍 Vérification : \(0{,}688 - 0{,}624 = 0{,}064\) ✓
Niveau 3Difficile/Expert (Exercices 25 à 30)
La page 1 a un lien vers les pages 2 et 3 ; la page 2 a un lien vers la page 3 ; la page 3 a un lien vers la page 1. Un internaute clique au hasard sur un des liens de la page où il se trouve.
a) Écris la matrice de transition \(P\).
b) Trouve la distribution invariante. Quelles pages sont les « plus importantes » ?
c) À la calculatrice, calcule \(\pi_0P^{30}\) avec \(\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}\). Commente.
Voir la correction›
probabilité \(\dfrac{1}{\text{nombre de liens}}\) sur chaque lien.
a) \(P = \begin{pmatrix} 0 & 0{,}5 & 0{,}5 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}\).
b) \(\pi P = \pi\) donne \(z = x\), \(0{,}5x = y\) et \(0{,}5x + y = z\). Avec \(x + y + z = 1\) : \(2{,}5x = 1\), donc \(\pi = \begin{pmatrix} 0{,}4 & 0{,}2 & 0{,}4 \end{pmatrix}\). Les pages \(1\) et \(3\) sont les plus importantes.
c) On obtient environ \(\begin{pmatrix} 0{,}4 & 0{,}2 & 0{,}4 \end{pmatrix}\) : la distribution se rapproche de la distribution invariante.
🔍 Vérification : \(\pi P = \begin{pmatrix} 0{,}4 & 0{,}2 & 0{,}2 + 0{,}2 \end{pmatrix}\) ✓
Deux boules sont réparties entre deux urnes. À chaque étape, on choisit une boule au hasard et on la change d'urne. L'état est le nombre de boules dans l'urne de gauche (\(0\), \(1\) ou \(2\)).
a) Écris la matrice de transition.
b) Vérifie que \(\begin{pmatrix} 0{,}25 & 0{,}5 & 0{,}25 \end{pmatrix}\) est invariante.
c) Avec \(\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}\), calcule \(\pi_1\) à \(\pi_4\). La suite \((\pi_n)\) converge-t-elle ?
Voir la correction›
depuis l'état \(1\), la boule choisie est à gauche ou à droite avec probabilité \(\dfrac{1}{2}\).
a) \(P = \begin{pmatrix} 0 & 1 & 0 \\ 0{,}5 & 0 & 0{,}5 \\ 0 & 1 & 0 \end{pmatrix}\).
b) \(\begin{pmatrix} 0{,}25 & 0{,}5 & 0{,}25 \end{pmatrix}P = \begin{pmatrix} 0{,}25 & 0{,}25 + 0{,}25 & 0{,}25 \end{pmatrix}\) ✓.
c) \(\pi_1 = \begin{pmatrix} 0 & 1 & 0 \end{pmatrix}\), \(\pi_2 = \begin{pmatrix} 0{,}5 & 0 & 0{,}5 \end{pmatrix}\), \(\pi_3 = \begin{pmatrix} 0 & 1 & 0 \end{pmatrix}\), \(\pi_4 = \pi_2\). La suite alterne : elle ne converge pas, bien qu'il existe une distribution invariante.
🔍 Vérification : le nombre de boules à gauche change de parité à chaque étape : on ne peut pas être dans l'état \(1\) deux étapes de suite ✓
Distribution invariante ne veut pas dire limite. Ici, la chaîne est « périodique ».
a) Écris la matrice d'adjacence \(M\) du graphe complet à \(4\) sommets.
b) Calcule \(M^2\) et interprète ses coefficients.
c) Calcule \(M^3\). Combien y a-t-il de chemins de longueur \(3\) entre deux sommets distincts ?
Voir la correction›
\(M = J - I_4\), où \(J\) n'a que des \(1\).
a) \(M\) a des \(0\) sur la diagonale et des \(1\) partout ailleurs.
b) \(M^2\) a des \(3\) sur la diagonale (le degré) et des \(2\) ailleurs : entre deux sommets distincts, il y a \(2\) chemins de longueur \(2\) (par chacun des deux autres sommets).
c) \(M^3\) a des \(6\) sur la diagonale et des \(7\) ailleurs : \(\boxed{7}\) chemins de longueur \(3\) entre deux sommets distincts.
🔍 Vérification : la somme d'une ligne de \(M^3\) compte tous les chemins de longueur \(3\) issus d'un sommet ; à chaque pas, on a \(3\) choix : \(3^3 = 27 = 6 + 3 \times 7\) ✓
\(P = \begin{pmatrix} 0{,}6 & 0{,}3 & 0{,}1 \\ 0{,}2 & 0{,}6 & 0{,}2 \\ 0{,}1 & 0{,}3 & 0{,}6 \end{pmatrix}\).
a) Écris le système vérifié par une distribution invariante \(\pi = \begin{pmatrix} x & y & z \end{pmatrix}\).
b) Résous-le.
c) À la calculatrice, compare avec \(\pi_0P^{20}\) pour \(\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}\).
Voir la correction›
\(\pi P = \pi\) et \(x + y + z = 1\).
a) \(\begin{cases} 0{,}6x + 0{,}2y + 0{,}1z = x \\ 0{,}3x + 0{,}6y + 0{,}3z = y \\ x + y + z = 1 \end{cases}\) (la troisième équation de \(\pi P = \pi\) découle des autres).
b) La deuxième donne \(0{,}3(x + z) = 0{,}4y\), et avec \(x + z = 1 - y\) : \(y = \dfrac{3}{7}\). La première donne \(0{,}2y + 0{,}1z = 0{,}4x\) ; avec \(z = \dfrac{4}{7} - x\), on obtient \(x = \dfrac{2}{7}\), puis \(z = \dfrac{2}{7}\). \(\boxed{\pi = \left(\dfrac{2}{7} \;\; \dfrac{3}{7} \;\; \dfrac{2}{7}\right)}\).
c) \(\pi_0P^{20} \approx \begin{pmatrix} 0{,}2857 & 0{,}4286 & 0{,}2857 \end{pmatrix}\) : c'est bien \(\pi\).
🔍 Vérification : \(0{,}6 \times \dfrac{2}{7} + 0{,}2 \times \dfrac{3}{7} + 0{,}1 \times \dfrac{2}{7} = \dfrac{1{,}2 + 0{,}6 + 0{,}2}{7} = \dfrac{2}{7}\) ✓
Démontre par récurrence que, pour tout \(n \geqslant 1\), le coefficient \((i, j)\) de \(M^n\) est le nombre de chemins de longueur \(n\) de \(i\) à \(j\).
Voir la correction›
récurrence sur \(n\), en coupant le chemin avant le dernier arc.
Étape 1 — Initialisation. Pour \(n = 1\), \(m_{ij}\) compte les arcs de \(i\) vers \(j\), c'est-à-dire les chemins de longueur \(1\) ✓.
Étape 2 — Hérédité. Supposons le résultat vrai pour \(n\). Un chemin de longueur \(n + 1\) de \(i\) à \(j\) est un chemin de longueur \(n\) de \(i\) à un sommet \(k\), suivi d'un arc de \(k\) vers \(j\). Leur nombre est \(\sum_k (M^n)_{ik} \, m_{kj}\), qui est le coefficient \((i, j)\) de \(M^nM = M^{n+1}\) ✓.
🔍 Vérification : pour \(n = 2\), on retrouve la démonstration du cours ✓
\(P = \begin{pmatrix} 1 - a & a \\ b & 1 - b \end{pmatrix}\) avec \(a + b > 0\), et \(\pi_n = \begin{pmatrix} x_n & 1 - x_n \end{pmatrix}\).
a) Montre que \(x_n = \dfrac{b}{a + b} + \left(x_0 - \dfrac{b}{a + b}\right)(1 - a - b)^n\).
b) Retrouve la convergence quand \(0 < a + b < 2\).
c) Que se passe-t-il si \(a = b = 1\) ? Et si \(a + b = 0\) ?
Voir la correction›
suite arithmético-géométrique.
a) \(x_{n+1} = (1 - a - b)x_n + b\). Avec \(x = \dfrac{b}{a + b}\), on a \(x = (1 - a - b)x + b\), donc \(x_{n+1} - x = (1 - a - b)(x_n - x)\), d'où la formule.
b) Si \(0 < a + b < 2\), alors \(-1 < 1 - a - b < 1\), donc \((1 - a - b)^n \to 0\) et \(x_n \to \dfrac{b}{a + b}\).
c) Si \(a = b = 1\) : \((1 - a - b)^n = (-1)^n\), la suite alterne (sauf si \(x_0 = \dfrac{1}{2}\)). Si \(a + b = 0\), alors \(a = b = 0\) : \(P = I_2\), rien ne bouge et toute distribution est invariante.
🔍 Vérification : météo, \(1 - a - b = 0{,}4\) : on retrouve \(x_n = \dfrac{2}{3} + \left(x_0 - \dfrac{2}{3}\right) \times 0{,}4^n\) ✓
Un avis sur ce chapitre ? Donne-le en quelques mots