Graphes, matrices et chaînes de Markov

Dans une ville, on observe chaque jour le temps : Soleil (S) ou Pluie (P). Si un jour est ensoleillé, le lendemain l'est aussi avec la probabilité 0,8. S'il pleut, le lendemain est ensoleillé avec la probabilité 0,6. Le jour 0 est ensoleillé. On note sₙ la probabilité que le jour n soit ensoleillé.
a) Écrire la matrice de transition M (ordre S, P).
b) Montrer que sₙ₊₁ = 0,6 + 0,2 sₙ.
c) Déterminer la limite éventuelle ℓ de (sₙ).
d) Exprimer sₙ en fonction de n, puis retrouver la limite.
e) Interpréter le résultat.

Une agence de location possède 3 points de retrait 1, 2, 3. Les voitures circulent selon la matrice de transition
M =
( 0,5 0,3 0,2 )
( 0,1 0,7 0,2 )
( 0,2 0,2 0,6 )
a) Vérifier que M est une matrice de transition.
b) Déterminer l'état stable P = ( x y z ) (avec x + y + z = 1).
c) Interpréter : à long terme, quelle est la répartition des voitures ?

On reprend le triangle à 3 sommets 1, 2, 3 (tous reliés), de matrice d'adjacence M. Pour un entier n ≥ 0, on note uₙ = (Mⁿ)₁₁ (nombre de chemins de longueur n de 1 à 1) et vₙ = (Mⁿ)₁₂ (de 1 à 2). Par symétrie, tous les coefficients diagonaux de Mⁿ valent uₙ et tous les autres valent vₙ.
a) Justifier que uₙ₊₁ = 2 vₙ et vₙ₊₁ = uₙ + vₙ.
b) Sachant u₀ = 1 et v₀ = 0, calculer uₙ et vₙ pour n allant de 1 à 5.
c) Montrer que, pour tout n, uₙ + 2 vₙ = 2ⁿ, et interpréter ce nombre.

On modélise un mini-web de 3 pages 1, 2, 3 par un graphe orienté : la page 1 pointe vers 2 et 3 ; la page 2 pointe vers 3 ; la page 3 pointe vers 1. Un internaute clique au hasard, de façon équiprobable, sur l'un des liens sortants de la page où il se trouve.
a) Écrire la matrice de transition M.
b) Déterminer la distribution stable P = ( x y z ), qui donne le « classement » des pages.
c) Quelles pages arrivent en tête ?

a) Peut-il exister un graphe d'ordre 5 dont tous les sommets sont de degré 3 ? Justifier.
b) Peut-il exister un graphe d'ordre 6 dont tous les sommets sont de degré 3 ? Si oui, combien a-t-il d'arêtes ?
c) Démontrer que, dans tout graphe, le nombre de sommets de degré impair est pair.

Un système passe entre trois états 1, 2, 3 selon la matrice de transition
M =
( 0,6 0,3 0,1 )
( 0,2 0,5 0,3 )
( 0,1 0,4 0,5 )
a) Calculer le coefficient (M²)₁₃ et interpréter ce nombre.
b) On part de l'état probabiliste P₀ = ( 0,5 0,5 0 ). Calculer P₁.
c) En déduire P₂ = P₁ × M.

Une puce se déplace le long d'une rangée de 4 cases 1−2−3−4 (chaque case est reliée à ses voisines immédiates). À chaque étape, elle passe sur une case voisine choisie au hasard, de façon équiprobable.
a) Écrire la matrice de transition M.
b) Déterminer l'état stable P = ( a b c d ) en résolvant P = P × M avec a + b + c + d = 1.
c) Vérifier que cette distribution est proportionnelle au degré de chaque case dans le graphe.

On considère le carré (cycle à 4 sommets) 1, 2, 3, 4 dont les arêtes sont 1−2, 2−3, 3−4, 4−1, de matrice d'adjacence M.
a) Écrire M puis calculer M².
b) Combien y a-t-il de chaînes de longueur 2 entre 1 et 3 ?
c) Calculer M⁴ (en utilisant M⁴ = (M²)²), puis donner le nombre de chaînes de longueur 4 de 1 à 3.
d) Justifier que le nombre de chaînes de longueur impaire entre 1 et 2 peut être non nul, tandis que celui entre 1 et 3 est toujours nul.

On étudie une chaîne de Markov générale à deux états A et B : on passe de A à B avec la probabilité a et de B à A avec la probabilité b, où 0 < a < 1 et 0 < b < 1. On note aₙ la probabilité d'être en A à l'étape n.
a) Écrire la matrice de transition M (ordre A, B).
b) Montrer que l'état stable est P = ( $\frac{b}{(a+b)}$ $\frac{a}{(a+b)}$ ).
c) Établir que aₙ₊₁ = b + (1 − a − b) aₙ, puis montrer que (aₙ) converge et donner sa limite.

Une machine peut être « en marche » (état A) ou « en panne » (état B). Chaque jour : si elle marche, elle tombe en panne avec la probabilité 0,1 ; si elle est en panne, elle est réparée (et remarche) avec la probabilité 0,4. Au jour 0 elle marche. On note aₙ la probabilité qu'elle marche le jour n.
a) Écrire la matrice de transition M.
b) Montrer que aₙ₊₁ = 0,4 + 0,5 aₙ.
c) Démontrer par récurrence que aₙ = 0,8 + 0,2 × 0,5ⁿ pour tout n ≥ 0.
d) Donner la limite de (aₙ) et l'interpréter.
e) Déterminer le plus petit entier n tel que aₙ ≤ 0,81.