Chaînes de Markov à temps discret

Une chaîne de Markov à temps discret évolue entre un ensemble dénombrable d'états à des instants entiers, choisissant son état suivant à partir de probabilités qui ne dépendent que de l'état actuel, ces probabilités étant encodées de manière compacte dans une matrice de transition.

Definition

Une chaîne de Markov à temps discret est une séquence d'états aléatoires dans un ensemble dénombrable telle que la probabilité de l'état suivant ne dépend que de l'état actuel, ces probabilités de transition en un pas étant regroupées dans une matrice de transition.

Scope

Ce sujet couvre les matrices de transition et les équations de Chapman-Kolmogorov, la propriété de Markov forte, la classification des états en classes communicantes et en états transitoires, nuls-récurrents et positifs-récurrents, la périodicité, les probabilités d'atteinte et les temps d'atteinte espérés calculés par analyse du premier pas, ainsi que la dichotomie de récurrence pour les marches aléatoires sur le réseau entier.

Core questions

• Comment une matrice de transition encode-t-elle la dynamique d'une chaîne sur plusieurs étapes ?
• Comment les états sont-ils classifiés selon leur structure de communication et leur récurrence ?
• Comment les probabilités d'atteinte et les temps d'atteinte espérés sont-ils calculés ?
• Quelles marches aléatoires reviennent à leur point de départ avec certitude et lesquelles s'échappent à l'infini ?

Key concepts

• matrice de transition
• équations de Chapman-Kolmogorov
• classes communicantes
• récurrence et transience
• temps d'atteinte

Key theories

Propriété de Markov forte

La propriété de Markov continue de s'appliquer à des instants aléatoires appropriés appelés temps d'arrêt, de sorte qu'une chaîne redémarre à neuf à partir de son état à un tel instant, ce qui est l'outil clé pour analyser les retours, les excursions et les temps d'atteinte.

Dichotomie de récurrence

Chaque état est soit récurrent, visité infiniment souvent avec une probabilité de un, soit transitoire, visité seulement un nombre fini de fois ; pour une marche aléatoire simple et symétrique, cela dépend de la dimension, avec récurrence en une et deux dimensions et transience en trois dimensions et plus.

Clinical relevance

Les chaînes de Markov à temps discret modélisent les jeux de société, les systèmes de gestion des stocks et de files d'attente, la navigation web via la chaîne PageRank, ainsi que la succession génétique et écologique ; leur théorie des temps d'atteinte et de la récurrence répond à des questions pratiques sur le temps nécessaire à un système pour atteindre un état cible ou revenir à une condition de référence.

History

Markov a introduit ces chaînes en 1906, les appliquant à la séquence de voyelles et de consonnes dans un poème de Pouchkine pour montrer que la loi des grands nombres s'applique aux variables dépendantes. L'analyse des marches aléatoires par Polya en 1921 a établi la dichotomie de récurrence dépendante de la dimension qui porte son influence.

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

Quelle est la différence entre un état récurrent et un état transitoire ?

Un état récurrent est un état auquel la chaîne est certaine de revenir, et qu'elle visite donc infiniment souvent, tandis qu'un état transitoire n'est visité qu'un nombre fini de fois avant que la chaîne ne s'éloigne définitivement.

Pourquoi la marche aléatoire simple est-elle récurrente en basses dimensions mais pas en hautes dimensions ?

En une et deux dimensions, la marche retourne à l'origine avec une probabilité de un, mais à partir de trois dimensions, il y a suffisamment d'espace pour s'échapper, de sorte que la marche ne revient qu'un nombre fini de fois et est transitoire ; c'est le résultat classique de Polya.