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.

Exemple de modélisation

On s’intéresse au développement d’une forêt naturelle en région tempérée sur une parcelle. Notre modèle comporte 3 états. L’état 1 est celui d’une végétation constituée d’herbes ou d’autres espèces au faible bilan carbone; l’état 2 correspond à la présence d’arbustes dont le développement rapide nécessite un ensoleillement maximal et dont le rendement carbone sera maximale, et l’état 3 celui d’arbres plus gros qui peuvent se développer dans un environnement semi ensoleillé (considéré comme une forêt). Si l’on note respectivement h, a, f ces trois états (pour herbe, arbustes, forêt), l’ensemble des états possibles pour un point donné de cette parcelle est l’ensemble s={h, a, f}. Sur la parcelle on repère au sol un grand nombre de points répartis sur un maillage régulier et on enregistre à intervalle de temps fixé l’état de la végétation en chacun de ces points. Ce type de programme s’appelle un automate cellulaire.

En observant l’évolution durant un intervalle de temps, on peut déterminer pour chaque état i∈S la proportion de points qui sont passées à l’état j∈S, et noter pij cette proportion. Si les différentes proportions ainsi relevées (il y en a 9) évoluent peu d’un intervalle de temps au suivant, on peut les supposées inchangées au cours du temps et on peut regarder comme les probabilités pour un point quelconque de passer de l’état i à l’état j pendant un intervalle de temps. Supposons par exemple que dans cette parcelle, ces probabilités soient les suivantes :

proba31

Si X0 désigne l’état d’un point à l’instant t=0 et X1 l’état du même point en t=1, on a par exemple la probabilité de passage de l’état arbuste en t=0 à l’état forêt en t=1 s’écrit P(X1=f : X0=a) est vaut 0, 4.

L’ensemble des états S et la matrice de transition P constituent un exemple de chaine de Markov. On peut aussi représenter cette chaine de Markov par le graphe suivant :

proba32

Dans ce modèle, on peut ainsi calculer la probabilité de n’importe quelle succession d’états, appelée trajectoire de la chaine de Markov. Par exemple la probabilité, qu’en un point de la parcelle, on observe la succession d’états (h, h, a, f, f) se calcule de la façon suivante :

proba33

où π0 est la probabilité d’être dans l’état à l’instant initial t=0.

L’observation de l’état dans lequel se trouve les différents points de la parcelle à l’instant initial t0 permet de déterminer les proportions initiales de chacun des 3 états. Pour cela, on relève pour chaque point l’état dans lequel il se trouve et on calcule la proportion de points de chacun des états possibles. On peut voir chaque proportion comme la probabilité pour un point de la parcelle d’être dans l’un des états à l’instant initial. Ainsi, si l’on a par exemple π0 =(0.5, 0.25, 0.25), cela signifie que la moitié des points de la parcelle sont au départ dans l’état h, un quart dans l’état a et un quart dans l’état f. Mais on peut aussi interpréter cela en considérant qu’un état quelconque a 50% de chance d’être dans l’état h, 25% d’être dans l’état a et 25% dans l’état f. C’est pour cela que proportion d’individus de la population étudiée se trouvant dans chacun des états,

proba34

s’appelle la loi de probabilité initiale ou encore la distribution initiale. Lorsqu’on choisit une modélisation par une chaine de Markov, l’objectif est souvent de déterminer l’évolution de la répartition des états au cours du temps. Par exemple, si la parcelle considérée ci-dessus est recouverte pour un tiers de forêt à l’instant initial, cette proportion va-t-elle grandir, tendre vers 100%, au contraire tendre vers zéro ou bien s’approcher d’une valeur limite sorte d’équilibre écologique ?

Nous allons voir que si l’on connait la distribution initiale on peut calculer la distribution à l’instant t=1, puis à l’instant t=2 et ainsi de suite. Calculons pour t=1 :

proba35

On en déduit que π1(h) est le produit scalaire du vecteur  π0  avec la première colonne de la matrice P. De même, on vérifie que π1(a) est le produit scalaire du vecteur avec la deuxième colonne de la matrice P et que π1(f) est le produit scalaire du vecteur avec la troisième colonne de la matrice P. On résume cela : π10P.

proba36

 

 

Publicités