Aller au contenu

Probabilité stationnaire d'une chaîne de Markov

Un article de Wikipédia, l'encyclopédie libre.

La probabilité stationnaire d'une chaîne de Markov s'interprète usuellement comme la fraction du temps passé en chaque état de l'espace d'états de cette chaîne de Markov, asymptotiquement. En effet, une version de la loi forte des grands nombres pour les chaînes de Markov stipule que :

presque sûrement, sous certaines hypothèses détaillées plus bas. La variable aléatoire s'interprète comme le temps passé en lors des premiers pas de la chaîne de Markov La fraction est donc la fraction de temps passé en l'état pendant les premiers pas de la chaîne de Markov. La convergence de cette fraction lorsque tend vers l'infini n'est pas un résultat anodin. On trouvera une discussion plus poussée sur le temps de séjour sur la page Récurrence et transience d'une chaîne de Markov.

Définition

[modifier | modifier le code]

Définition — 

  • Une mesure sur l'espace d'états d'une chaîne de Markov de matrice de transition est dite stationnaire si
ou, de manière équivalente,
Une mesure stationnaire est une fonction propre de la transposée de la matrice de transition, associée à la valeur propre 1.
  • Une mesure stationnaire est appelée probabilité stationnaire ou loi stationnaire si elle remplit la condition supplémentaire :
Remarques :
  • Comme toute mesure discrète, les mesures et vérifient, implicitement,
  • La chaîne de Markov est un processus stationnaire, i.e., pour tout a même loi de probabilité que si et seulement si la loi initiale de (la loi de ) est une probabilité stationnaire.
  • Cela entraîne en particulier que si la loi initiale de la chaîne de Markov est une probabilité stationnaire, alors la loi de est cette même probabilité stationnaire, indépendamment de
  • L'ensemble des probabilités stationnaires est convexe.

Existence et unicité : cas irréductible

[modifier | modifier le code]

L'existence d'une probabilité stationnaire pour une chaîne de Markov irréductible est liée aux propriétés du temps de retour en et en particulier aux propriétés de récurrence de l'état

Définition — 

  • Le temps de premier retour en noté est une variable aléatoire à valeurs dans définie par
  • L'état est récurrent positif si l'espérance du temps de premier retour en cet état, partant de cet état, est finie, i.e. si

Rappelons que lorsqu'on étudie une chaîne de Markov particulière, sa matrice de transition est en général bien définie et fixée tout au long de l'étude, mais la loi initiale peut changer lors de l'étude et les notations doivent refléter la loi initiale considérée sur le moment : si à un moment de l'étude on considère une chaîne de Markov de loi initiale définie par alors les probabilités sont notées et les espérances sont notées En particulier, si on dit que la chaîne de Markov part de les probabilités sont notées et les espérances sont notées Ci-dessus, dans la notation l'indice signifie qu'on calcule l'espérance pour la chaîne de Markov partant de i.e. de loi initiale définie par Ainsi s'interprète comme l'intervalle de temps "typique" entre deux passages consécutifs à l'état

Théorème — Si une chaîne de Markov est irréductible, alors il existe au plus une probabilité stationnaire. On a alors équivalence entre les 3 propositions :

  • il existe une probabilité stationnaire,
  • il existe un état récurrent positif,
  • tous les états sont récurrents positifs.

Supposons qu'une des 3 conditions ci-dessus est remplie et notons l'unique probabilité stationnaire : alors

Théorème — Une chaîne de Markov irréductible à espace d'états fini est récurrente positive (i.e. tous ses états sont récurrents positifs). Elle possède donc exactement une probabilité stationnaire.

La relation entre existence et unicité des probabilités stationnaires, classifications des états de la chaîne de Markov et récurrence positive est traité dans un cadre complètement général à la section Existence et unicité. Cependant les théorèmes ci-dessus, valables uniquement pour les chaînes de Markov irréductibles, sont suffisants dans un grand nombre d'exemples.

Loi forte des grands nombres

[modifier | modifier le code]
Graphe de la marche réfléchie en 0
Distribution empirique (rouge) et distribution stationnaire (bleue) pour la marche réfléchie en 0, départ à la moyenne stationnaire -1+1/ρ=2 : p=0.4, q=0.6, ρ=1/3, 2 000 pas
Distribution empirique (rouge) : départ à la moyenne stationnaire -1+1/ρ=12, p=0.48, q=0.52, ρ=1/13, 2 000 pas
Distribution empirique (rouge) : départ à la moyenne stationnaire -1+1/ρ=12, p=0.48, q=0.52, ρ=1/13, 5 000 pas
Distribution empirique (rouge) : départ à la moyenne stationnaire -1+1/ρ=12, p=0.48, q=0.52, ρ=1/13, 20 000 pas

Dans le cas d'une chaîne de Markov irréductible et récurrente positive, la loi forte des grands nombres est en vigueur : la moyenne d'une fonction sur les instances de la chaîne de Markov est égale à sa moyenne selon sa probabilité stationnaire. Plus précisément, sous l'hypothèse

on a presque sûrement :

La moyenne de la valeur des instances est donc, sur le long terme, égale à l'espérance de la probabilité stationnaire. En particulier, cette équivalence sur les moyennes s'applique si est la fonction indicatrice d'un sous-ensemble de l'espace des états :

Cela permet d'approcher la probabilité stationnaire par un histogramme (la distribution empirique) construit à partir d'une séquence particulière.

Ergodicité

[modifier | modifier le code]

En particulier, si le processus est construit en prenant la probabilité stationnaire comme loi initiale, le shift défini par

préserve la mesure, ce qui fait de la chaîne de Markov un système dynamique. La loi forte des grands nombres entraine alors que la chaîne de Markov est un système dynamique ergodique. L'ergodicité est à la fois plus forte que la loi forte des grands nombres car on peut en déduire, par exemple, que a pour limite presque sûre mais elle est aussi plus faible car elle réclame en principe la stationnarité de la chaîne de Markov, ce qui n'est pas le cas de la loi forte des grands nombres.

Convergence vers la loi stationnaire

[modifier | modifier le code]

Convergence de la loi marginale

[modifier | modifier le code]

Si la chaîne de Markov est irréductible, récurrente positive et apériodique, alors converge vers une matrice dont chaque ligne est l'unique distribution stationnaire En particulier, la loi de converge vers indépendamment de la loi initiale Dans le cas d'un espace d'état fini, cela se prouve par le théorème de Perron-Frobenius.

Typiquement, par exemple dans le cas d'une chaîne de Markov à espace d'états fini irréductible et apériodique, la convergence est exponentiellement rapide, i.e. pour une norme quelconque, on peut trouver et tels que

On trouve plus loin dans l'article une démonstration de cette décroissance exponentielle dans le cas particulier des chaînes réversibles.

Convergence de la mesure empirique

[modifier | modifier le code]

Si la chaîne de Markov est irréductible et récurrente positive alors, par suite de la loi forte des grands nombres, la mesure empirique de la chaîne de Markov,

converge vers l'unique distribution stationnaire. Typiquement, par exemple dans le cas d'une chaîne de Markov à espace d'états fini irréductible et récurrente positive, la convergence est, en un certain sens, en Cela permet d'approcher la probabilité stationnaire par un histogramme construit à partir d'une séquence particulière. Nota: alors que la loi de notée ci-dessus, est une mesure de probabilité fixée, la loi empirique est, elle, une mesure de probabilité aléatoire, ou bien, si l'on veut, une variable aléatoire à valeurs dans les mesures de probabilité.

Marche aléatoire réfléchie :

C'est la chaîne de Markov d'espace d'états de matrice de transition définie par pour tout et pour Ce modèle est étroitement lié à l'étude des files d'attente M/M/1. La marche aléatoire réfléchie est

  • irréductible pour
  • récurrente positive pour de loi stationnaire
  • récurrente nulle pour
  • transiente pour

On a dessiné ci-contre des exemples de distributions empiriques et de distributions stationnaires pour la marche réfléchie en 0, pour  : il semble que la convergence de l'une vers l'autre soit de plus en plus lente lorsque tend vers 0, i.e. quand on se rapproche des cas récurrents nuls et transients.

Chaînes réversibles

[modifier | modifier le code]

Théorème —  1. Si est une mesure de masse finie satisfaisant

alors est une probabilité stationnaire.

2. Plus généralement, si pour une mesure de masse finie il existe une matrice de transition satisfaisant

alors est une probabilité stationnaire.

3. Si est une probabilité stationnaire, associée à la matrice de transition telle que alors définie par

est une matrice de transition.

La matrice est l'adjointe de la matrice pour le produit scalaire défini par

Interprétation

[modifier | modifier le code]

Si une variable aléatoire à valeur dans satisfait, pour tout et toute suite

on dit que X est une chaîne de Markov stationnaire, de matrice de transition et de loi stationnaire En effet :

  • cela définit une et une seule mesure de probabilité sur  ;
  • X possède la propriété de Markov faible ;
  • stationnarité : la suite (définie par ) a même loi que la suite X, pour tout entier relatif s.

Renversons le cours du temps, i.e. considérons la suite définie par

On a alors

Proposition — 

  • Y est une chaîne de Markov stationnaire, de matrice de transition (définie au point 3 ci-dessus) et de loi stationnaire
  • Si ou, de manière équivalente, si
    alors X et Y ont même loi. On dit que ces deux chaînes de Markov sont réversibles.
Graphe de la marche du cavalier sur l'échiquier (quart Sud-Ouest), et degré des sommets

Marche aléatoire sur un graphe

[modifier | modifier le code]

Soit G un graphe connexe, fini, simple et sans boucles. Par définition,

i.e. à partir de on saute vers un de ses voisins choisis au hasard (avec équiprobabilité), désignant le degré de dans le graphe La connexité de entraîne l'irréductibilité de la marche aléatoire et l'unicité de la probabilité stationnaire. On remarque que satisfait le critère 2, or i.e. est deux fois le nombre d'arêtes de Ainsi est l'unique probabilité stationnaire : on passe d'autant plus de temps en un sommet que son degré est élevé, et ce temps de séjour asymptotique est proportionnel au degré du sommet, avec coefficient de proportionnalité Un exemple amusant est la marche aléatoire d'un cavalier sur un échiquier.

Marche du cavalier sur l'échiquier

[modifier | modifier le code]

C'est un cas particulier de l'exemple ci-dessus, où et Ainsi

c'est-à-dire qu'il faut en moyenne 168 sauts à un cavalier partant du coin Sud-Ouest pour y retourner. On peut étudier de la même manière les autres pièces du jeu d'échecs.

Deux chiens (disons A et B) se partagent N puces de la manière suivante : à chaque instant t entier, une des N puces est tirée au hasard et change alors de chien. Notons Xt le nombre de puces infestant A au temps t : X = (Xt)t≥0 est une chaîne de Markov en vertu du critère fondamental. Supposons que dans l'état initial, le chien A n'a aucune puce.

Cette chaîne de Markov est clairement irréductible. Si on la suppose réversible, on doit avoir

ce qui suggère une probabilité stationnaire, π = (πk )0≤kN, proportionnelle aux coefficients binomiaux. La seule loi de probabilité proportionnelle aux coefficients binomiaux est la loi binomiale de paramètre 1/2 (et N). La chaîne est donc bien réversible, et le temps écoulé entre deux passages par l'état initial est

Cet exemple illustre la réponse de Boltzmann à Zermelo : Zermelo observait[1] une contradiction entre le théorème de récurrence de Poincaré[2],[3], selon lequel un système dynamique repasse infiniment souvent par un état donné, et le théorème H de Boltzmann. La réponse de Boltzmann[4] consiste à estimer le temps de récurrence moyen : pour un gaz macroscopique contenant molécules, Boltzmann estime celui-ci d'ordre , une durée qui est largement supérieure à l'âge de l'univers[5] lorsque  ; les récurrences sont donc invisibles à notre échelle.

Théorie spectrale (cas fini)

[modifier | modifier le code]

On suppose

  • l'espace d'états E fini, à N éléments,
  • la chaîne réversible,
  • chaque πi strictement positif.

Alors[6]

Théorème — La matrice de transition P est diagonalisable à gauche dans une base orthonormée pour la distance du χ2 , i.e. dans une base orthonormée pour la forme bilinéaire

Ses valeurs propres à gauche sont réelles et de valeurs absolues inférieures à 1.

Convergence pour la distance du χ2

[modifier | modifier le code]

Si la chaîne est irréductible et apériodique, 1 est valeur propre de P de multiplicité 1, et les autres valeurs propres sont en valeur absolue strictement inférieures à 1. Si on note α le maximum de ces valeurs absolues et si on note μn la loi de la chaîne au temps n, on en déduit[6] que

Si l'erreur relative, au site i, est définie par

alors la distance du χ2 entre μn et π s'écrit

Ainsi les erreurs relatives sont moins pénalisantes si elles affectent les états les moins probables mais sont, toutefois, plus pénalisantes que si on utilise la distance euclidienne classique :

Théorème — La matrice de transition P possède N+1 valeurs propres distinctes :

Le vecteur ek défini par

est un vecteur propre à gauche de P associé à la valeur propre λk .

Ainsi, il y a convergence vers la loi stationnaire uniquement si la loi initiale μ est orthogonale à eN , i.e. si

En ce cas, il existe une constante CN telle que, pour tout entier naturel k, on ait :

Existence et unicité

[modifier | modifier le code]
Graphe d'une chaîne de Markov non irréductible à espace d'états fini, possédant 3 classes : et

Discuter l'existence et l'unicité d'une probabilité stationnaire telle que amène à discuter les propriétés du graphe de la chaîne de Markov et la classification de ses états, amène aussi à étudier les propriétés de la variable aléatoire appelée "temps de retour" en et souvent notée

Théorème —  On a équivalence entre les 2 propositions suivantes

  • L'état est récurrent positif,
  • il existe une probabilité stationnaire telle que

Si l'une des deux conditions précédentes est remplie, alors

  • la classe de l'état est une classe finale,
  • le support de contient
  • tous les éléments de sont récurrent positifs,

De plus, il y a équivalence entre

  • le support de est exactement i.e.
  • est un point extrémal de l'ensemble (convexe) des probabilités stationnaires.

En particulier, si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une probabilité stationnaire.

Exemple :

Pour la chaîne dont le graphe est représenté ci-dessus, l'ensemble des probabilités stationnaires est le segment dont les extrémités, correspondant aux deux classes finales et sont et Une probabilité stationnaire est nécessairement de la forme

Corollaire — Si une chaîne de Markov possède une seule classe finale alors il existe au plus une probabilité stationnaire. On a alors équivalence entre les 3 propositions :

  • il existe une probabilité stationnaire,
  • il existe un état récurrent positif,
  • tous les états de la classe finale sont récurrents positifs.

Supposons qu'une des 3 conditions ci-dessus soit remplie et notons l'unique probabilité stationnaire : alors

et on a la série d'équivalences

Ce théorème vaut en particulier pour les chaînes de Markov irréductibles, puisque ces dernières possèdent une seule classe (qui est donc nécessairement une classe finale) ; les chaînes de Markov irréductibles vérifient en particulier

  1. (de) Ernst Zermelo, « Uber einen Satz der Dynamik und der mechanischen Wärmetheorie », Wied. Ann., vol. 57,‎ , p. 793 (DOI 10.1002/andp.18962930314).
  2. Henri Poincaré, « Sur le problème des trois corps et les équations de la dynamique », Acta Mathamatica, vol. 13,‎ , p. 1-270.
  3. (de) Ludwig Boltzmann, « Uber einen mechanischen Satz von Poincaré », Akademie der Wissenschaften Wien, vol. 106,‎ , p. 12.
  4. (de) Ludwig Boltzmann, « Entgegnung auf die wärmetheoretische Betrachtung des Herrn Zermelo », Wien. Ann., vol. 57,‎ , p. 773 et vol. 60, p.392 (1897).
  5. Environ 15 milliards d'années.
  6. a et b Bernard Ycart, Modèles et algorithmes Markoviens, p.127-130.
  7. Mark Kac, Random Walk and the Theory of Brownian Motion, American Mathematical Monthly 54(7) (1947), 369-391. Texte au format pdf.

Bibliographie

[modifier | modifier le code]
  • Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on Probability Theory and Statistics, 301-413. Lecture Notes in Math. n° 1665. Springer (1997).
  • Jim Norris, Markov chains.
  • Samuel Karlin et Howard E. Taylor, A Second Course in Stochastic Processes.

Pages liées

[modifier | modifier le code]