Correction Question 1
Pour vérifier si une chaîne est réductible, le mieux est de chercher le graphe réduit correspondant à la matrice de transition.
1.1) Utilisation du graphe réduit pour tester la réductibilité de la chaîne de Markov.
Si le graphe réduit ne contient qu'un seul point, alors la matrice est irréductible, ce qui signifie que la chaîne de Markov ne contient qu'une seule classe fermée et pas de classes transitoires.
Si le graphe réduit possède plus d'un point, alors deux cas peuvent se produire :
Dans le graphe réduit, un seul point n'a pas de successeur et dans ce cas la matrice est réductible, mais il existe une ou plusieurs classes transitoires et une seule classe fermée dans lequel vient s'établir un régime permanent au bout d'un temps fini
Dans le graphe réduit, plusieurs points n'ont pas de successeur et dans ce cas, il n'y a pas de régime permanent (on ne sait pas dans quelle classe fermée on atterrit lorsque le temps tend vers l'infini, sauf si l'état initial nous place dans une classe fermée ou dans une classe transitoire qui ne mène qu'à une seule classe fermée).
1.2) Obtention du graphe réduit associé à la chaîne de Markov.
Pour obtenir le graphe réduit d'un graphe donné, il faut rechercher les composantes fortement connexes du graphe qui donnent les points du graphe réduit, puis regarder si dans le graphe initial il existe au moins un arc allant d'une composante connexe à une autre composante connexe pour obtenir les arcs du graphe réduit.
Il y a plusieurs façons d'obtenir les composantes fortement connexes d'un graphe.
Par exemple, on choisit un point au hasard pour la composante connexe n°1, on marque ce point avec un signe + et un signe -, puis on marque avec + ses successeurs, les successeurs des successeurs (= des points marqués +) ..., puis on marque avec - ses prédécesseurs, les prédécesseurs des prédécesseurs (= les points marqués -) ... on met dans la composante n° 1 tous les points marqués + et -, puis on efface les marquages et on ôte du graphe tous les points qui sont dans la composante n° 1 et on recommence de même pour la composante n° 2 ...
Une autre méthode consiste à rechercher la fermeture transitive stricte T du graphe, en faisant le "ou logique" de la matrice booléenne B d'existence des arcs avec B2, B3, ... , Bn, ou mieux, pour ne pas élever la matrice B à la puissance n, en posant T:=B, puis en répétant T:=T x B "ou logique" B jusqu'à ce que la nouvelle version de T soit identique à l'ancienne.
Puis on construit à partir d'un point quelconque x1 la composante n°1 en prenant tous les points y tels que T(x1,y)=T(y,x1)="vrai". On fait de même à partir d'un point x2 n'appartenant pas à la première composante ...
