Chaines de Markov en temps discret

Rappel sur les probabilités

Lorsqu’on est en présence d’un phénomène aléatoire, on remarque que le futur n’est dépendant que du présent.

Soit (Xn) une suite de variables aléatoires à valeurs dans un ensemble fini de J états, Xt=j est l’état du système au temps t. On dit que Xn est une chaîne de Markov de transition si qqsoit n, qqsoit i0, …, in+1 :

P(X(n+1)=i(n+1) | Xn =in,…,X0=i0) = P(X(n+1) = i(n+1) | Xn = in)

Un tel processus est dit sans mémoire. La valeur de cette probabilité est notée pn(n+1).

On remarque que X0 n’est pas fixée par la définition, cette loi est appelée loi initiale. Le vecteur des probabilités initiales est noté PI, avec pij=P(S0=j) avec j compris dans l’ensemble fini et la somme des pij=1.

Le vecteur des probabilités de transition est noté vi (pi0,…,pij) avec j compris dans l’ensemble fini et la somme des pij=1.

La matrice des probabilités de transition est la concaténation des vecteurs de probabilités de transition. Tous les termes sont donc positifs ou nuls, la somme des termes sur une ligne est égale à 1. Les puissances d’une matrice de transition (ou matrice stochastique) sont des matrices stochastiques.

Une chaîne de Markov est dite homogène dans le temps si les probabilités de transition ne sont pas affectées par une translation dans le temps. C’est-à-dire qu’elle ne dépend pas de n. Les probabilités de transition restent stationnaires dans le temps.

Prenons un exemple. Tant qu’un joueur a de l’argent, il joue en misant 1£. Il gagne 1£ avec une probabilité de p et perd sa mise avec une probabilité (1-p) avec p entre 0 et 1. Le jeu s’arrête lorsqu’il a 3£.

Nous pouvons définir quatre états : 0, 1, 2, 3, représentant l’argent qu’il possède. La matrice de transition est la suivante :

markov5

Une chaine de Markov peut posséder une loi initiale qui se présente sous forme d’un vecteur stochastique (la somme est égale à 1). Cette loi représente la répartition à l’origine.

Représentation en graphe et déplacement

Le graphe associé à un processus de Markov est formé des points représentant les états du processus de l’ensemble fini, et d’arcs correspondant aux transitions possible pij.

markovchain

markov4

Notons Q la matrice de transition. Une suite d’états (x1, x2, . . . , xm) définit un chemin de longueur m allant de x1 à xm dans le graphe associé à la chaine de Markov homogène si et seulement si Q(x1, x2)Q(x3, x4) . . .Q(xm-1, xm) > 0.

Lorsque l’on cherche à simuler les premiers états d’une chaine de Markov homogène (Xn) d’espace d’états finis X = {1, . . . ,N} décrite uniquement par sa loi initiale et sa matrice de transition Q on peut utiliser l’algorithme suivant :

 markov1

La probabilité d’être dans un état j à partir d’un état i après n itération revient à multiplier la matrice de transition Qn par le vecteur initial. La réponse est alors Qn(i,j).

Graphes réduits

Un état j est accessible à partir d’un état i sil y a une probabilité strictement positive d’atteindre l’état j à partir de l’état i en un nombre fini de transition. D’un point de vue de la théorie des graphes, j est accessible à partir d’un état i s’il existe un chemin entre i et j.

Si l’état j est accessible à partir de l’état i et que, réciproquement, l’état i est accessible à partir de l’état j, alors on dit que les états i et j communiquent. Cela se traduit par le fait que i et j soient sur un même circuit.

Un graphe réduit est une partition d’une chaîne de Markov en classes d’équivalence telles que tous les états d’une classe communiquent entre eux.

Les classes d’équivalence sont les suivantes :

  • une classe est dite transitoire s’il est possible d’en sortir mais dans ce cas, le processus ne pourra plus jamais y revenir;
  • une classe est dite récurrente ou persistante s’il est impossible de la quitter. Si une classe récurrente est composée d’un seul état, il est dit absorbant.

markov1

Si la partition en classes d’équivalence n’induit qu’une seule classe récurrente, la chaîne de Markov est dite irréductible. Une chaîne de Markov possède au moins une classe récurrente.

Publicités