Chaines de Markov en temps discret
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. C’est dans cette condition que l’on peut modélisation les chaines de Markov en temps discret.
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é π, avec πj=P(S0=j) avec j compris dans l’ensemble fini et la somme des πj=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.
Chaines de Markov en temps discret homogènes
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 :
Les chaines de Markov en temps discret peuvent 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 des chaines de Markov en temps discret
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 des chaines de Markov en temps discret homogènes (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 :
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 des chaines de Markov en temps discret
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.
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.
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 sur les chaines de Markov en temps discret
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 :
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 :
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 :
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,
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 :
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 : π1=π0P.
FR 
EN 
ES