Chaîne de Markov

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En mathématiques, une chaîne de Markov est un processus stochastique possédant la propriété markovienne. Dans un tel processus, la prédiction du futur à partir du présent ne nécessite pas la connaissance du passé. Elles ont pris le nom de leur découvreur, Andrei Markov.

Une chaîne de Markov en temps discret est une séquence X₁, X₂, X₃, ... de variables aléatoires. L'ensemble de leurs valeurs possibles est appelé l’espace d'états, la valeur X_n étant l'état du processus au moment n.

Si la distribution de probabilité conditionnelle de X_n+1 sur les états passés est une fonction de X_n seul, alors :

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

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

Andrei 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 chaînes 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 XXe siècle.

Sommaire

1 Propriétés des Chaînes de Markov
2 Chaînes de Markov à espace d'états discret
- 2.1 Classification des états
3 Notation
4 Exemple: Doudou le hamster
5 Applications
6 Articles connexes
7 Bibliographie
8 Liens externes

[modifier] Propriétés des Chaînes de Markov

Une chaîne de Markov est caractérisée par la distribution conditionnelle

$P(X_{n+1}| 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}|X_n) = \int P(X_{n+2},X_{n+1}|X_n)\,dX_{n+1} = \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1}$

De même,

$P(X_{n+3}|X_n) = \int P(X_{n+3}|X_{n+2}) \int P(X_{n+2}|X_{n+1}) \, P(X_{n+1}|X_n) \, dX_{n+1} \, 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 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}|X_n)\,P(X_n)\,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|Y)\,\pi(Y)\,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.

Certaines propriétés du processus déterminent s'il existe ou non une distribution stationnaire, et si elle est unique ou non.

Irréductible : tout état est accessible à partir de n'importe quel autre état.
Récurrent : pour chaque état, l'espérance de la durée avant le retour sur cet état est finie.

Quand l'espace des états d'une Chaîne de Markov n'est pas irréductible, il peut être partionné 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 est récurrente, alors il existe une distribution stationnaire.

Si une chaîne de Markov est récurrente 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)\,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)\,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.

[modifier] Chaînes de Markov à espace d'états discret

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) \,$

Si l'espace des états est fini, alors les intégrales pour les probabilités de transition pour k pas deviennent des sommes, qui peuvent être calculées en élevant la matrice de transition à la puissance k. Si P est la matrice de transition pour 1 pas, alors P^k est la matrice de transition pour k pas.

P étant la matrice de transition, une distribution stationnaire est un vecteur $π *$ qui vérifie l'équation

π * P = π *

Dans ce cas, la distribution stationnaire $π *$ est un vecteur propre de la matrice de transition, associé à la valeur propre 1.

Si la matrice de transition P est irréductible et apériodique, alors P^k converge vers une matrice dont chaque ligne est l'unique distribution stationnaire $π *$ , avec

$\lim_{k\rightarrow\infty}\pi P^k=\pi^*$ ,

indépendamment de la distribution initiale $π$ . Cela se prouve par le théorème de Perron-Frobenius.

Une matrice de transition dont tous les éléments sont strictement positifs est irréductible et apériodique.

[modifier] Classification des états

On dit que i et j communiquent si et seulement s'il existe $n 1$ et $n 2$ tel que $P(X_{n_1}=i|X_0=j) >0$ et $P(X_{n_2}=j|X_0=i) >0$ . C'est une relation d'équivalence. On appelle classe, toute classe pour cette relation.

Une classe est dite finale, si elle ne conduit à aucune autre, sinon, elle est dite transitoire.

Soit $N i j = {n / P (X n = j | X 0 = i) > 0}$ . La période d'une classe est définie par $p g c d (N i i)$ (la valeur est la même quel que soit i à l'intérieur d'une même classe). Si la période vaut 1, la classe est dite apériodique.

[modifier] Notation

Dans les formules qui précèdent, l'élément (i, j) est la probabilité de la transition de i à j. La somme des éléments d'une ligne vaut toujours 1 et la distribution stationnaire est donnée par le vecteur propre gauche de la matrice de transition.

On rencontre parfois des matrices de transition dans lesquelles le terme (i , j) est la probabilité de transition de j vers i, auquel cas la matrice de transition est simplement la transposée de celle décrite ici. La somme des éléments d'une colonne vaut alors 1. De plus, la distribution stationnaire du système est alors donnée par le vecteur propre droit de la matrice de transition, au lieu du vecteur propre gauche.

[modifier] Exemple: Doudou le hamster

Doudou le hamster paresseux ne connaît que 3 endroits dans sa cage: les copeaux où il dort, la mangeoire où il mange et la roue où il fait de l'exercice. Ses journées sont assez semblables les unes aux autres, et son activité se représente aisément par une chaîne de Markov. Toutes les minutes, il peut soit changer d'activité, soit continuer celle qu'il était en train de faire. L'appellation processus sans mémoire n'est pas du tout exagérée pour parler de Doudou.

Quand il dort, il a 9 chances sur 10 de ne pas se réveiller la minute suivante.
Quand il se réveille, il y a 1 chance sur 2 qu'il aille manger et 1 chance sur 2 qu'il parte faire de l'exercice.
Le repas ne dure qu'une minute, après il fait autre chose.
Après avoir mangé, il y a 3 chances sur 10 qu'il parte courir dans sa roue, mais surtout 7 chances sur 10 qu'il retourne dormir.
Courir est fatigant; il a donc 80% de chance de retourner dormir au bout d'une minute. Sinon il continue en oubliant qu'il est déjà un peu fatigué.

[modifier] Diagrammes

Les diagrammes peuvent montrer toutes les flèches, chacune représentant une probabilité de transition. Cependant, c'est plus lisible si:

On ne dessine pas les flèches de probabilité zéro (transition impossible)
On ne dessine pas les boucles (flèche d'un état vers lui-même). Cependant elles existent; leur probabilité est sous-entendue car on sait que la somme des probabilités des flèches partant de chaque état doit être égale à 1.

[modifier] Matrice de transition

La matrice de transition de ce système est la suivante (les lignes et les colonnes correspondent dans l'ordre aux états dormir, manger, courir) :

P = $\begin{bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\ \end{bmatrix}$

[modifier] Prévisions

Prenons l'hypothèse que Doudou dort lors de la première minute de l'étude.

$\mathbf{x}^{(0)} = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}$

Au bout d'une minute, on peut prédire :

$\mathbf{x}^{(1)} = \mathbf{x}^{(0)} P = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\ \end{bmatrix} = \begin{bmatrix} 0.9 & 0.05 & 0.05 \end{bmatrix}$

Ainsi, après une minute, on a 90% de chances que Doudou dorme encore, 5% qu'il mange et 5% qu'il courre.

$\mathbf{x}^{(2)} = \mathbf{x}^{(1)} P = \mathbf{x}^{(0)} P^2 = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\ \end{bmatrix}^2 = \begin{bmatrix} 0.885 & 0.045 & 0.07 \end{bmatrix}$

Après 2 minutes, il y a 4,5% de chances que l'hamster mange.

De manière générale, pour n minutes

$\mathbf{x}^{(n)} = \mathbf{x}^{(n-1)} P$

$\mathbf{x}^{(n)} = \mathbf{x}^{(0)} P^n$

La théorie montre qu'au bout d'un certain temps, la loi de probabilité est indépendante de la loi initiale. Notons la q :

$\mathbf{q} = \lim_{n \to \infty} \mathbf{x}^{(n)}$

On obtient la convergence si et seulement si la chaîne est apériodique et irréductible. C'est le cas dans notre exemple, on peut donc écrire :

$\begin{matrix} P & = & \begin{bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\ \end{bmatrix} \\ \mathbf{q} P & = & \mathbf{q} & \mbox{(} \mathbf{q} \mbox{ est la loi invariante par rapport a } P \mbox{.)} \\ & = & \mathbf{q} I \\ \mathbf{q} (I - P) & = & \mathbf{0} \\ & = & \mathbf{q} \left( \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} - \begin{bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\ \end{bmatrix} \right) \\ & = & \mathbf{q} \begin{bmatrix} 0.1 & -0.05 & -0.05 \\ -0.7 & 1 & -0.3 \\ -0.8 & 0 & 0.8 \\ \end{bmatrix} \end{matrix}$

$\begin{bmatrix} q_1 & q_2 & q_3 \end{bmatrix} \begin{bmatrix} 0.1 & -0.05 & -0.05 \\ -0.7 & 1 & -0.3 \\ -0.8 & 0 & 0.8 \\ \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 \end{bmatrix}$

Sachant que $q 1 + q 2 + q 3 = 1$ , on obtient :

$\begin{bmatrix} q_1 & q_2 & q_3 \end{bmatrix} = \begin{bmatrix} 0.884 & 0.0442 & 0.0718 \end{bmatrix}$

Doudou passe 88,4 % de son temps à dormir !

[modifier] Applications

Les systèmes Markoviens sont très présents en Physique particulièrement en Physique statistique. 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 papier 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édictabilité 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 chaine 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= \frac{1-q}{k_i}+\frac{q}{N}$ et $p_i^{nl}=\frac{q}{N}$ 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.