Chaînes de Markov à temps discret

Une chaîne de Markov à temps discret est une séquence d'états aléatoires évoluant en temps entier, de sorte que la distribution de l'état suivant ne dépend que de l'état actuel, et non de l'historique complet.

Definition

Une chaîne de Markov à temps discret est un processus stochastique sur un espace d'états dénombrable indexé par les entiers non négatifs, dont la distribution conditionnelle de l'état suivant, étant donné l'historique complet, ne dépend que de l'état présent, encodée par une matrice de probabilité de transition à une étape.

Scope

Ce domaine couvre la propriété de Markov et les matrices de transition, la classification des états par communication, récurrence, transience et périodicité, l'existence et l'unicité des distributions stationnaires et limites, les taux de convergence et de mélange, ainsi que les principales applications, notamment les méthodes de Monte Carlo par chaînes de Markov et les modèles de Markov cachés.

Sub-topics

• Modèles de Markov cachés
• Classification et récurrence des chaînes de Markov
• Chaîne de Markov Monte Carlo
• Distributions stationnaires et convergence

Core questions

• Que signifie la propriété de Markov et comment est-elle représentée par une matrice de transition ?
• Comment les états sont-ils classifiés en classes récurrentes, transitoires et périodiques ?
• Quand une chaîne possède-t-elle une distribution stationnaire unique et converge-t-elle vers celle-ci ?
• À quelle vitesse une chaîne approche-t-elle l'équilibre, et comment cela est-il exploité en simulation ?

Key theories

Propriété de Markov et équations de Chapman-Kolmogorov

Le futur est conditionnellement indépendant du passé étant donné le présent, de sorte que les probabilités de transition à plusieurs étapes sont obtenues en multipliant les matrices de transition, ce qui rend le comportement à n étapes calculable à partir de la matrice à une étape.

Théorème ergodique pour les chaînes de Markov

Une chaîne irréductible, apériodique et positivement récurrente possède une distribution stationnaire unique vers laquelle la distribution marginale converge et par rapport à laquelle les moyennes temporelles des fonctions convergent presque sûrement, reliant ainsi les fréquences à long terme à la loi stationnaire.

Clinical relevance

Les chaînes de Markov à temps discret modélisent les marches aléatoires, les instantanés de files d'attente, la génétique des populations, les algorithmes de classement tels que PageRank, et les transitions d'états économiques ; leur théorie de la convergence sous-tend les méthodes de Monte Carlo par chaînes de Markov, la méthode de calcul dominante pour l'échantillonnage à partir de distributions de probabilité complexes en statistique, en physique et en apprentissage automatique.

History

Andrey Markov a introduit des chaînes avec des transitions dépendantes mais sans mémoire en 1906 pour étendre la loi des grands nombres au-delà de l'indépendance, les illustrant avec des séquences de lettres dans la poésie de Pushkin. Kolmogorov et Doeblin ont établi la théorie de la convergence sur des fondements rigoureux basés sur la théorie de la mesure dans les années 1930.

Key figures

• Andrey Markov
• Andrey Kolmogorov
• Wolfgang Doeblin

Seminal works

• norris1997

Frequently asked questions

Qu'est-ce qui fait qu'un processus est une chaîne de Markov ?

La propriété de Markov : étant donné l'état présent, l'évolution future est indépendante de la manière dont la chaîne a atteint cet état, de sorte que l'ensemble de la dynamique est décrit par des probabilités de transition à une étape.

Quand une chaîne de Markov converge-t-elle vers une distribution unique à long terme ?

Lorsqu'elle est irréductible, apériodique et positivement récurrente ; il existe alors une unique distribution stationnaire vers laquelle la chaîne converge, quel que soit son état de départ.