Loi invariante et comportement asymptotique

Nous cherchons à comprendre la comportement asymptotique d’une chaine de Markov homogène. C’est à dire la limite des probabilités de transition Qn(i,j) quand n devient très grand.

Idée

Nous cherchons à répondre à la question suivante : « Quelle est la probabilité qu’après n
pas, la chaîne de Markov soit dans un état donné ? ». Prenons la matrice de transition P suivante :

proba9.png

Supposons qu’aucune des machines n’est en panne le premier jour. Alors nous avons comme vecteur initial (1, 0), pour calculer la répartition suivante nous multiplions le vecteur initial par P, etc. Ce qui donne les résultats suivant :

proba10

Cela signifie qu’après 10 itération, si on considère que nous partons de l’état 0, nous avons 99% d’être dans l’état 0 et 1% dans l’état 1. Cela peut aussi s’interprété de la façon suivante : sur une population de départ, en considérant la répartition initiale par le vecteur (1,0), alors 99% de la population sera dans l’état 0 et 1% dans l’état 1.

Nous remarquons que la quatrième et la dixième itération ont des résultats proches (ici identique à 4 chiffres significatifs). On parle alors de loi de convergence, et cette loi ne dépend pas de la répartition à l’origine.

 

Périodicité

Prenons l’exemple de la matrice suivante P={0, 1; 1, 0}. Nous constatons que P²=Id ce qui implique la relation suivante : ∀n∈Ν, P2n+1=P.

Une telle chaine ne converge pas, on dit qu’elle est 2-périodique ou de période 2.

Une chaine est dite k-périodique ssi : ∀(n,k)∈Ν², Pkn+1=P. Les états d’une classe ont tous la même période.
Un état x est dit apériodique si Pn(x,x)>0. Si P est irréductible et possède au moins un état apériodique, alors tous les états sont apériodique.

Avant de calculer la loi invariante d’une chaîne de Markov, il faut vérifier que cette dernière soit irréductible et apériodique (aussi dit ergodique).

Une chaîne est donc ergodique si tout état est atteignable depuis tout autre état et pour une puissance Pk tous les éléments sont strictement positifs. Il est donc possible d’aller d’un état à un autre en au plus k étapes, indépendamment des points de départ et d’arrivée. Une chaîne ergodique possède une loi invariante (attention, il est aussi possible de calculer la distribution stationnaire des autres chaines, l’interprétation n’est alors pas la même).

 

Loi invariante

Une dit qu’une mesure de probabilité π est invariante ou stationnaire si pour une matrice de transition P nous avons πP=π. Notons que puisque π est une mesure alors la somme de ces termes est égale à 1.

Soit (Xn) définissant une chaine de Markov homogène avec P une matrice de transition irréductible et apériodique possédant une mesure invariante π. Alors :

  • P(Xn = x) → π(x) quand n → ∞ pour tout x
  • pn(x, y) → π(y) quand n → ∞ pour tous x, y

La vitesse de convergence vers la loi stationnaire est de l’ordre de |ζ|n où ζ est la valeur propre de P différente de 1 et de plus grand module (qui est strictement plus petit que 1).

Si la chaine est ergodique (irréductible et apériodique) alors tous les états sont atteignable depuis tout autre état. Une telle chaine possède une loi invariante.

Calcul exacte de la mesure

Prenons la définition µP=µ sachant que µ est stochastique (et oui j’ai changé le nom de la distribution initiale !). Cela donne le système linéaire suivant :

Une mesure µ sur E est invariante (pour P) si µ = µP, c’est-à-dire : pour tout y ∈ Emarkov1

On parle de loi invariante si de plus µ est une probabilité (µ(E) = 1). On dit aussi loi/probabilité invariante/stationnaire.

 

Vu la relation µn+1 = µnP, on constate de suite que, si µ est une loi invariante et X0 ∼ µ, alors Xn ∼ µ pour tout n. On remarque aussi que µ ne dépend pas du vecteur de distribution initial.

Prenons par exemple une chaîne de Markov à trois états, dont la la matrice de transition est la suivante :

proba11

Nous remarquons tout de suite que la matrice forme une chaîne irréductible et apériodique, puisque tous les états communique et que pii >0. Nous cherchons à résoudre le système  µP=µ avec pour solution  µ*= (p, q, r) tel que p+q+r=1 et 0<p,q,r <1 ce qui donne les équations suivantes :

proba12

On trouve comme solution le vecteur µ*=(2/53, 10/53, 41/53).

 

Calcul exacte de la mesure (cas non ergodique)

Prenons la chaîne de Markov suivante

proba13

Nous constatons que l’état 1 forme une classe transitoire, l’état 2 forme une classe absorbante et les états 3, 4 forment une classe récurrente. Faisons l’analyse du comportement asymptotique en ne tenant pas compte de son caractère non ergotique (pas de garanti de convergence).

Résolvons le système suivant :

proba14

Le système n’admet pas de solution unique. Posons α entre 0 et 1, alors nous trouvons une solution en admettant que α est solution de π2 :

proba15

Nous remarquons dans la classe {3,4} que les probabilités sont égales sur une fréquence de 2k, nous en déduisons que la classe et périodique sur une période de 2 (que nous aurions pu calculer par puissance de la matrice). La classe {2} est absorbante, il n’y a pas de période. La classe {1} est transitoire, c’est pourquoi il n’y a plus de population après un temps k.

Dans le cas d’une chaîne non périodique, il est possible de déduire du comportement asymptotique les classes des états ainsi que les périodicités des classes et de la chaîne.

 

Publicités