Chaîne de Markov - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Introduction

Selon les auteurs, une chaîne de Markov est de manière générale un processus de Markov à temps discret ou un processus de Markov à temps discret et à espace d'états discret. En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov : de manière simplifiée, la prédiction du futur, sachant le présent, n'est pas rendue plus précise par des éléments d'information supplémentaires concernant le passé (Le passé est d'abord un concept lié au temps : il est constitué de l'ensemble des configurations successives du monde et s'oppose au futur sur une échelle des temps centrée...). Les processus de Markov portent le nom de leur découvreur, Andreï Markov.

Un processus de Markov à temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) discret est une séquence \scriptstyle\ X_0, \scriptstyle\ X_1, \scriptstyle\ X_2, \scriptstyle\ X_3,\ \dots de variables aléatoires à valeurs dans l’espace des états, qu'on notera \scriptstyle\ E\ dans la suite. La valeur \scriptstyle\ X_n\ est l'état du processus à l'instant \scriptstyle\ n. Les applications où l'espace d'états \scriptstyle\ E\ 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.

Andrei Markov a publié les premiers résultats sur les chaînes de Markov à espace d'états fini en 1906. Une généralisation (La généralisation est un procédé qui consiste à abstraire un ensemble de concepts ou d'objets en négligeant les détails...) à un espace d'états infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en...) dénombrable a été publiée par Kolmogorov en 1936. Les processus de Markov sont liés au mouvement brownien (Le mouvement brownien, ou processus de Wiener est une description mathématique du mouvement aléatoire d'une « grosse » particule immergée dans un fluide et qui n'est...) et à l'hypothèse ergodique, deux sujets de physique statistique (La physique statistique a pour but d'expliquer le comportement et l'évolution de systèmes physiques comportant un grand nombre de particules...) qui ont été très importants au début du XXe siècle.

Propriété de Markov faible

Définitions

C'est la propriété caractéristique d'une chaîne (Le mot chaîne peut avoir plusieurs significations :) 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 \scriptstyle\ X_{n+1}\ sachant le passé, i.e. sachant \scriptstyle\ \left(X_k\right)_{0\le k\le n},\ est une fonction de \scriptstyle\ X_n\ seul :

\begin{align}\forall n\ge 0, \forall (i_0,\ldots,i_{n-1},i,j)&\in E^{n+2}, \\ \mathbb{P}\Big(X_{n+1}=j&\mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) = \mathbb{P}\left(X_{n+1}=j\mid X_n=i\right). \end{align}

On suppose le plus souvent les chaînes de Markov homogènes, i.e. on suppose que le mécanisme de transition ne change pas au cours du temps. La propriété de Markov faible prend alors la forme suivante :

\begin{align}\forall n\ge 0, \forall (i_0,\ldots,i_{n-1},i,j)&\in E^{n+2}, \\ \mathbb{P}\Big(X_{n+1}=j&\mid\, X_0=i_0, X_1=i_1,\ldots, X_{n-1}=i_{n-1},X_n=i\Big) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right). \end{align}

Cette forme de la propriété de Markov faible est plus forte que la forme précédente, et entraîne en particulier que

\forall n\ge 0, \forall (i,j)\in E^{2},\qquad\mathbb{P}\left(X_{n+1}=j\mid X_n=i\right) = \mathbb{P}\left(X_{1}=j\mid X_0=i\right).

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 (L’optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la...), 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 (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de propositions initiales, en s'appuyant sur...) 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

Critère fondamental — Soit une suite \scriptstyle\ Y=(Y_{n})_{n\ge 1}\ de variables aléatoires indépendantes et de même loi, à valeurs dans un espace \scriptstyle\ F\ , et soit \scriptstyle\ f\ une application mesurable de \scriptstyle\ E\times F\ dans \scriptstyle\ E.\ Supposons que la suite \scriptstyle\ X=(X_{n})_{n\ge 0}\ est définie par la relation de récurrence :

\forall n\ge 0,\qquad X_{n+1}=f\left(X_n,Y_{n+1}\right),

et supposons que la suite \scriptstyle\ Y\ est indépendante de \scriptstyle\ X_0.\ Alors \scriptstyle\ X\ est une chaîne de Markov homogène.

Collectionneur de vignettes (coupon collector)  :

Petit Pierre fait la collection des portraits des onze joueurs de l'équipe nationale de football, qu'il trouve sur des vignettes à l'intérieur de l'emballage des tablettes de chocolat ; chaque fois qu'il achète une tablette il a une chance sur 11 de tomber sur le portrait du joueur n°\scriptstyle\ k\ (pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) \scriptstyle\ k\ ). On note \scriptstyle\ X_{n}\in\mathcal{P}([\![ 1,11]\!])\ l'état de la collection de Petit Pierre, après avoir ouvert l'emballage de sa \scriptstyle\ n\ -ème tablette de chocolat. \scriptstyle\ X=(X_{n})_{n\ge 0}\ est une chaîne de Markov partant de \scriptstyle\ X_{0}=\emptyset\ , car elle rentre dans le cadre précédent pour le choix \scriptstyle\ F=[\![1,11]\!],\ E=\mathcal{P}(F),\ f(x,y)=x\cup\{y\},\ puisque

 X_{n+1}=X_n\cup\{Y_{n+1}\},

où les variables aléatoires \scriptstyle\ Y_{n}\ sont des variables aléatoires indépendantes et uniformes sur \scriptstyle\ [\![1,11]\!]\  : ce sont les numéros successifs des vignettes tirées des tablettes de chocolat. Le temps moyen nécessaire pour compléter la collection (ici le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de tablettes que Petit Pierre doit acheter en moyenne (La moyenne est une mesure statistique caractérisant les éléments d'un ensemble de quantités : elle exprime la grandeur qu'auraient chacun des membres de l'ensemble s'ils étaient tous...) pour compléter sa collec') est, pour une collection de \scriptstyle\ N\ vignettes au total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". En physique le total n'est pas...), de \scriptstyle\ N\,H_N,\ \scriptstyle\ H_N\ est le \scriptstyle\ N\ -ème nombre harmonique (Dans plusieurs domaines, une harmonique est un élément constitutif d'un phénomène périodique ou vibratoire (par exemple en électricité : les...). Par exemple, \scriptstyle\ 11\,H_{11}=33,2\dots\quad tablettes de chocolat.

Remarques  :
  • La propriété de Markov découle de l'indépendance des \scriptstyle\ Y_i\ ;\ elle reste vraie lorsque les \scriptstyle\ Y_i\ ont des lois différentes, et lorsque la "relation de récurrence" \scriptstyle\ X_{n+1}=f_n\left(X_n,Y_{n+1}\right)\ dépend de \scriptstyle\ n.\ Les hypothèses faites en sus de l'indépendance sont là uniquement pour assurer l'homogénéité de la chaîne de Markov.
  • Le critère est fondamental en cela que toute chaîne de Markov homogène peut être simulée via une récurrence de la forme \scriptstyle\ X_{n+1}=f\left(X_n,Y_{n+1}\right),\ pour une fonction \scriptstyle\ f\ bien choisie. On peut même choisir \scriptstyle\ F=[0,1],\ et choisir des variables \scriptstyle\ Y_{j}\ indépendantes et uniformes sur l'intervalle [0,1], ce qui est commode pour l'étude de chaînes de Markov via des méthodes de Monte-Carlo.
Page générée en 0.084 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique