vignette|Exemple élémentaire de chaîne de Markov, à deux états A et E. Les flèches indiquent les probabilités de transition d'un état à un autre.
En mathématiques, une chaîne de Markov est un processus de Markov à temps discret, ou à temps continu et à espace d'états discret. Un processus de Markov est un processus stochastique possédant la propriété de Markov : l'information utile pour la prédiction du futur est entièrement contenue dans l'état présent du processus et n'est pas dépendante des états antérieurs (le système n'a pas de « mémoire »). Les processus de Markov portent le nom de leur inventeur, Andreï Markov.
Un processus de Markov à temps discret est une séquence de variables aléatoires à valeurs dans l’espace des états, qu'on notera dans la suite. La valeur est l'état du processus à l'instant Les applications où l'espace d'états est fini ou dénombrable sont innombrables : on parle alors de chaîne de Markov ou de chaînes de Markov à espace d'états discret. Les propriétés essentielles des processus de Markov généraux, par exemple les propriétés de récurrence et d'ergodicité, s'énoncent ou se démontrent plus simplement dans le cas des chaînes de Markov à espace d'états discret. Cet article concerne précisément les chaînes de Markov à espace d'états discret.
Andreï Markov a publié les premiers résultats sur les chaînes de Markov à espace d'états fini en 1906. Une généralisation à un espace d'états infini dénombrable a été publiée par Kolmogorov en 1936. Les processus de Markov sont liés au mouvement brownien et à l'hypothèse ergodique, deux sujets de physique statistique qui ont été très importants au début du .
Propriété de Markov faible
Définitions C'est la propriété caractéristique d'une chaîne de Markov : la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé, car toute l'information utile pour la prédiction du futur est contenue dans l'état présent du processus. La propriété de Markov faible possède plusieurs formes équivalentes qui reviennent toutes à constater que la loi conditionnelle de sachant le passé, c'est-à-dire sachant est une fonction de seul :
Une variante courante des chaînes de Markov est la chaîne de Markov homogène, pour laquelle la probabilité de transition est indépendante de :
Dans la suite de l'article on ne considèrera que des chaînes de Markov homogènes. Pour une application intéressante des chaînes de Markov non homogènes à l'optimisation combinatoire, voir l'article Recuit simulé. Il existe une propriété de Markov forte, liée à la notion de temps d'arrêt : cette propriété de Markov forte est cruciale pour la démonstration de résultats importants (divers critères de récurrence, loi forte des grands nombres pour les chaînes de Markov). Elle est énoncée dans l'article « Propriété de Markov ».
Critère
Probabilités de transition Définition
La terminologie matrice de transition est la plus utilisée, mais elle n'est appropriée, en toute rigueur, que lorsque, pour un entier Lorsque est fini, par exemple de cardinal on peut toujours numéroter les éléments de arbitrairement de 1 à ce qui règle le problème, mais imparfaitement, car cette renumérotation est contre-intuitive dans beaucoup d'exemples.
Plutôt que de renuméroter les états à partir de 1, il est donc plus ergonomique dans beaucoup de cas d'accepter des matrices finies ou infinies dont les lignes et colonnes sont « numérotées » à l'aide des éléments de Le produit de deux telles « matrices », et , est alors défini très naturellement par
par analogie avec la formule plus classique du produit de deux matrices carrées de taille
Propriétés
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 .
Puissances de la matrice de transition Pour la probabilité de transition en pas, ne dépend pas de :
Par une simple application de la formule des probabilités totales, on en déduit les lois marginales de la chaîne de Markov.
Classification des états
Pour , on dit que est accessible à partir de si et seulement s'il existe tel que On note :
On dit que et communiquent si et seulement s'il existe tels que et On note :
La relation communiquer, notée est une relation d'équivalence. Quand on parle de classe en parlant des états d'une chaîne de Markov, c'est en général aux classes d'équivalence pour la relation qu'on fait référence. Si tous les états communiquent, la chaîne de Markov est dite irréductible.
La relation être accessible, notée s'étend aux classes d'équivalence : pour deux classes et , on a
La relation est une relation d'ordre entre les classes d'équivalence.
Une classe est dite finale si elle ne conduit à aucune autre, i.e. si la classe est minimale pour la relation Sinon, elle est dite transitoire. L'appartenance à une classe finale ou transitoire a des conséquences sur les propriétés probabilistes d'un état de la chaîne de Markov, en particulier sur son statut d'état récurrent ou d'état transient. Le nombre et la nature des classes finales dicte la structure de l'ensemble des probabilités stationnaires, qui résument de manière précise le comportement asymptotique de la chaîne de Markov, comme on peut le voir à la prochaine section et dans les deux exemples détaillés à la fin de cette page.
Soit
La période d'un état est le PGCD de l'ensemble Si deux états communiquent, ils ont la même période : on peut donc parler de la période d'une classe d'états. Si la période vaut 1, la classe est dite apériodique. L'apériodicité des états d'une chaîne de Markov conditionne la convergence de la loi de vers la probabilité stationnaire, voir la page Probabilité stationnaire d'une chaîne de Markov.
La classification des états et leur période se lisent de manière simple sur le graphe de la chaîne de Markov. Toutefois, si tous les éléments de la matrice de transition sont strictement positifs, la chaîne de Markov est irréductible et apériodique : dessiner le graphe de la chaîne de Markov est alors superflu.
Loi stationnaire
Définition Il peut exister une ou plusieurs mesures sur l'espace d'états telles que :
ou bien encore
Une telle mesure est appelée une mesure stationnaire. Une mesure stationnaire est une fonction propre de la transposée de la matrice de transition, associée à la valeur propre 1. Elle est appelée probabilité stationnaire ou loi stationnaire si elle remplit les conditions supplémentaires :
Le terme « stationnaire » est justifié par la proposition suivante :
Plus généralement, la chaîne de Markov est un processus stationnaire si et seulement si sa loi initiale est une probabilité stationnaire.
Existence et unicité
Dans le cas des chaînes de Markov à espace d'états discret, certaines propriétés du processus déterminent s'il existe ou non une probabilité stationnaire, et si elle est unique ou non : une chaîne de Markov est irréductible si tout état est accessible à partir de n'importe quel autre état ; un état est récurrent positif si l'espérance du temps de premier retour en cet état, partant de cet état, est finie.
Si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une probabilité stationnaire. S'il existe une probabilité stationnaire telle que , alors l'état est récurrent positif, et réciproquement.
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
Loi forte des grands nombres et ergodicité 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 suivant 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 la distribution empirique (qui est un histogramme construit à partir d'une séquence particulière), comme dans le cas de la marche aléatoire avec barrière.
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 mesuré. 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 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. Notons qu'il est naturel que la suite définie par récurrence par la relation ait, éventuellement, pour limite un point fixe de cette transformation, i.e. une solution de l'équation
Chaînes de Markov à espace d'états fini
Si une chaîne de Markov est irréductible et si son espace d'états est fini, tous ses états sont récurrents positifs. La loi forte des grands nombres est alors en vigueur.
Plus généralement, tous les éléments d'une classe finale finie sont récurrents positifs, que l'espace d'états soit fini ou bien infini dénombrable.
Distributions quasi-stationnaires d'une chaîne de Markov absorbée
Soit une chaîne de Markov sur l'ensemble des entiers naturels . Supposons que l'état 0 soit absorbant et la chaîne soit absorbée en 0 presque sûrement. Soit le temps d'absorption en 0. On dit qu'une probabilité sur est une distribution quasi-stationnaire si pour tout et pour tout ,
On dit qu'une probabilité sur est une limite de Yaglom si pour tout et tout ,
Une limite de Yaglom est une distribution quasi-stationnaire. Si elle existe, la limite de Yaglom est unique. En revanche, il peut y avoir plusieurs distributions quasi-stationnaires.
Si est une distribution quasi-stationnaire, alors il existe un nombre réel tel que .
Notation Dans les formules qui précèdent, l'élément () est la probabilité de la transition de à . La somme des éléments d'une ligne vaut toujours 1 et la distribution stationnaire est donnée par le vecteur propre gauche de la matrice de transition.
On rencontre parfois des matrices de transition dans lesquelles le terme () est la probabilité de transition de vers , auquel cas la matrice de transition est simplement la transposée de celle décrite ici. La somme des éléments d'une colonne vaut alors 1. De plus, la distribution stationnaire du système est alors donnée par le vecteur propre droit de la matrice de transition, au lieu du vecteur propre gauche.
Exemple : Doudou le hamster