Processus de Markov

En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov. Dans un tel processus, la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information concernant le passé.

Catégories :

Processus stochastique - Physique statistique - Statistiques

En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov. Dans un tel processus, la prédiction du futur à partir du présent n'est pas rendue plus précise par des éléments d'information concernant le passé. Les processus de Markov portent le nom de leur découvreur, Andreï Markov.

Un processus de Markov en temps discret est une séquence de variables aléatoires. La totalité de leurs valeurs envisageables est nommé l'espace d'états, la valeur étant l'état du processus à l'instant Selon les auteurs, le terme «chaîne de Markov» sert à désigner les processus de Markov à temps discret ou seulement les processus de Markov à temps discret ainsi qu'à espace d'états discret, i. e. les processus de Markov à temps discret dont l'espace d'états est fini ou dénombrable.

Si la loi conditionnelle de sachant le passé, i. e. sachant est une fonction de seul, alors :

$P(X_{n+1}=x\mid X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x\mid X_n). \,$

où $x$ est un état quelconque du processus. L'identité ci-dessus identifie la probabilité markovienne.

Andreï Markov a publié les premiers résultats de ces processus en 1906.

Une généralisation à un espace d'états illimité dénombrable a été donnée par Kolmogorov en 1936.

Les processus de Markov sont liées au mouvement brownien ainsi qu'à l'hypothèse ergodique, deux sujets de physique statistique qui ont été particulièrement importants au début du XX^e siècle.

Types de processus de Markov

Espace d'états discret

Quand les variables aléatoires successives sont des variables discrètes pourvues d'une fonction de probabilité, on parle de chaîne de Markov.

Bien que les chaînes de Markov s'appliquent à des phénomènes dont l'aspect temporel est le plus souvent sans intérêt, on peut associer aux valeurs successives $x_i\,$ les instants $t_i\,$ . La propriété markovienne selon laquelle la probabilité d'un état du dispositif ne dépend que de son état précédent à travers une probabilité conditionnelle nommée probabilité de transition s'exprime par :

$<img class=$ et la probabilité de transition. On obtient par exemple la probabilité au second ordre par :

$<img class=$ Espace d'états continu

Les chaînes de Markov trouvent des applications dans les domaines les plus divers mais les processus reconnus dans les problèmes dynamiques, surtout en vibrations, portent le plus souvent sur des variables aléatoires continues.

Dans ces conditions, la probabilité d'obtenir une valeur donnée est le plus souvent nulle et les probabilités d'apparition doivent être remplacées par des densités de probabilité dans la formule de la propriété markovienne :

$<img class=$ Temps discret et temps continu

Les considérations qui précèdent restent valables si les intervalles de temps deviennent illimitément petits. Cette remarque est spécifiquement intéressante dans le cas d'une équation différentielle. Si elle est du premier ordre, la mise en différences finies fait apparaître un mécanisme markovien. Pour les ordres supérieurs et les dispositifs différentiels, la décomposition en équations du premier ordre conduit à un dispositif markovien à plusieurs dimensions.

Propriétés des processus de Markov à temps discret

Un processus de Markov est caractérisé par la distribution conditionnelle :

$P(X_{n+1}\mid X_n)\,$

qui est aussi nommée probabilité de transition d'un pas du processus. La probabilité de transition pour deux, trois pas ou plus se déduit de la probabilité de transition d'un pas, et de la propriété de Markov :

$P(X_{n+2}\mid X_n) = \int P(X_{n+2},X_{n+1}\mid X_n)\,\mathrm dX_{n+1} = \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1}$

De même,

$P(X_{n+3}\mid X_n) = \int P(X_{n+3}\mid X_{n+2}) \int P(X_{n+2}\mid X_{n+1}) \, P(X_{n+1}\mid X_n) \, \mathrm dX_{n+1} \, \mathrm dX_{n+2}$

Ces formules se généralisent à un futur arbitrairement lointain $n + k$ en multipliant les probabilités de transition et en intégrant $k - 1$ fois.

La loi de distribution marginale $P (X n)$ est la loi de distribution des états au temps $n$ . La distribution d'origine est $P (X 0)$ . L'évolution du processus après un pas est décrite par :

$P(X_{n+1}) = \int P(X_{n+1}\mid X_n)\,P(X_n)\,\mathrm dX_n$

Ceci est une version de l'équation de Frobenius-Perron. Il peut exister une ou plusieurs distributions d'états $π$ telles que :

$\pi(X) = \int P(X\mid Y)\,\pi(Y)\,\mathrm dY$

où $Y$ est un nom arbitraire pour la variable d'intégration. Une telle distribution $π$ est nommée une distribution stationnaire. Une distribution stationnaire est une fonction propre de la loi de distribution conditionnelle, associée à la valeur propre 1.

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

Lorsque l'espace des états d'une chaîne de Markov n'est pas irréductible, il peut être partitionné en un ensemble de classes communicantes irréductibles. Le problème de la classification a son importance dans l'étude mathématique des chaînes de Markov et des processus stochastiques.

Si une chaîne de Markov possède au moins un état récurrent positif, alors il existe une distribution stationnaire.

Si une chaîne de Markov est récurrente positive et irréductible, alors :

il existe une unique distribution stationnaire ;
et le processus construit en prenant la distribution stationnaire comme distribution d'origine est ergodique.

Donc, la moyenne d'une fonction $f$ sur les instances de la chaîne de Markov est égale à sa moyenne selon sa distribution stationnaire :

$\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} f(X_k) = \int f(X)\,\pi(X)\,\mathrm dX$

C'est vrai surtout quand $f$ est la fonction identité.

La moyenne de la valeur des instances est par conséquent, sur le long terme, égale à l'espérance de la distribution stationnaire.

De plus, cette équivalence sur les moyennes s'applique aussi si $f$ est la fonction indicatrice d'un sous-ensemble $A$ de l'espace des états :

$\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}ˆ{n-1} \chi_A(X_k) = \int_A \pi(X)\,\mathrm dX = \mu_{\pi}(A)$

où $μ π$ est la mesure induite par $π$ .

Cela permet d'approximer la distribution stationnaire par un histogramme d'une séquence spécifique.

Si l'espace des états est fini, alors la distribution de probabilité peut être représentée par une matrice stochastique nommée matrice de transition, dont le $(i, j)$ ^ème élément vaut :

$P(X_{n+1}=j\mid X_n=i) \,$

Applications

Les dispositifs Markoviens sont particulièrement présents en physique spécifiquement en physique statistique. Ils interviennent surtout à travers l'équation de Fokker-Planck. D'une façon plus générale l'hypothèse markovienne est fréquemment invoquée quand des probabilités sont utilisées pour modéliser l'état d'un dispositif, en supposant cependant que l'état futur du dispositif peut être déduit du passé avec un historique assez faible.

Le célèbre article de 1948 de Claude Shannon, A mathematical theory of communication, qui fonde la théorie de l'information, débute en introduisant la notion d'entropie à partir d'une modélisation Markovienne de la langue anglaise. Il montre ainsi le degré de prédictibilité de la langue anglaise, pourvu d'un simple modèle d'ordre 1. Quoique simples, de tels modèles permettent de bien représenter les propriétés statistiques des dispositifs et de réaliser des prédictions efficaces sans décrire totalement la structure complète des dispositifs.

En compression, la modélisation markovienne permet la réalisation de techniques de codage entropique particulièrement efficaces, comme le codage arithmétique. De très nombreux algorithmes en reconnaissance des formes ou en intelligence artificielle comme par exemple l'algorithme de Viterbi, utilisé dans la grande majorité des dispositifs de téléphonie mobile pour la correction d'erreurs, font l'hypothèse d'un processus markovien sous-jacent.

L'indice de popularité d'une page Web (PageRank) tel qu'il est utilisé par Google est défini par une chaîne de Markov. Il est défini par la probabilité d'être dans cette page à partir d'un état quelconque de la chaine de Markov représentant le Web. Si $N$ est le nombre de pages Web connues, et une page $i$ a $k i$ liens, alors sa probabilité de transition vers une page liée (vers laquelle elle pointe) est $p_iˆl= \tfrac{1-q}{k_i}+\tfrac qN$ et $p_iˆ{nl}=\tfrac qN$ pour l'ensemble des autres (pages non liées). Notons qu'on a bien $k_i p_iˆl+(N-k_i) p_iˆ{nl}=1$ . Le paramètre $q$ vaut à peu près 0, 15.

Les chaînes de Markov sont un outil essentiel pour modéliser les processus en théorie des files d'attente et en statistiques.

Les chaînes de Markov sont aussi utilisées en bioinformatique pour modéliser les relations entre symboles successifs d'une même séquence (de nucléotides par exemple), en allant au delà du modèle polynomial. Les modèles markoviens cachés ont aussi diverses utilisations, telles que la segmentation (définition de frontières de régions au sein de séquences de gènes ou de protéines dont les propriétés chimiques fluctuent), l'alignement multiple, la prédiction de fonction, ou la découverte de gènes (les modèles markoviens cachés sont plus «flexibles» que les définitions strictes de type codon start + multiples codons + codons stop et ils sont par conséquent plus adaptés pour les eucaryotes (à cause de la présence d'introns dans le génome de ceux-ci) ou pour la découverte de pseudo-gènes).

Voir aussi

Chaîne de Markov
Matrice d'adjacence
Problème de décision de Markov (MDP)
Problème de décision de Markov partiellement observable (POMDP)
Marche aléatoire
Mouvement brownien
Modèle des urnes d'Ehrenfest
Modèle de Markov caché
Processus de Markov à temps continu

Liens externes

Recherche sur Google Images :

"d'une chaîne de Markov"
L'image ci-contre est extraite du site fr.wikipedia.org

Il est possible que cette image soit réduite par rapport à l'originale. Elle est peut-être protégée par des droits d'auteur.

Voir l'image en taille réelle (360 x 356 - 53 ko - png)

Refaire la recherche sur Google Images

Recherche sur Amazone (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/Processus_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.