Correction Question 2
Pour tester si une chaîne est périodique,
on teste tout d'abord qu'il n'existe pas de boucles, car la seule présence de boucles interdit à la chaîne d'être périodique,
si on a d'abord recherché si la chaîne était réductible et que la réponse était oui, alors la chaîne ne peut pas être périodique. Si l'une de ces classes fermées était périodique, alors le comportement pourrait devenir périodique à l'infini, mais il n'est pas prédictible, sauf si on sait qu'à l'instant initial on est déjà dans l'un des états de cette classe fermée périodique.
Ensuite, après avoir éliminé ces cas, on peut analyser la longueur des circuits élémentaires,
d'où un algorithme de recherche de tous les circuits d'un graphe :
à chaque itération de l'algorithme, on construit les circuits qui partent du point n°i et qui ne passent que par des points de n° strictement plus grand que i, on met i sur une pile, on empile le premier successeur de i de valeur > i, puis le premier successeur du sommet de la pile > i, ... si i est successeur du sommet de la pile, alors le contenu de la pile est un circuit passant par i et la hauteur de la pile donne la longueur du circuit, si un point n'a pas de successeur empilable, alors on le dépile, mais en gardant son numéro et on ne peut empiler immédiatement à sa place qu'un autre successeur du point précédent de plus grande valeur, on arrête l'itération pour i lorsque la pile se vide.
Puis on examine les circuits obtenus pour voir s'ils ont un PGCD différent de 1. En fait, on peut arrêter la recherche précédente de circuits du graphe, dès l'instant où le PGCD de la longueur des circuits obtenus est égal à 1 et dans ce cas, la chaîne de Markov n'était pas périodique.
Si le PGCD de la longueur de tous les circuits n'est pas égal à 1. Alors on utilise un algorithme par marquage pour vérifier avec la valeur du PGCD si la chaîne est périodique :
on marque un point 0, ses successeurs 1, les successeurs des successeurs 2 ... (modulo le PGCD) et chaque fois que l'on rencontre un point marqué, il doit déjà avoir la marque que l'on veut lui donner, on arrête quand tous les points sont marqués sans contradiction de marques, on peut alors affirmer que la chaîne est périodique et on connaît sa périodicité, c'est la valeur du PGCD.
