Probabilité stationnaire d'une chaîne de Markov

La probabilité stationnaire d'une chaîne de Markov s'interprète habituellement comme la fraction du temps passé en chaque état de l'espace d'états de cette chaîne de Markov, asymptotiquement.



Catégories :

Processus stochastique - Physique statistique - Statistiques

Page(s) en rapport avec ce sujet :

  • Cette chaîne de Markov admet-elle une loi de probabilité réversible ?.... Suite markovienne stationnaire. Une source émet une suite de chiffres choisis... (source : wims.unicaen)
  • Examen – Probabilités. 19 déc. 2007... 2.3 Distribution stationnaire d'une chaîne de Markov rationnelle. On considère une chaîne de Markov régulière à n... (source : pdfqueen)
  • Théorème 6 : Une chaine de Markov irréductible et récurrente positive possède une et une seule probabilité stationnaire π. Cette probabilité stationnaire π... (source : perso-math.univ-mlv)

La probabilité stationnaire d'une chaîne de Markov s'interprète habituellement 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 :

 \pi_i\ =\ \lim_n\ \frac{1_{X_0=i}+1_{X_1=i}+\dots+1_{X_{n-2}=i}+1_{X_{n-1}=i}}{n}\ =\ \lim_n\ \frac{S_n(i)}{n},

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 par conséquent la fraction de temps passé en l'état pendant les premiers pas de la chaîne de Markov. La convergence de cette fraction quand 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

Définition — 

  • Une mesure sur l'espace d'états d'une chaîne de Markov de matrice de transition est dite stationnaire si
 \mu = \mu\,P,
ou, de manière équivalente,
\forall j\in E,\qquad \mu_j = \sum_{i\in E}\mu_i\,p_{i,j}.
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 nommée probabilité stationnaire ou loi stationnaire si elle remplit les conditions supplémentaires :
\forall i\in E, \qquad \pi_i\ \ge\ 0,
\text{et}\qquad\sum_{i\in E}\pi_i\ =\ 1.
Remarques :
  • La chaîne de Markov est un processus stationnaire, i. e., pour tout a même loi de probabilité que si et uniquement si la loi initiale de (la loi de) est une probabilité stationnaire.
  • Cela entraîne surtout que si la loi d'origine de la chaîne de Markov est une probabilité stationnaire, alors la loi de est cette même probabilité stationnaire, indépendamment de
  • La totalité des probabilités stationnaires est convexe.

Existence et unicité : cas irréductible

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 surtout 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
T_i=\left\{\begin{array}{ll}\inf\{k\ge 1\,|\,X_k=i\}&\text{ si }\{k\ge 1\,|\,X_k=i\}\neq\emptyset,\\+\infty&\text{ sinon.}\end{array}\right..
  • 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
\mathbb{E}_i\left[T_i\right]\ <\ +\infty.

Rappelons que quand on étudie une chaîne de Markov spécifique, sa matrice de transition est généralement bien définie et fixée tout au long de l'étude, mais la loi d'origine peut changer lors de l'étude et les notations doivent refléter la loi d'origine reconnue sur le moment : si à un moment de l'étude on considère une chaîne de Markov de loi d'origine définie par alors les probabilités sont notées et les espérances sont notées Surtout, 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 veut dire qu'on calcule l'espérance pour la chaîne de Markov partant de i. e. de loi d'origine 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

\forall i\in E,\quad \pi_i\ =\ \frac1{\mathbb{E}_i\left[T_i\right]}.

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).

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 totalement général à la section Existence et unicité. Cependant les théorèmes ci-dessus, valables seulement pour les chaînes de Markov irréductibles, sont suffisants dans la plupart d'exemples.

Loi forte des grands nombres

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 exactement, sous l'hypothèse

\sum_{i\in E} |f(i)|\,\pi_i\ < +\infty,

on a presque sûrement :

 \lim_{n}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} f(X_k)
  \ =\ \sum_{i\in E} f(i)\,\pi_i\ =\ \pi f.

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

 \lim_{n}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} 1_A(X_k)\ 
=\ \sum_{i\in A}\ \pi_i\ =\ \pi(A).

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

Ergodicité

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

préserve la mesure, ce qui fait de la chaîne de Markov un dispositif dynamique. La loi forte des grands nombres entraine tandis que la chaîne de Markov est un dispositif 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 habituellement 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

Convergence de la loi marginale

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 Surtout, la loi de converge vers indépendamment de la loi d'origine 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, récurrente positive et apériodique, la convergence est exponentiellement rapide, i. e. pour une norme quelconque, on peut trouver 0\ " src="http ://upload. wikimedia. org/math/4/8/7/487289c2a3c58255441b15c219ebc00e. png" /> et tels que

\Vert\mu_n-\pi\Vert \le K\ \alphaˆn.

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

Convergence de la mesure empirique

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,

\tfrac1n\quad\sum_{k=0}ˆ{n-1}\,\delta_{X_k}\quad=\quad \tfrac1n\quad\sum_{i\in E}\ S_n(i)\,\delta_{i},

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 spécifique. Nota : tandis 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 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 0.5. \quad" src="http ://upload. wikimedia. org/math/5/a/5/5a5ab9e56bb94a29e3c906f8993a3286. png" />

On a dessiné ci-contre des exemples de distributions empiriques et de distributions stationnaires pour la marche réfléchie en 0, pour 0\quad" src="http ://upload. wikimedia. org/math/f/b/9/fb9998bd66e66f8631bf18022ef3597f. png" /> : il semble que la convergence de l'une vers l'autre soit de plus en plus lente quand tend vers 0, i. e. lorsque on se rapproche des cas récurrents nuls et transients.

Chaînes réversibles

Critères

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

\forall i,j\in E,\qquad \mu_ip_{i,j} = \mu_jp_{j,i} ,

alors est une probabilité stationnaire.

2. D'une façon plus générale, si pour une mesure de masse finie il existe une matrice de transition satisfaisant

\forall i,j\in E,\qquad \mu_ip_{i,j} = \mu_jq_{j,i} ,

alors est une probabilité stationnaire.

3. Si est une probabilité stationnaire, associée à la matrice de transition telle que 0, \qquad" src="http ://upload. wikimedia. org/math/6/7/0/670bb8fb8036fa3170daa49b4851c245. png" /> alors définie par

q_{i,j} = \frac{\pi_jp_{j,i}}{\pi_i},

est une matrice de transition.

Interprétation

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

\mathbb{P}\left((X_t,X_{t+1},\dots,X_{t+n})=(i_0,i_1,\dots,i_n)\right)= \pi_{i_0}p_{i_0,i_1}\dots p_{i_{n-1},i_n}

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

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

Yt = X t.

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
    \pi_ip_{i,j}\equiv\pi_jp_{j,i},\
    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

Exemples

Marche aléatoire sur un graphe

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

\forall i,j\in E=V(G),\text{ tels que }i\sim j,\qquad p_{i,j} = \frac1{d_i},

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 cœfficient de proportionnalité Un exemple amusant est la marche aléatoire d'un cavalier sur un échiquier.

Marche du cavalier sur l'échiquier

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

\pi_{\text{coin SO}} = \frac{2}{336}\quad\text{et}\quad\mathbb{E}_{\text{coin SO}}\left[T_{\text{coin SO}}\right]=168,

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'Ehrenfest

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 essentiel. Supposons que dans l'état d'origine, 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

\frac{\pi_{k+1}}{\pi_{k}}\ =\ \frac{p_{k,k+1}}{p_{k+1,k}}\ =\ \frac{N-k}{k+1}\ =\ \frac{{N\choose k+1}}{{N\choose k}},

ce qui suggère une probabilité stationnaire, π = (πk) 0≤k≤N, proportionnelle aux cœfficients binomiaux. L'unique loi de probabilité proportionnelle aux cœfficients binomiaux est la loi binomiale de paramètre 1/2 (et N). La chaîne est par conséquent bien réversible, et le temps écoulé entre deux passages par l'état d'origine est

\mathbb{E}_{0}\left[T_{0}\right]\ =\ \frac1{\pi_{0}}\ =\ 2ˆN.

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 dispositif dynamique repasse illimitément fréquemment 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 ce dernier d'ordre, une durée qui est beaucoup supérieure à l'age de l'univers[5] quand  ; les récurrences sont par conséquent invisibles à notre échelle.

Théorie spectrale (cas fini)

On suppose

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

\langle x,y\rangle\ =\ \sum_{i=1}ˆN\, \frac{x_i\,y_i}{\pi_i}.

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

Convergence pour la distance du χ2

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

\langle \mu_n-\pi,\mu_n-\pi\rangle\ \le\ C\,\alphaˆ{2n}.

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

\varepsilon_i=\frac{\mu_{n,i}-\pi_i}{\pi_i},

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

\langle \mu_n-\pi,\mu_n-\pi\rangle\ =\ \sum_{i=1}ˆN\,\pi_i\,\varepsilon_iˆ2.

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

\Vert\mu_n-\pi\Vertˆ2\ =\  \sum_{i=1}ˆN\,(\mu_{n,i}-\pi_i)ˆ2\ =\  \sum_{i=1}ˆN\,\pi_iˆ2\,\varepsilon_iˆ2.

Théorie spectrale (cas du modèle des urnes d'Ehrenfest)

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

1=\lambda_{0}\ge\lambda_{1}\ge\dots\ge\lambda_{k}=\tfrac{N-2k}N\ge\dots\ge\lambda_{N}=-1.

Le vecteur ek défini par

(1-X)ˆ{k}(1+X)ˆ{N-k}\,=\,\sum_{j=0}ˆ{N}\ e_{k,j}Xˆ{j}

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

Ainsi, il y a convergence vers la loi stationnaire seulement si la loi d'origine μ est orthogonale à eN, i. e. si

\sum_{i=0}ˆN\,(-1)ˆi\,\mu_i=0.

En ce cas

\Vert\mu.Pˆk-\pi\Vert\le C\left(1-\tfrac2N\right)ˆk.

Existence et unicité

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 0\ " src="http ://upload. wikimedia. org/math/2/8/6/286dd41952dab6437217b2255705b62d. png" /> 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 nommée "temps de retour" en et fréquemment 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 0. \ " src="http ://upload. wikimedia. org/math/2/d/0/2d007b36f8b676b657639bfd35a61e43. png" />

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 précisément i. e. 0\}\Leftrightarrow\{j\in C\}, " src="http ://upload. wikimedia. org/math/4/5/1/451a4cdbfbd0571b9db468a4e4c00fa2. png" />
  • est un point extrémal de la totalité (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, la totalité des probabilités stationnaires est le segment dont les extrémités, correspondant aux deux classes finales et sont et Une probabilité stationnaire est obligatoirement 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

\forall i\in E,\quad \pi_i\ =\ \frac1{\mathbb{E}_i\left[T_i\right]},

et on a la série d'équivalences

<img class=A voir

Notes

  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. À peu près 15 milliards d'années.
  6. 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

  • 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

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Probabilit%C3%A9_stationnaire_d%27une_cha%C3%AEne_de_Markov.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu