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é. Les processus de Markov portent le nom de leur découvreur, Andreï Markov.

Un processus de Markov en temps discret est une séquence $\scriptstyle\ X_1,$ $\scriptstyle\ X_2,$ $\scriptstyle\ X_3,\ \dots$ de variables aléatoires. L'ensemble de leurs valeurs possibles est appelé l’espace d'états, la valeur $\scriptstyle\ X_n\$ étant l'état du processus à l'instant $\scriptstyle\ n.$ Selon les auteurs, le vocable « chaîne de Markov » désigne les processus de Markov à temps discret ou uniquement les processus de Markov à temps discret et à 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 $\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, 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 infini dénombrable a été donnée par Kolmogorov en 1936.

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

Types de processus de Markov

Espace d'états discret

Lorsque les variables aléatoires successives sont des variables discrètes munies 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 généralement 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 système ne dépend que de son état précédent à travers une probabilité conditionnelle appelée probabilité de transition s'exprime par :

$P(x_n,t_n|x_{n-1},t_{n-1};x_{n-2},t_{n-2};...;x_1,t_1;x_0,t_0) = P(x_n,t_n|x_{n-1},t_{n-1}) \quad t_n>t_{n-1}>...>t_1>t_0\,$.

Une chaîne de Markov est entièrement définie par la probabilité au premier ordre $P(x,t)\,$ et la probabilité de transition. On obtient par exemple la probabilité au second ordre par :

$P(x_1,t_1;x_2,t_2) = P(x_1,t_1) P(x_2,t_2|x_1,t_1) \quad t_2>t_1\,$.

Elle est donc également définie par la probabilité au second ordre. Enfin, elle peut être définie par l'état initial et la probabilité de transition.

Espace d'états continu

Les chaînes de Markov trouvent des applications dans les domaines les plus divers mais les processus considérés dans les problèmes dynamiques, en particulier en vibrations, portent généralement sur des variables aléatoires continues.

Dans ces conditions, la probabilité d'obtenir une valeur donnée est généralement 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 :

$p(x_n,t_n|x_{n-1},t_{n-1};x_{n-1},t_{n-1};...;x_1,t_1;x_0,t_0) = p(x_n,t_n|x_{n-1},t_{n-1}) \quad t_n>t_{n-1}>...>t_1>t_0\,$

Temps discret et temps continu

Les considérations qui précèdent restent valables si les intervalles de temps deviennent infiniment petits. Cette remarque est particulièrement 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 systèmes différentiels, la décomposition en équations du premier ordre conduit à un système 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 appelé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 initiale est P(X₀). 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 appelé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.

Quand 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 initiale 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 en particulier lorsque f est la fonction identité.

La moyenne de la valeur des instances est donc, 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 particulière.

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

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

Applications

• Les systèmes Markoviens sont très présents en physique particulièrement en physique statistique. Ils interviennent en particulier à travers l'équation de Fokker-Planck. Plus généralement l'hypothèse markovienne est souvent invoquée lorsque des probabilités sont utilisées pour modéliser l'état d'un système, en supposant toutefois que l'état futur du système 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, commence 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, muni d'un simple modèle d'ordre 1. Bien que simples, de tels modèles permettent de bien représenter les propriétés statistiques des systèmes et de réaliser des prédictions efficaces sans décrire complètement la structure complète des systèmes.
• En compression, la modélisation markovienne permet la réalisation de techniques de codage entropique très 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 systèmes 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 toutes les 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 environ 0,15.
• Les chaînes de Markov sont un outil fondamental pour modéliser les processus en théorie des files d'attente et en statistiques.
• Les chaînes de Markov sont également utilisées en bio-informatique 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 également 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 varient), 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 donc 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

Articles connexes

• 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 (en)

Liens externes

• (en) [PDF] Charles M. Grinstead et J. Laurie Snell, chap. « Markov Chains », dans Introduction to probability, AMS
• (en) Markov Marvellous Chain
• Exercices corrigés (wims de l'université de Nice Sophia Antipolis)