Chaînes de Markov

Dans ce cours, nous parlerons surtout de la théorie autour des chaînes de Markov d’ordre 1 : relation de dépendance simple entre variables aléatoires et à temps discret.

Compléments de cours sur les processus de Markov :

  • études sur les probabilités de transition

Généralité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

Liens avec la théorie des graphes

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

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.

Graphes réduits

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. Les états 4, 5, 6 sont des états terminaux, ils forment toujours une classe récurrente ou absorbant.

Publicités