Probabilité stationnaire d'une chaîne de Markov

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éfinitionModifier

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 les conditions supplémentaires :
 
 
Remarques :
  • 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éductibleModifier

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 nombresModifier

 
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

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 stationnaireModifier

Convergence de la loi marginaleModifier

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 empiriqueModifier

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éversiblesModifier

CritèresModifier

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étationModifier

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

ExemplesModifier

Marche aléatoire sur un grapheModifier

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'échiquierModifier

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.

Modèle des urnes d'EhrenfestModifier

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≤k≤N , 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

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

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éorie spectrale (cas du modèle des urnes d'Ehrenfest)Modifier

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

 
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  

À voirModifier

NotesModifier

  1. Ernst Zermelo ; Uber einen Satz der Dynamik une der mechanischen Wärmetheorie, Wied. Ann. 57 (1896), 793.
  2. Henri Poincaré ; Sur le problème des trois corps et les équations de la dynamique, Acta Mathamatica 13 (1890), 1-270.
  3. Ludwig Boltzmann ; Uber einen mechanischen Satz von Poincaré, Wien. Ber. 106 (1897), 12.
  4. Ludwig Boltzmann ; Entgegnung auf die wärmetheoretische Betrachtung des Herrn Zermelo, Wied. Ann. \textbf{57} (1896), 773 ; et : \textbf{60} (1897), 392.
  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.

BibliographieModifier

  • 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éesModifier