Cette page regroupe de nombreux exercices corrigés sur les chaines de Markov en temps discret et comportement asymptotique, classe, chaine ergodique, absorption.
Exercice 1
Construire la chaîne de Markov correspondant à la matrice stochastique suivante :
0.4 | 0.6 | 0 |
0.2 | 0.5 | 0.3 |
0 | 0.4 | 0.6 |
Combien la chaîne a-t-elle de classe ? Est-elle réductible ? Si oui la réduire. Calculer la probabilité stationnaire, si elle existe, de la chaîne irréductible. Calculer la périodicité des classes.
Pour représenter la chaîne, on choisit de numéroter les états de 1 à 3, dans l’ordre des lignes de la matrice de transition :
Pour vérifier les classes de la chaîne, nous devons vérifie les états qui communiquent. Ici, 1 communique avec 2 et 2 avec 3 (donc accessibles dans les deux sens), par transitivité 1 communique avec 3. La chaîne ne possède qu’une seule classe, elle est irréductible. Les états sont donc tous récurrents, et sont apériodique car ils possèdent tous une boucle sur eux-mêmes. Dans ces conditions, la chaîne admet une unique probabilité stationnaire. Il suffit de résoudre le système d’équation suivant :
Ce qui donne le vecteur (4/25, 12/25, 9/25).
Exercice 2
De même que l’exercice 1 avec la matrice stochastique suivante :
0 | 0.5 | 0.5 | 0 |
0 | 1 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
On constate que 2 ne communique avec personne, c’est un état absorbant. Personne ne communique avec 1, l’état forme une classe transitoire. Les états 3 et 4 communiquent entre eux, ils forment une classe récurrente. Il y a donc trois classes {1}, {2}, {3,4}.
Il n’y a pas de garanti de probabilité stationnaire. Résolvons le système suivant :
Le système n’admet pas de solution unique. Posons Pi2 entre 0 et 1, alors nous trouvons une solution :
Nous remarquons dans la classe {3,4} que les probabilités sont égales sur une fréquence de 2k, nous en déduisons que la classe et périodique sur une période de 2. La classe {2} est absorbante, il n’y a pas de période. La classe {1} est transitoire, c’est pourquoi il n’y a plus de population après un temps k.
Exercice 3
De même que l’exercice 1 avec la matrice stochastique suivante :
0 | 1 | 0 |
0 | 0 | 1 |
1 | 0 | 0 |
Passons maintenant à la probabilité stationnaire :
Ce qui donne le vecteur (1/3, 1/3, 1/3). Pour ce qui est de la périodicité, on remarque que la matrice de transition devient la matrice identité quand elle est au cube. Nous pouvons donc en déduire que la chaîne de Markov est périodique de périodicité 3. La probabilité stationnaire n’existe donc pas, par contre nous pouvons en conclure que sur un pas aléatoire grand, nous passons 1/3 du temps dans chacun des états.
Exercice 4
A partir des trois graphes de transition suivants, reconstituez les chaines de Markov associées (espace d’états et matrice). Puis faites l’analyse de ces chaines de Markov : les classes et caractéristiques, loi stationnaire, probabilité d’absorption, temps moyens d’absorption).
PREMIER GRAPHE :
Tous les états communiquent, il y a donc une seule classe forcément récurrente. On remarque que la matrice puissance 4 donne la matrice identité, la périodicité est donc de 4.
Calculons maintenant la répartition stationnaire :
Comme il y a périodicité, nous savons qu’il n’y a pas de convergence. Par ailleurs, un pas aléatoire passera ¼ de son temps dans chaque état. Pour ce qui est de l’absorption, nous avons une chaine irréductible, donc la probabilité d’être dans l’unique classe est de 1.
DEUXIEME GRAPHE :
Tous les états communiquent, les états sont tous de même période. La matrice semble similaire au premier graphe, mais notons que l’état 1 possède une boucle, donc de période 1. L’unique classe est donc apériodique (de période 1).
Comme la chaine est apériodique et irréductible, nous savons qu’elle converge vers la distribution stationnaire.
Comme il existe une seule classe, le calcul des probabilités d’absorption est simple, de n’importe quel état, nous allons toujours dans la même classe.
TROISIEME GRAPHE :
Nous avons quatre classes
{1} qui est transitoire donc pas de périodicité.
[2} qui est récurrente avec boucle donc une périodicité de 1.
{3} idem que {1}
{4} idem que {2}
Calculons la distribution stationnaire. Compte tenu qu’il y a des classes transitoires, nous savons qu’il n’y aura pas de convergence :
Notons qu’il y a une infinité de solution.
Calculons les probabilités d’absorption. Commençons par l’état 2. Calculons le vecteur v tel que vi soit égale à la probabilité que la chaîne soit absorbée en 2 sachant qu’il démarre à i. Les calculs sont simples puisque nous avons deux classes transitoires d’espérance 1 (sans boucle et à état unique).
Nous savons donc que l’état 2 est atteint avec un pas de 1 maximum, cela réduit considérablement le nombre de calcul. En effet, la probabilité d’atteindre 2 partant de 1 est connu puisque c’est p12. Les probabilité de transition sont donc la deuxième colonne de P. De même les probabilités d’absorption de l’état 4 est la quatrième colonne de P. Dans le cas général, il faut calculer le vecteur v tel que (P-I)v=0.
Nous pouvons calculer le temps moyen d’absorption. Les états 2 et 4 sont récurrents donc x2=x4=0. Il est rapide de voir que x1=x3=1+0=1.
Exercice 5
Prenons l’exemple suivant :
Calculer la probabilité des trajectoires suivantes (h, a, f, h), (h, a, f, a), (a, a, a).
Calculer la distribution des états X1 à l’instant t = 1 si l’on suppose X0 = (1, 0, 0).
Interpréter.
Montrer qu’une distribution uniforme X0 = (1/3, 1/3, 1/3) n’est pas une distribution stationnaire pour cette chaîne de Markov.
Y-a-t-il une distribution stationnaire pour cette chaîne de Markov ?
P(h,a,f,h)= X0(h)*0.45*0.4*0=0
P(h,a,f,a)=0.018*X0(h)
P(a,a,a)= 0.25*X0(a)
Il y a donc, après trois itérations, la moitié de la parcelle recouverte d’herbe, .45 arbustes et .05 de foret en supposant qu’au début il n’y ait que de l’herbe.
La distribution uniforme n’est pas stationnaire. Pour calculer la distribution stationnaire il faut résoudre le système XP=X :
Ce qui donne pour solution (2/53, 10/53, 41/53). On peut en conclure qu’on tend vers une majorité de foret, d’une densité de 41/53.
Exercice 6
On considère une chaine de Markov de quatre états suivant la matrice de transition suivante :
Déterminer les classes de la chaine puis la probabilité d’absorption de l’état 4 en partant de 2.
Déterminer le temps d’absorption dans 1 ou 4 en partant de 2.
Nous remarquons que l’état 1 et l’état 4 sont tous deux des états absorbant, formant deux classes. Les états 2 et 3 communiquent mais peuvent aller dans une classe absorbante. On en déduit que {2,3} forme une classe transiente.
D’après le cours, la probabilité d’absorption d’un état absorbant k à partir d’un état i se résout par le système suivant :
Cela donne le système suivant :
Et donc le vecteur solution (0 ;1/3 ;2/3 ;1), h1=0 afin de ne pas influencer les autres équations. On en déduit par h2 la probabilité d’absorption de l’état 4 en partant de 2.
D’après le cours, le temps d’absorption par un état absorbant k à partir d’un état i se résout par le système suivant :
Cela donne le système suivant :
Et donc le vecteur solution est (0 ;2 ;2 ;0). Le temps d’absorption K2 donne la bonne réponse.
Exercice 7
On considère un réseau routier composé de 5 villes A, B, C, D, S suivant :
Pour modéliser le trafic routier, nous considérons que les voitures empruntent une route sortant de lors ville de façon équitable (uniforme). Notons Xn la variable aléatoire représentant la ville atteinte par une voiture au temps n.
- Justifier que le processus probabiliste est bien stochastique et forme une chaine de Markov. Et donner la matrice de transition.
- Quelle est la probabilité que, partant de B, la voiture soit en C après deux itérations.
- Classer les états en classes et calculer leurs périodes.
- Ecrire le système d’équations vérifié par les probabilités stationnaires.
- On note le nombre de routes issues de i. En déduire une répartition d’une population initiale en fonction de . Calculer la distribution stationnaire. Est-elle unique ?
- On observe une voiture pendant un temps N supposé très grand. Combien de temps approximativement a-t-elle passé dans un état donné ?
- Partant de S, quel est le nombre moyen d’étapes nécessaires à la voiture pour revenir en S ?
- Quelle est la probabilité que, partant de S, la voiture visite la ville D avant la ville C ?
- Même en connaissant toute sa trajectoire passée, la destination de la voiture n’est décidée qu’à partir de sa position actuelle. De plus, d’après la définition de l’exercice, la voiture a une probabilité de 1 de quitter sa ville actuelle, donc d’effectuer un pas vers les villes connectées. Le choix du pas est indépendant du passé, nous sommes bien en présence d’une chaine de Markov. La matrice de transition est la suivante :
- Il n’y a que deux chemins qui va de B en C en deux pas : BAC et BSC. La probabilité d’aller de B en C en deux pas est donc égale à ½ * 1/3 +1/2 * ¼ = 7/24.
- Comme le montre le graphe, tous les états sont liés entre eux, ils communiquent tous et ne forme donc qu’une unique classe récurrente (donc positif). La chaîne est irréductible. Pour ce qui est de la périodicité, notons qu’il existe des chaines de toutes les longueurs de A vers A. La chaine est donc apériodique.
- Voir le cours.
- On remarque que le vecteur de répartition calculer par le nombre de sorties de chaque ville correspond au vecteur des probabilités stationnaires (1/4, 1/6, 1/6, 1/12, 1/3). Cette probabilité est unique puisque la chaine est ergodique.
- Comme la chaine est ergodique, nous savons que son comportement asymptotique est équivalent aux probabilités stationnaires. Par exemple, la voiture passera 1/12 de son temps dans l’état D.
- Encore une fois, la chaine est ergodique, nous savons que l’espérance est l’inverse de la probabilité stationnaire. Le temps moyen pour revenir en S est donc de 3 pas.
- Ce point est beaucoup plus complexe a déduire. L’idée est de faire en sorte que la chaine de Markov soit absorbante en C ou D. La probabilité partant de S, d’atteindre D est donc la probabilité d’être absorbé par la classe {D}. Dans un premier temps, on modifie les états C et D comme suit :
Nous avons alors deux classes récurrentes (et absorbantes) et une classe de transition contenant {A,B,S}. Il ne reste plus qu’à calculer les probabilités d’absorption et à conclure (voir le cours).
Exercice 8
On considère une chaine de Markov a trois états de matrice de transition suivante :
Quels sont les états récurrents, transients, le régime stationnaire ? Calculer le temps d’atteinte de chaque état. Calculer la période de chaque état. En déduire sur la distribution stationnaire.
A partir de l’état 1 nous pouvons aller à l’état 2 et 3, à partir de l’état 2 nous pouvons aller à l’état 1 et 3, à partir de l’état 3 nous pouvons aller en 1 et par transitivité de 1 vers 2 on en déduit que 3 peut aller à 2. Tous les états communiquent donc la chaine est irréductible, tous les états sont récurrents positifs.
La chaine admet donc une unique loi stationnaire de valeur (4/9 ; 2/9 ; 3/9)
Le temps d’atteinte dans un état est l’inverse des valeurs de la loi stationnaire.
Lorsque l’on calcule Q² et Q3, on remarque que la valeur en indice (1,1) est positive, donc il n’y a pas de période. Il n’est pas utile de vérifier toute la diagonale car nous avons montré que tous les états font partis de la même classe.
La chaine est ergodique, son caractère asymptotique tend vers la distribution stationnaire.
Exercice 9
Pour représenter le passage d’une molécule de phosphore dans un écosystème, nous considérerons quatre états possibles :
- la molécule est dans le sol,
- la molécule est dans l’herbe,
- la molécule a été absorbée par du bétail,
- la molécule est sortie de l’écosystème.
La matrice de transition est la suivante :
Représenter la chaîne de Markov associée. Etudiez la chaîne de Markov.
Pi=(0, 0, 0, 1) à cause de l’état absorbant. Il est possible de calculer N et B par :
