QCM : Chaines de Markov

[enonce]
Ce QCM porte sur les chaînes de Markov : matrice de transition, lecture d'un graphe probabiliste, évolution d'une distribution et état stable. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
Parmi les matrices suivantes, laquelle peut être la matrice de transition d'une chaîne de Markov à deux états ?
[qcm]
[option]$\begin{pmatrix} 0{,}3 & 0{,}6 \\ 0{,}7 & 0{,}4 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}4 & 0{,}4 \\ 0{,}5 & 0{,}5 \end{pmatrix}$[/option]
[option correct="true"]$\begin{pmatrix} 0{,}3 & 0{,}7 \\ 0{,}6 & 0{,}4 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 1{,}2 & -0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$[/option]
[reponse statut="correct"]Bonne réponse !
Tous les coefficients sont compris entre $0$ et $1$, et la somme de chaque ligne vaut $1$ : $0{,}3 + 0{,}7 = 1$ et $0{,}6 + 0{,}4 = 1$. C'est bien une matrice stochastique.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}3 & 0{,}6 \\ 0{,}7 & 0{,}4 \end{pmatrix}$"]Non.
Le piège est de contrôler les colonnes au lieu des lignes. Vérifier plutôt la somme de chaque ligne de cette matrice.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}4 & 0{,}4 \\ 0{,}5 & 0{,}5 \end{pmatrix}$"]Non.
Recalculer la somme des coefficients de la première ligne : décrit-elle bien une répartition complète des probabilités au départ d'un état ?[/reponse]
[reponse motif="$\begin{pmatrix} 1{,}2 & -0{,}2 \\ 0{,}5 & 0{,}5 \end{pmatrix}$"]Non.
Observer attentivement les deux coefficients de la première ligne : un coefficient d'une matrice de transition peut-il prendre de telles valeurs ?[/reponse]
[reponse statut="incorrect"]Non.
Une matrice de transition est stochastique : ses coefficients sont compris entre $0$ et $1$ et la somme de chaque ligne vaut $1$.[/reponse]
[/qcm]
[/etape]

[etape]
Une entreprise répartit ses clients chaque mois entre deux offres $A$ et $B$. Les transitions d'un mois au suivant sont décrites par le graphe probabiliste ci-dessous (états classés dans l'ordre $A$, $B$).

Graphe probabiliste à deux états A et B avec boucles et arcs pondérés par les probabilités de transition

Quelle est la matrice de transition $P$ associée à ce graphe ?
[qcm]
[option correct="true"]$\begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}7 & 0{,}4 \\ 0{,}3 & 0{,}6 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}3 & 0{,}7 \\ 0{,}6 & 0{,}4 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}3 & 0{,}7 \end{pmatrix}$[/option]
[reponse statut="correct"]Exactement !
La ligne $1$ décrit les départs de $A$ : la boucle $A \to A$ donne $0{,}7$ et l'arc $A \to B$ donne $0{,}3$. La ligne $2$ décrit les départs de $B$ : $B \to A$ donne $0{,}4$ et la boucle $B \to B$ donne $0{,}6$. Chaque ligne a bien pour somme $1$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}7 & 0{,}4 \\ 0{,}3 & 0{,}6 \end{pmatrix}$"]Non.
Les arcs $A \to B$ et $B \to A$ semblent avoir été rangés dans les colonnes au lieu des lignes. Relire ce que représente une ligne de $P$ : tous les départs d'un même état.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}3 & 0{,}7 \\ 0{,}6 & 0{,}4 \end{pmatrix}$"]Non.
Pour chaque état, repérer d'abord l'arc qui revient sur lui-même (la boucle) avant l'arc qui part vers l'autre état.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}3 & 0{,}7 \end{pmatrix}$"]Non.
Vérifier dans quel ordre les états sont classés : la première ligne doit décrire les départs de l'état $A$, pas ceux de $B$.[/reponse]
[reponse statut="incorrect"]Non.
Le coefficient $P_{i,j}$ se lit sur l'arc orienté de l'état $i$ vers l'état $j$ ; chaque ligne regroupe tous les départs d'un même état.[/reponse]
[/qcm]
[/etape]

[etape]
On reprend la matrice $P = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$ précédente. Au mois $0$, tous les clients ont choisi l'offre $A$, donc $\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. Quelle est la distribution $\pi_1$ au mois suivant ?
[qcm]
[option]$\begin{pmatrix} 1 & 0 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}7 & 0{,}4 \end{pmatrix}$[/option]
[option correct="true"]$\begin{pmatrix} 0{,}7 & 0{,}3 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}3 & 0{,}7 \end{pmatrix}$[/option]
[reponse statut="correct"]Bravo !
On calcule $\pi_1 = \pi_0 \times P = \begin{pmatrix} 1 & 0 \end{pmatrix} P$, ce qui sélectionne la première ligne de $P$ : $\pi_1 = \begin{pmatrix} 0{,}7 & 0{,}3 \end{pmatrix}$.[/reponse]
[reponse motif="$\begin{pmatrix} 1 & 0 \end{pmatrix}$"]Non.
Cela reviendrait à laisser la distribution inchangée. Or l'état évolue : il faut effectuer le produit $\pi_0 \times P$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}7 & 0{,}4 \end{pmatrix}$"]Non.
La première colonne de $P$ semble avoir été lue au lieu de la première ligne. Bien identifier quelle partie de $P$ est sélectionnée par le produit $\begin{pmatrix} 1 & 0 \end{pmatrix} \times P$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}3 & 0{,}7 \end{pmatrix}$"]Non.
Les deux composantes paraissent inversées. Reprendre l'ordre des états $A$ puis $B$ dans le résultat.[/reponse]
[reponse statut="incorrect"]Non.
La distribution évolue par $\pi_1 = \pi_0 \times P$, vecteur ligne multiplié à gauche de la matrice.[/reponse]
[/qcm]
[/etape]

[etape]
Avec la même matrice $P = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}4 & 0{,}6 \end{pmatrix}$ et $\pi_1 = \begin{pmatrix} 0{,}7 & 0{,}3 \end{pmatrix}$, quelle est la distribution $\pi_2$ au mois suivant ?
[qcm]
[option]$\begin{pmatrix} 0{,}49 & 0{,}09 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}55 & 0{,}45 \end{pmatrix}$[/option]
[option correct="true"]$\begin{pmatrix} 0{,}61 & 0{,}39 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}39 & 0{,}61 \end{pmatrix}$[/option]
[reponse statut="correct"]Tout à fait !
On effectue $\pi_2 = \pi_1 \times P$ : la première composante vaut $0{,}7 \times 0{,}7 + 0{,}3 \times 0{,}4 = 0{,}49 + 0{,}12 = 0{,}61$ et la seconde $0{,}7 \times 0{,}3 + 0{,}3 \times 0{,}6 = 0{,}21 + 0{,}18 = 0{,}39$. La somme $0{,}61 + 0{,}39 = 1$ confirme le calcul.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}49 & 0{,}09 \end{pmatrix}$"]Non.
Il semble que seuls les coefficients diagonaux de $P$ aient été élevés au carré. Le produit $\pi_1 \times P$ combine chaque composante de $\pi_1$ avec une colonne entière de $P$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}55 & 0{,}45 \end{pmatrix}$"]Non.
Reprendre le produit terme à terme : chaque composante de $\pi_2$ additionne deux produits, pas une simple moyenne des coefficients.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}39 & 0{,}61 \end{pmatrix}$"]Non.
Les deux composantes paraissent permutées. Vérifier quelle colonne de $P$ donne la probabilité de l'état $A$ et laquelle donne celle de $B$.[/reponse]
[reponse statut="incorrect"]Non.
Chaque composante de $\pi_2 = \pi_1 \times P$ est une somme de produits ligne par colonne ; les composantes doivent encore avoir pour somme $1$.[/reponse]
[/qcm]
[/etape]

[etape]
Une chaîne de Markov à deux états a pour matrice de transition $P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}4 & 0{,}6 \end{pmatrix}$. Quel est son état stable $\pi = \begin{pmatrix} x & y \end{pmatrix}$ ?
[qcm]
[option]$\begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}$[/option]
[option correct="true"]$\begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}2 & 0{,}8 \end{pmatrix}$[/option]
[option]$\begin{pmatrix} 0{,}9 & 0{,}1 \end{pmatrix}$[/option]
[reponse statut="correct"]C'est bien ça !
L'égalité $\pi = \pi \times P$ donne $x = 0{,}9\,x + 0{,}4\,y$, soit $0{,}1\,x = 0{,}4\,y$, donc $x = 4y$. Avec la condition $x + y = 1$, on obtient $5y = 1$, d'où $y = 0{,}2$ et $x = 0{,}8$. On vérifie : $\begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix} \times P = \begin{pmatrix} 0{,}8 & 0{,}2 \end{pmatrix}$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}$"]Non.
Un état stable n'est pas une simple répartition égale entre les deux états : il faut le déterminer en résolvant $\pi = \pi \times P$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}2 & 0{,}8 \end{pmatrix}$"]Non.
Les deux composantes semblent inversées. Reprendre la relation entre $x$ et $y$ obtenue à partir de $\pi = \pi \times P$.[/reponse]
[reponse motif="$\begin{pmatrix} 0{,}9 & 0{,}1 \end{pmatrix}$"]Non.
Une ligne de $P$ n'est pas l'état stable. L'état stable se trouve en résolvant le système $\pi = \pi \times P$ avec la condition de somme égale à $1$.[/reponse]
[reponse statut="incorrect"]Non.
L'état stable vérifie $\pi = \pi \times P$ ; on le détermine en résolvant ce système complété par la condition $x + y = 1$.[/reponse]
[/qcm]
[/etape]

[etape]
Dans le chapitre, on rencontre la matrice de transition d'une chaîne de Markov et la matrice d'adjacence d'un graphe. Quelle affirmation les distingue correctement ?
[qcm]
[option]Ce sont deux noms différents pour le même objet.[/option]
[option]La matrice de transition compte des arêtes, la matrice d'adjacence contient des probabilités.[/option]
[option correct="true"]La matrice de transition contient des probabilités, avec une somme de $1$ sur chaque ligne ; la matrice d'adjacence contient des entiers qui comptent des arêtes ou des arcs.[/option]
[option]Les deux ont des coefficients dont chaque ligne a pour somme $1$.[/option]
[reponse statut="correct"]Tu as raison !
La matrice de transition $P$ a des coefficients réels compris entre $0$ et $1$ (des probabilités) et chaque ligne a pour somme $1$. La matrice d'adjacence a des coefficients entiers qui dénombrent les arêtes ou les arcs entre deux sommets : ce sont deux objets distincts.[/reponse]
[reponse motif="Ce sont deux noms différents pour le même objet."]Non.
Comparer la nature des coefficients de chacune : des probabilités d'un côté, des entiers de l'autre. Cela suffit à montrer que ce sont deux objets différents.[/reponse]
[reponse motif="La matrice de transition compte des arêtes, la matrice d'adjacence contient des probabilités."]Non.
Les deux rôles sont intervertis ici. Redéfinir ce que contient chaque matrice avant de conclure.[/reponse]
[reponse motif="Les deux ont des coefficients dont chaque ligne a pour somme $1$."]Non.
La propriété « somme de chaque ligne égale à $1$ » ne caractérise que l'une des deux matrices. Vérifier ce que vaut la somme d'une ligne d'une matrice d'adjacence.[/reponse]
[reponse statut="incorrect"]Non.
La matrice de transition est stochastique (probabilités, lignes de somme $1$) ; la matrice d'adjacence est entière et compte des arêtes ou des arcs.[/reponse]
[/qcm]
[/etape]

Chaine de Markov : etat stable d’un systeme

Sur une autoroute, chaque véhicule qui se présente à une barrière de péage utilise l'une des trois files suivantes :

la file automatique par carte bancaire (état $A$) ;
la file manuelle avec un agent (état $M$) ;
la file de télépéage sans arrêt (état $T$).

Une étude statistique modélise le choix d'un même conducteur d'un passage au suivant par une chaîne de Markov. D'un passage à l'autre :

un conducteur de la file $A$ reprend $A$ avec la probabilité $0{,}7$, passe à $M$ avec la probabilité $0{,}1$ et à $T$ avec la probabilité $0{,}2$ ;
un conducteur de la file $M$ passe à $A$ avec la probabilité $0{,}3$, reprend $M$ avec la probabilité $0{,}5$ et passe à $T$ avec la probabilité $0{,}2$ ;
un conducteur de la file $T$ passe à $A$ avec la probabilité $0{,}1$, à $M$ avec la probabilité $0{,}1$ et reprend $T$ avec la probabilité $0{,}8$.

Graphe probabiliste à 3 états A, M et T avec arcs et boucles pondérés par les probabilités de transition entre les files de péage

On classe les états dans l'ordre $A$, $M$, $T$.

Déterminer la matrice de transition $P$ de cette chaîne de Markov et vérifier qu'elle est stochastique.
Au premier passage observé, un conducteur emprunte la file automatique : on prend donc $\pi_0 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix}$.
1. Calculer $\pi_1$, puis $\pi_2$.
2. Interpréter chaque composante de $\pi_2$.
On cherche une distribution $\pi = \begin{pmatrix} x & y & z \end{pmatrix}$ stable au cours du temps.
1. Écrire le système traduisant $\pi = \pi \times P$.
2. Déterminer $\pi$ (valeurs exactes) en tenant compte de la condition de normalisation.
Interpréter le comportement à long terme du système et le comparer à $\pi_2$.

Corrigé

Chaque arc orienté de l'état $i$ vers l'état $j$ fournit le coefficient $P_{i,j}$ (les boucles donnent les coefficients diagonaux). Dans l'ordre $A$, $M$, $T$ :

$P = \begin{pmatrix} 0{,}7 & 0{,}1 & 0{,}2 \\ 0{,}3 & 0{,}5 & 0{,}2 \\ 0{,}1 & 0{,}1 & 0{,}8 \end{pmatrix}$

Tous les coefficients sont compris entre $0$ et $1$ et chaque ligne a pour somme $1$ : $0{,}7 + 0{,}1 + 0{,}2 = 1$, $0{,}3 + 0{,}5 + 0{,}2 = 1$ et $0{,}1 + 0{,}1 + 0{,}8 = 1$. La matrice $P$ est donc bien stochastique.
1. La distribution après un passage est $\pi_1 = \pi_0 \times P$, c'est-à-dire la première ligne de $P$ :
  
  $\pi_1 = \begin{pmatrix} 1 & 0 & 0 \end{pmatrix} P = \begin{pmatrix} 0{,}7 & 0{,}1 & 0{,}2 \end{pmatrix}$
  
  On calcule ensuite $\pi_2 = \pi_1 \times P$ en effectuant le produit ligne par colonne :
  - file $A$ : $0{,}7 \times 0{,}7 + 0{,}1 \times 0{,}3 + 0{,}2 \times 0{,}1 = 0{,}49 + 0{,}03 + 0{,}02 = 0{,}54$ ;
  - file $M$ : $0{,}7 \times 0{,}1 + 0{,}1 \times 0{,}5 + 0{,}2 \times 0{,}1 = 0{,}07 + 0{,}05 + 0{,}02 = 0{,}14$ ;
  - file $T$ : $0{,}7 \times 0{,}2 + 0{,}1 \times 0{,}2 + 0{,}2 \times 0{,}8 = 0{,}14 + 0{,}02 + 0{,}16 = 0{,}32$.
  D'où $\pi_2$ = $\mathbf{\begin{pmatrix} 0{,}54 & 0{,}14 & 0{,}32 \end{pmatrix}}$. La somme $0{,}54 + 0{,}14 + 0{,}32 = 1$ confirme le résultat.
2. Au deuxième passage, le conducteur emprunte la file automatique avec la probabilité $0{,}54$, la file manuelle avec la probabilité $0{,}14$ et la file de télépéage avec la probabilité $0{,}32$.
1. L'égalité $\begin{pmatrix} x & y & z \end{pmatrix} = \begin{pmatrix} x & y & z \end{pmatrix} P$ se traduit, colonne par colonne, par :
  
  $\left\{ \begin{array}{l} x = 0{,}7\,x + 0{,}3\,y + 0{,}1\,z \\ y = 0{,}1\,x + 0{,}5\,y + 0{,}1\,z \\ z = 0{,}2\,x + 0{,}2\,y + 0{,}8\,z \end{array} \right.$
2. La troisième équation étant redondante, on l'abandonne et on simplifie les deux premières :
  - $x = 0{,}7\,x + 0{,}3\,y + 0{,}1\,z$ donne $0{,}3\,x = 0{,}3\,y + 0{,}1\,z$, soit $3x = 3y + z$ ;
  - $y = 0{,}1\,x + 0{,}5\,y + 0{,}1\,z$ donne $0{,}5\,y = 0{,}1\,x + 0{,}1\,z$, soit $5y = x + z$.
  De la première relation, $z = 3x - 3y$. On reporte dans $5y = x + z$ :
  
  $5y = x + (3x - 3y) = 4x - 3y$
  
  soit $8y = 4x$, donc $x = 2y$. On en déduit $z = 3 \times 2y - 3y = 3y$.
  
  La condition de normalisation $x + y + z = 1$ donne alors :
  
  $2y + y + 3y = 6y = 1$
  
  d'où $y = \dfrac{1}{6}$, puis $x = 2y = \dfrac{1}{3}$ et $z = 3y = \dfrac{1}{2}$. Toutes les composantes sont positives et leur somme vaut $\dfrac{1}{3} + \dfrac{1}{6} + \dfrac{1}{2} = \dfrac{2 + 1 + 3}{6} = 1$.
  
  La distribution stable est $\mathbf{\pi}$ = $\mathbf{\begin{pmatrix} \dfrac{1}{3} & \dfrac{1}{6} & \dfrac{1}{2} \end{pmatrix}}$.
La chaîne est régulière (tous les coefficients de $P$ sont strictement positifs), donc la suite $\pi_n$ converge vers la distribution stable $\pi$, quelle que soit la file de départ. À long terme, la répartition des passages se stabilise autour de $\dfrac{1}{3} \approx 0{,}33$ pour la file automatique, $\dfrac{1}{6} \approx 0{,}17$ pour la file manuelle et $\dfrac{1}{2} = 0{,}5$ pour le télépéage : environ la moitié des passages se font à terme par le télépéage.

On retrouve déjà cette tendance dès le deuxième passage : la composante de la file $A$ passe de $1$ à $0{,}54$ et celle du télépéage monte à $0{,}32$, $\pi_2$ se rapprochant progressivement de $\pi$.

Chaine de Markov : evolution d’abonnements

Une plateforme de streaming étudie la fidélité de son public mois après mois. Chaque utilisateur est dans l'un des deux états suivants : abonné (état $A$) ou non-abonné (état $N$). Les relevés du service marketing établissent que, d'un mois au suivant :

un abonné conserve son abonnement avec la probabilité $0{,}85$ et le résilie avec la probabilité $0{,}15$ ;
un non-abonné souscrit un abonnement avec la probabilité $0{,}20$ et reste non-abonné avec la probabilité $0{,}80$.

On modélise la situation par une chaîne de Markov à deux états $A$ et $N$. Pour tout entier naturel $n$, on note $\pi_n = \begin{pmatrix} a_n & b_n \end{pmatrix}$ la distribution de probabilité au mois $n$, où $a_n$ (respectivement $b_n$) est la probabilité qu'un utilisateur choisi au hasard soit abonné (respectivement non-abonné) au mois $n$.

Au lancement de l'offre (mois $0$), un utilisateur sur trois est déjà abonné : on prend $\pi_0 = \begin{pmatrix} 0{,}3 & 0{,}7 \end{pmatrix}$.

1. Représenter cette chaîne de Markov par un graphe probabiliste.
2. Donner la matrice de transition $P$ en classant les états dans l'ordre $A$, $N$, et vérifier qu'elle est stochastique.
1. Calculer $\pi_1$.
2. Calculer $\pi_2$, puis $\pi_3$.
3. Interpréter l'évolution de la proportion d'abonnés au cours de ces trois mois.
On garde la même matrice $P$ mais on suppose maintenant qu'au mois $0$, tous les utilisateurs sont abonnés : $\pi'_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. Calculer $\pi'_1$, $\pi'_2$ et $\pi'_3$, puis comparer cette évolution à celle de la question 2.

Corrigé

Question 1

a. Chaque flèche porte la probabilité de passer d'un état à l'autre d'un mois sur le suivant ; les boucles correspondent au maintien dans l'état.

Graphe probabiliste a deux etats A (abonne) et N (non-abonne) avec boucles et arcs portant les probabilites de transition

b. En classant les états dans l'ordre $A$, $N$, on reporte chaque probabilité dans la case correspondante : la ligne $i$ décrit le devenir de l'état $i$.

$P = \begin{pmatrix} 0{,}85 & 0{,}15 \\ 0{,}20 & 0{,}80 \end{pmatrix}$

Tous les coefficients sont compris entre $0$ et $1$ et la somme de chaque ligne vaut $1$ : $0{,}85 + 0{,}15 = 1$ et $0{,}20 + 0{,}80 = 1$. La matrice $P$ est donc stochastique.

Question 2

a. On calcule $\pi_1 = \pi_0 \times P$ :

$\pi_1 = \begin{pmatrix} 0{,}3 & 0{,}7 \end{pmatrix} \begin{pmatrix} 0{,}85 & 0{,}15 \\ 0{,}20 & 0{,}80 \end{pmatrix}$

Le détail du produit ligne par colonne donne $0{,}3 \times 0{,}85 + 0{,}7 \times 0{,}20 = 0{,}255 + 0{,}14 = 0{,}395$ pour l'état $A$, et $0{,}3 \times 0{,}15 + 0{,}7 \times 0{,}80 = 0{,}045 + 0{,}56 = 0{,}605$ pour l'état $N$.

$\mathbf{\pi_1 = \begin{pmatrix} 0{,}395 & 0{,}605 \end{pmatrix}}$

b. On enchaîne $\pi_2 = \pi_1 \times P$ :

$a_2 = 0{,}395 \times 0{,}85 + 0{,}605 \times 0{,}20 = 0{,}335\,75 + 0{,}121 = 0{,}456\,75$
$b_2 = 0{,}395 \times 0{,}15 + 0{,}605 \times 0{,}80 = 0{,}059\,25 + 0{,}484 = 0{,}543\,25$

$\mathbf{\pi_2 = \begin{pmatrix} 0{,}456\,75 & 0{,}543\,25 \end{pmatrix}}$

Puis $\pi_3 = \pi_2 \times P$ :

$a_3 = 0{,}456\,75 \times 0{,}85 + 0{,}543\,25 \times 0{,}20 = 0{,}388\,237\,5 + 0{,}108\,65 = 0{,}496\,887\,5$
$b_3 = 0{,}456\,75 \times 0{,}15 + 0{,}543\,25 \times 0{,}80 = 0{,}068\,512\,5 + 0{,}434\,6 = 0{,}503\,112\,5$

Arrondi au millième : $\mathbf{\pi_3 \approx \begin{pmatrix} 0{,}497 & 0{,}503 \end{pmatrix}}$.

c. La proportion d'abonnés passe de $0{,}3$ au mois $0$ à $0{,}395$, puis $0{,}457$ et enfin environ $0{,}497$ au mois $3$. Elle augmente régulièrement et se rapproche de $0{,}5$. La plateforme gagne donc des abonnés mois après mois, mais la progression ralentit : les gains successifs ($+0{,}095$, puis $+0{,}062$, puis $+0{,}040$) diminuent, ce qui suggère une stabilisation à venir.

Question 3

On part cette fois de $\pi'_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$. La première étape est simplement la première ligne de $P$ :

$\pi'_1 = \begin{pmatrix} 1 & 0 \end{pmatrix} P = \begin{pmatrix} 0{,}85 & 0{,}15 \end{pmatrix}$

Ensuite $\pi'_2 = \pi'_1 \times P$ :

$0{,}85 \times 0{,}85 + 0{,}15 \times 0{,}20 = 0{,}722\,5 + 0{,}03 = 0{,}752\,5$
$0{,}85 \times 0{,}15 + 0{,}15 \times 0{,}80 = 0{,}127\,5 + 0{,}12 = 0{,}247\,5$

soit $\pi'_2 = \begin{pmatrix} 0{,}752\,5 & 0{,}247\,5 \end{pmatrix}$. Enfin $\pi'_3 = \pi'_2 \times P$ :

$0{,}752\,5 \times 0{,}85 + 0{,}247\,5 \times 0{,}20 = 0{,}639\,625 + 0{,}049\,5 = 0{,}689\,125$
$0{,}752\,5 \times 0{,}15 + 0{,}247\,5 \times 0{,}80 = 0{,}112\,875 + 0{,}198 = 0{,}310\,875$

Arrondi au millième : $\mathbf{\pi'_3 \approx \begin{pmatrix} 0{,}689 & 0{,}311 \end{pmatrix}}$.

Ici la proportion d'abonnés part de $1$ et diminue ($1 \to 0{,}85 \to 0{,}752\,5 \to 0{,}689$), alors qu'à la question 2 elle partait de $0{,}3$ et augmentait. Les deux suites évoluent en sens contraire mais se rapprochent l'une de l'autre : au mois $3$, on a environ $0{,}497$ d'un côté et $0{,}689$ de l'autre, et l'écart se réduit à chaque mois. Quelle que soit la répartition de départ, la chaîne tend vers une même répartition d'équilibre, proche de $\begin{pmatrix} 0{,}571 & 0{,}429 \end{pmatrix}$ (soit $\tfrac{4}{7}$ d'abonnés et $\tfrac{3}{7}$ de non-abonnés).

QCM Bilan : Graphes

[enonce]
Ce QCM bilan couvre l'ensemble du chapitre : matrice d'adjacence, chaînes de Markov, plus court chemin (Dijkstra), coloration (nombre chromatique) et synthèse des notions de graphes. Choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
À quoi sert l'algorithme de Dijkstra ?
[qcm]
[option]Déterminer si un graphe possède une chaîne eulérienne.[/option]
[option]Compter les chaînes de longueur fixée entre deux sommets.[/option]
[option correct="true"]Trouver un plus court chemin entre deux sommets d'un graphe pondéré à poids positifs.[/option]
[option]Calculer le nombre chromatique d'un graphe.[/option]
[reponse statut="correct"]Exactement !
L'algorithme de Dijkstra construit un plus court chemin (au sens du poids total) entre un sommet de départ et un sommet d'arrivée, à condition que tous les poids des arêtes soient positifs.[/reponse]
[reponse motif="Déterminer si un graphe possède une chaîne eulérienne."]Non.
Cette question relève du théorème d'Euler (compter les sommets de degré impair), pas d'un algorithme de plus court chemin. Dijkstra ne s'occupe que des distances pondérées.[/reponse]
[reponse motif="Compter les chaînes de longueur fixée entre deux sommets."]Non.
Le comptage des chaînes de longueur $k$ s'obtient par les puissances de la matrice d'adjacence. Dijkstra ne dénombre pas, il optimise une distance.[/reponse]
[reponse motif="Calculer le nombre chromatique d'un graphe."]Non.
Le nombre chromatique se détermine par un encadrement (degré max et sous-graphes complets) puis un coloriage explicite. Dijkstra ne traite pas la coloration.[/reponse]
[reponse statut="incorrect"]Non.
Dijkstra fournit un plus court chemin entre deux sommets dans un graphe pondéré à poids positifs.[/reponse]
[/qcm]
[/etape]

[etape]
À quelle hypothèse l'algorithme de Dijkstra ne fournit-il plus nécessairement la bonne réponse ?
[qcm]
[option]Le graphe est non orienté.[/option]
[option correct="true"]Certains poids des arêtes sont négatifs.[/option]
[option]Le graphe contient un cycle.[/option]
[option]Plusieurs sommets ont le même degré.[/option]
[reponse statut="correct"]Bonne réponse !
Dijkstra repose sur le principe que la distance d'un sommet déjà traité ne peut plus diminuer. En présence d'arêtes de poids négatif, cette propriété tombe : un détour par une arête de poids négatif peut raccourcir une distance déjà fixée.[/reponse]
[reponse motif="Le graphe est non orienté."]Non.
Dijkstra fonctionne aussi bien sur des graphes orientés que non orientés. Cette caractéristique ne change rien à la validité de l'algorithme.[/reponse]
[reponse motif="Le graphe contient un cycle."]Non.
La présence de cycles ne pose aucun problème tant que les poids restent positifs. L'algorithme passe simplement au sommet non traité de plus petite distance, sans se soucier des cycles.[/reponse]
[reponse motif="Plusieurs sommets ont le même degré."]Non.
Le degré ne joue aucun rôle dans l'algorithme : seules les distances et les poids des arêtes sont utilisés. Avoir des degrés égaux n'a aucun effet sur le résultat.[/reponse]
[reponse statut="incorrect"]Non.
Dijkstra suppose que tous les poids sont positifs ; en présence de poids négatifs, il peut renvoyer une réponse fausse.[/reponse]
[/qcm]
[/etape]

[etape]
Que désigne le nombre chromatique d'un graphe ?
[qcm]
[option]Le nombre total d'arêtes du graphe.[/option]
[option]Le degré le plus élevé parmi tous les sommets.[/option]
[option correct="true"]Le plus petit nombre de couleurs nécessaire pour colorier les sommets sans que deux sommets adjacents partagent une même couleur.[/option]
[option]Le nombre de sommets que l'on peut isoler dans un sous-graphe complet.[/option]
[reponse statut="correct"]C'est bien ça !
Le nombre chromatique, noté $\chi$, est le minimum du nombre de couleurs permettant un coloriage propre du graphe (sommets adjacents toujours de couleurs distinctes).[/reponse]
[reponse motif="Le nombre total d'arêtes du graphe."]Non.
Le nombre d'arêtes ne dépend que de la structure du graphe, pas du coloriage. Le nombre chromatique mesure une difficulté de coloriage, pas une quantité combinatoire d'arêtes.[/reponse]
[reponse motif="Le degré le plus élevé parmi tous les sommets."]Non.
Le degré maximum $d_{\max}$ sert à majorer le nombre chromatique ($\chi \leqslant d_{\max} + 1$), mais il ne lui est pas égal en général.[/reponse]
[reponse motif="Le nombre de sommets que l'on peut isoler dans un sous-graphe complet."]Non.
La taille du plus grand sous-graphe complet (clique) minore le nombre chromatique, mais ne le donne pas exactement. Pour certains graphes, $\chi$ est strictement supérieur à cette taille.[/reponse]
[reponse statut="incorrect"]Non.
Le nombre chromatique est le plus petit nombre de couleurs permettant un coloriage propre des sommets.[/reponse]
[/qcm]
[/etape]

[etape]
Soit un graphe dont le degré maximal vaut $d_{\max} = 4$ et qui contient un sous-graphe complet à $3$ sommets (un triangle). Que peut-on affirmer sur son nombre chromatique $\chi$ ?
[qcm]
[option]$\chi = 3$.[/option]
[option]$\chi = 5$.[/option]
[option correct="true"]$3 \leqslant \chi \leqslant 5$.[/option]
[option]$\chi = 4$.[/option]
[reponse statut="correct"]Tu as raison !
On a deux encadrements : le sous-graphe complet à $3$ sommets impose $\chi \geqslant 3$ ; le théorème de majoration donne $\chi \leqslant d_{\max} + 1 = 5$. Donc $\chi$ est compris entre $3$ et $5$, sans pouvoir être déterminé exactement à ce stade.[/reponse]
[reponse motif="$\chi = 3$."]Non.
La présence d'un triangle assure $\chi \geqslant 3$, mais pas l'égalité. Selon la structure du graphe, $\chi$ peut très bien valoir $4$ ou $5$.[/reponse]
[reponse motif="$\chi = 5$."]Non.
La valeur $5$ est seulement la borne supérieure donnée par $d_{\max} + 1$. Cette borne n'est pas toujours atteinte : la plupart des graphes ont un nombre chromatique strictement inférieur.[/reponse]
[reponse motif="$\chi = 4$."]Non.
Sans information supplémentaire, on ne peut conclure à l'égalité $\chi = 4$. Les seules informations sûres sont les bornes : $3 \leqslant \chi \leqslant 5$.[/reponse]
[reponse statut="incorrect"]Non.
Avec un sous-graphe complet à $3$ sommets, $\chi \geqslant 3$. Avec $d_{\max} = 4$, $\chi \leqslant 5$. Donc $3 \leqslant \chi \leqslant 5$.[/reponse]
[/qcm]
[/etape]

[etape]
Lors de l'application de l'algorithme de Dijkstra, comment choisit-on à chaque étape le prochain sommet à traiter ?
[qcm]
[option]On prend le sommet de plus grand degré non encore traité.[/option]
[option correct="true"]On prend le sommet non encore traité ayant la plus petite distance provisoire.[/option]
[option]On prend un sommet adjacent au sommet de départ pris au hasard.[/option]
[option]On prend le sommet de plus petit numéro non encore traité.[/option]
[reponse statut="correct"]Bravo !
À chaque étape, on sélectionne parmi les sommets non encore traités celui dont la distance provisoire au sommet de départ est minimale. Une fois ce sommet choisi, on met à jour les distances de ses voisins.[/reponse]
[reponse motif="On prend le sommet de plus grand degré non encore traité."]Non.
Le degré d'un sommet ne participe pas à l'algorithme. Dijkstra utilise uniquement les distances provisoires et les poids des arêtes.[/reponse]
[reponse motif="On prend un sommet adjacent au sommet de départ pris au hasard."]Non.
Le choix doit être déterministe pour garantir un plus court chemin. Prendre un voisin au hasard ne garantit pas que sa distance soit minimale parmi les sommets non encore traités.[/reponse]
[reponse motif="On prend le sommet de plus petit numéro non encore traité."]Non.
Le numéro du sommet ne joue aucun rôle dans l'algorithme. Le critère de sélection est la plus petite distance provisoire courante.[/reponse]
[reponse statut="incorrect"]Non.
À chaque étape, on choisit le sommet non encore traité ayant la plus petite distance provisoire au sommet de départ.[/reponse]
[/qcm]
[/etape]

[etape]
Lequel des énoncés suivants est faux ?
[qcm]
[option]Pour un graphe non orienté simple, la matrice d'adjacence est symétrique.[/option]
[option]Le nombre chromatique d'un graphe est toujours inférieur ou égal à $d_{\max} + 1$.[/option]
[option correct="true"]Tout graphe connexe admet une chaîne eulérienne.[/option]
[option]Le coefficient $(M^{2})_{i,j}$ donne le nombre de chaînes de longueur $2$ allant de $i$ à $j$.[/option]
[reponse statut="correct"]Exactement !
Cet énoncé est faux : la connexité ne suffit pas. Il faut en plus que le graphe ait $0$ ou $2$ sommets de degré impair (théorème d'Euler). Les trois autres propositions correspondent à des résultats du cours.[/reponse]
[reponse motif="Pour un graphe non orienté simple, la matrice d'adjacence est symétrique."]Non, cette affirmation est vraie : pour un graphe non orienté, $M_{i,j} = M_{j,i}$ par définition. Cherche plutôt un énoncé qui contredit le cours.[/reponse]
[reponse motif="Le nombre chromatique d'un graphe est toujours inférieur ou égal à $d_{\max} + 1$."]Non, cette affirmation est vraie : c'est précisément le théorème de majoration du nombre chromatique. L'erreur recherchée se trouve dans une autre proposition.[/reponse]
[reponse motif="Le coefficient $(M^{2})_{i,j}$ donne le nombre de chaînes de longueur $2$ allant de $i$ à $j$."]Non, cette affirmation est vraie : c'est l'application directe du théorème sur les puissances de la matrice d'adjacence, avec $k = 2$.[/reponse]
[reponse statut="incorrect"]Non.
L'énoncé faux est : « Tout graphe connexe admet une chaîne eulérienne. » La connexité est nécessaire mais non suffisante : il faut aussi $0$ ou $2$ sommets de degré impair.[/reponse]
[/qcm]
[/etape]

[etape]
Soit $M$ la matrice d'adjacence d'un graphe non orienté simple à $4$ sommets, dans lequel on lit $\left(M^{3}\right)_{1,2} = 5$. Que représente ce coefficient ?
[qcm]
[option]Le nombre d'arêtes reliant directement le sommet $1$ au sommet $2$.[/option]
[option correct="true"]Le nombre de chaînes de longueur $3$ reliant le sommet $1$ au sommet $2$.[/option]
[option]La distance minimale entre le sommet $1$ et le sommet $2$.[/option]
[option]Le degré commun des sommets $1$ et $2$.[/option]
[reponse statut="correct"]Exactement !
Le coefficient $\left(M^{k}\right)_{i,j}$ donne le nombre de chaînes de longueur $k$ reliant le sommet $i$ au sommet $j$. Ici $k = 3$ : il y a donc $5$ chaînes de longueur $3$ entre les sommets $1$ et $2$.[/reponse]
[reponse motif="Le nombre d'arêtes reliant directement le sommet $1$ au sommet $2$."]Non.
C'est le coefficient $M_{1,2}$ (la matrice elle-même, soit $M^{1}$) qui compte les arêtes directes, c'est-à-dire les chaînes de longueur $1$. Ici la puissance est $3$.[/reponse]
[reponse motif="La distance minimale entre le sommet $1$ et le sommet $2$."]Non.
Les puissances de la matrice d'adjacence comptent des chaînes ; elles ne mesurent pas une distance. La distance minimale relèverait d'un graphe pondéré et de l'algorithme de Dijkstra.[/reponse]
[reponse motif="Le degré commun des sommets $1$ et $2$."]Non.
Le degré d'un sommet se lit sur la somme d'une ligne de $M$, pas sur un coefficient de $M^{3}$. Ce coefficient compte des chaînes de longueur $3$.[/reponse]
[reponse statut="incorrect"]Non.
Le coefficient $\left(M^{k}\right)_{i,j}$ compte les chaînes de longueur $k$ entre $i$ et $j$ : ici, les chaînes de longueur $3$ entre les sommets $1$ et $2$.[/reponse]
[/qcm]
[/etape]

[etape]
Pour une chaîne de Markov de matrice de transition $P$ et de distribution initiale $\pi_0$, par quelle relation obtient-on la distribution $\pi_n$ après $n$ étapes ?
[qcm]
[option]$\pi_n = P^n \times \pi_0$.[/option]
[option correct="true"]$\pi_n = \pi_0 \times P^n$.[/option]
[option]$\pi_n = \pi_0 + n\,P$.[/option]
[option]$\pi_n = \pi_0 \times P \times n$.[/option]
[reponse statut="correct"]Bien vu !
La distribution $\pi_n$ est un vecteur ligne : on multiplie la distribution initiale (à gauche) par la puissance $n$-ième de la matrice de transition, soit $\pi_n = \pi_0 \times P^n$.[/reponse]
[reponse motif="$\pi_n = P^n \times \pi_0$."]Non.
$\pi_0$ est un vecteur ligne : il se place à gauche de $P^n$. L'écriture $P^n \times \pi_0$ n'a pas le bon format de produit matriciel.[/reponse]
[reponse motif="$\pi_n = \pi_0 + n\,P$."]Non.
L'évolution d'une chaîne de Markov est multiplicative (produit par $P$ à chaque étape), pas additive. On n'ajoute jamais la matrice de transition à la distribution.[/reponse]
[reponse motif="$\pi_n = \pi_0 \times P \times n$."]Non.
Passer de $\pi_0$ à $\pi_n$ revient à appliquer $n$ fois la transition, donc à multiplier par $P^n$, et non par $P$ puis par le nombre $n$.[/reponse]
[reponse statut="incorrect"]Non.
On a $\pi_n = \pi_0 \times P^n$ : le vecteur ligne initial multiplié par la puissance $n$-ième de la matrice de transition.[/reponse]
[/qcm]
[/etape]