Chaîne de Markov

Infos
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 X1, X2, X3, ... de variables aléatoires. L'ensemble de leurs valeurs possibles est appelé l’espace d'états, la
Chaîne de Markov

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 X1, X2, X3, ... de variables aléatoires. L'ensemble de leurs valeurs possibles est appelé l’espace d'états, la valeur Xn étant l'état du processus au moment n. Si la distribution de probabilité conditionnelle de Xn+1 sur les états passés est une fonction de Xn seul, alors : : P(X_=x|X_0, X_1, X_2, \ldots, X_n) = P(X_=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.

Propriétés des Chaînes de Markov

Une chaîne de Markov est caractérisée par la distribution conditionnelle : P(X_| 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_|X_n) = \int P(X_, X_|X_n)\, dX_ = \int P(X_|X_) \, P(X_|X_n) \, dX_ De même, : P(X_|X_n) = \int P(X_|X_) \int P(X_|X_) \, P(X_|X_n) \, dX_ \, dX_ 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(Xn) est la loi de distribution des états au temps n. La distribution initiale est P(X0). L'évolution du processus après un pas est décrite par : P(X_) = \int P(X_|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 positif : 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 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 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 \; \sum_^ 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 \; \sum_^ \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.

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_=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 Pk est la matrice de transition pour k pas. P étant la matrice de transition, une distribution stationnaire est un vecteur \pi^
- qui vérifie l'équation : \pi^
- P= \pi^
-. Dans ce cas, la distribution stationnaire \pi^
- 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 Pk converge vers une matrice dont chaque ligne est l'unique distribution stationnaire \pi^
-, avec :\lim_k\rightarrow\infty\pi P^k=\pi^
-, indépendamment de la distribution initiale \pi. 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.

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_=i|X_0=j) >0 et P(X_=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_ = \n/P(X_n=j|X_0=i)>0\. La période d'une classe est définie par pgcd(N_) (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.

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.

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

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.

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 0, 9 & 0, 05 & 0, 05 \\ 0, 7 & 0 & 0, 3 \\ 0, 8 & 0 & 0, 2 \\ \end

Prévisions

Prenons l'hypothèse que Doudou dort lors de la première minute de l'étude. : \mathbf^ = \begin 1 & 0 & 0 \end Au bout d'une minute, on peut prédire : : \mathbf^ = \mathbf^ P = \begin 1 & 0 & 0 \end \begin 0, 9 & 0, 05 & 0, 05 \\ 0, 7 & 0 & 0, 3 \\ 0, 8 & 0 & 0, 2 \\ \end = \begin 0.9 & 0.05 & 0.05 \end Ainsi, après une minute, on a 90 % de chances que Doudou dorme encore, 5 % qu'il mange et 5 % qu'il coure. : \mathbf^ = \mathbf^ P = \mathbf^ P^2 = \begin 1 & 0 & 0 \end \begin 0, 9 & 0, 05 & 0, 05 \\ 0, 7 & 0 & 0, 3 \\ 0, 8 & 0 & 0, 2 \\ \end^2 = \begin 0.885 & 0.045 & 0.07 \end Après 2 minutes, il y a 4, 5 % de chances que le hamster mange. De manière générale, pour n minutes : \mathbf^ = \mathbf^ P : \mathbf^ = \mathbf^ 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 = \lim_n \to \infty \mathbf^ 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 P & = & \begin 0, 9 & 0, 05 & 0, 05 \\ 0, 7 & 0 & 0, 3 \\ 0, 8 & 0 & 0, 2 \\ \end \\ \mathbf P & = & \mathbf & \mbox \mathbf \mbox P \mbox \\ & = & \mathbf I \\ \mathbf (I - P) & = & \mathbf \\ & = & \mathbf \left( \begin 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end - \begin 0, 9 & 0, 05 & 0, 05 \\ 0, 7 & 0 & 0, 3 \\ 0, 8 & 0 & 0, 2 \\ \end \right) \\ & = & \mathbf \begin 0.1 & -0.05 & -0.05 \\ -0.7 & 1 & -0.3 \\ -0.8 & 0 & 0.8 \\ \end \end \begin q_1 & q_2 & q_3 \end \begin 0.1 & -0.05 & -0.05 \\ -0.7 & 1 & -0.3 \\ -0.8 & 0 & 0.8 \\ \end = \begin 0 & 0 & 0 \end Sachant que q_1 + q_2 + q_3 = 1, on obtient : :\begin q_1 & q_2 & q_3 \end = \begin 0.884 & 0.0442 & 0.0718 \end Doudou passe 88, 4 % de son temps à dormir !

Illustration de l'impact du modèle

L'exemple qui suit a pour but de montrer l'importance de la modélisation du système. Une bonne modélisation permet de répondre à des questions complexes avec des calculs simples. On étudie une civilisation (fictive) constituée de plusieurs classes sociales, et dans laquelle les individus peuvent passer d'une classe à l'autre. Chaque étape représentera un an. On considérera une lignée plutôt qu'un individu, pour éviter d'obtenir des citoyens bicentenaires. Les différents statuts sociaux sont au nombre de 4 :
- Esclave
- Libre
- Citoyen
- Haut-fonctionnaire Dans cette société : Les esclaves peuvent rester esclaves ou bien devenir des hommes libres (en achetant leur liberté ou en étant affranchis généreusement par leur maître). Les hommes libres peuvent rester libres ou bien vendre leur liberté (pour payer leurs dettes, etc.) ou encore devenir citoyens (là encore par mérite ou en achetant le titre de citoyen). Les citoyens sont citoyens à vie et transmettent leur citoyenneté à leur lignée (On pourrait croire que le nombre de citoyens tend à augmenter et qu'au bout d'un certain temps, tous sont citoyens mais historiquement, dans les civilisations qui suivaient ce schéma, les citoyens sont décimés par les guerres et de nouveaux esclaves arrivent régulièrement de l'étranger).Ils peuvent aussi se porter candidats lors des élections annuelles afin de devenir hauts-fonctionnaires (magistrats). Au terme de leur mandat, ils peuvent être réélus ou redevenir de simples citoyens. Pour compliquer un peu l'exemple et montrer ainsi l'étendue des applications des chaînes de Markov, nous considérerons que les fonctionnaires sont élus pour plusieurs années. Par conséquent, l'avenir d'un individu fonctionnaire dépend du temps depuis lequel il est fonctionnaire. Nous sommes donc dans le cas d'une chaîne de Markov non homogène. Heureusement, nous pouvons aisément nous ramener à une chaîne homogène. En effet, il suffit de rajouter un état artificiel pour chaque année du mandat. Au lieu d'avoir un état 4 : Fonctionnaire , nous aurons un état
- 4 : Fonctionnaire en début de mandat
- 5 : Fonctionnaire en seconde année de mandat
- etc. Les probabilités reliant deux états artificiels consécutifs (troisième et quatrième année par exemple) sont de valeur 1 car on considère que tout mandat commencé se termine (On pourrait modéliser le contraire en changeant la valeur de ces probabilités). fixons la durée des mandats à deux ans, le contingent des fonctionnaires étant renouvelable par moitié chaque année. On a alors le graphe suivant : Image:graphe2.jpeg|graphe Pour modéliser des élections qui ne seraient pas annuelles, il faudrait de même ajouter des états fictifs (année d'élection, un an depuis la dernière élection, etc). La matrice P s'écrit alors : \mathbf= \left( \begin \frac & \frac & 0 & 0 & 0 \\ \frac & \frac & \frac & 0 & 0 \\ 0 & 0 & \frac & \frac & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & \frac & \frac & 0 \end \right) Comme cela est expliqué plus haut, P^ donne les probabilités de transition en n étapes. Donc p^_ est la probabilité d'être dans l'état j au bout de n années pour une lignée partie de la classe sociale i. Pour savoir ce que devient un esclave au bout de n ans, il suffit donc d'écrire : (1 \ , \ 0 \ , \ 0 \ , \ 0 \ , \ 0 \ ) \times \big( P^ \big) = \left( \begin p_1^ \\ p_2^ \\ p_3^ \\ p_4^ \\ p_5^ \end \right) Où p_i^= probabilité d'être dans la classe sociale i au bout de n années sachant que la lignée étudiée est partie de l'état d'esclave. Si on connaît les effectifs de chaque classe sociale à l'an 0, il suffit alors de calculer : (1/nb de lignées) x (nb d'esclaves , nb de libres , nb de citoyens , nb d'élus1 , nb d'élus2 ) x P^ = Y On obtient ainsi la répartition de la population dans les différentes classes sociales (au bout de n années). Y x 100 = (... , ... , ... , ... , ... ) = répartition de la population en % En multipliant ce vecteur Y par l'effectif total de la population au lieu de le multiplier par 100, on obtient les effectifs de chaque classe au bout de n années. Posons-nous maintenant la question suivante : Au bout de n années, combien de lignées auront déjà eu un haut fonctionnaire ayant terminé son mandat? La réponse est différente du nombre de mandats effectués en n années car il y a possibilité d'être réélu. Répondre à cette question semble difficile (encore faudrait-il que ce soit possible). En fait, il suffit de changer la modélisation du problème. Passons donc à une nouvelle modélisation pour répondre à cette question. (Par contre, elle ne permet pas de répondre aux questions précédentes d'où la présentation des 2 modèles). Il suffit de modifier ainsi le graphe : Image:graphe4.JPG|graphe modifié On ajoute un sommet absorbant car une fois q'une lignée a fini un mandat, on ne tient plus compte d'elle. Si certains lecteurs font preuve d'esprit critique, ils diront peut-être que le modèle est faux car les lignées comportant un élu ne participent plus aux élections. Il n'en est rien. En effet, le nombre d'élus est proportionnel au nombre de citoyens. Ne pas réinjecter les anciens hauts-fonctionnaires parmi les candidats ne change donc en rien la probabilité pour un citoyen d'être élu car, la population des citoyens étant plus restreinte, le nombre de postes offerts l'est aussi. Ce modèle permet de répondre avec exactitude à la question posée. On a donc une nouvelle matrice de transition : \mathbf= \left( \begin \frac & \frac & 0 & 0 & 0 & 0 \\ \frac & \frac & \frac & 0 & 0 & 0 \\ 0 & 0 & \frac & \frac & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end \right) En faisant les mêmes calculs qu'aux questions précédentes on obtient en dernière ligne du vecteur solution le pourcentage de lignées ayant accompli au moins un mandat ou bien l'effectif (si on multiplie par l'effectif total de la population). Autrement dit, remodéliser le problème permet de répondre à la question qui semblait si compliquée par un simple calcul de puissances d'une matrice.

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 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é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 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 ki liens, alors sa probabilité de transition vers une page liée (vers laquelle elle pointe) est p_i^l= \frac+\frac et p_i^=\frac pour toutes les autres (pages non liées). Notons qu'on a bien k_i p_i^l+(N-k_i) p_i^=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.

Voir aussi

- 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é
- Chaîne de Markov à temps continu
- Chaîne de Markov à états infinis ==
Sujets connexes
Algorithme de Viterbi   Andrei Markov (mathématicien)   Claude Shannon   Codage arithmétique   Compression de données   Entropie de Shannon   Fonction propre   Google   Graphe   Histogramme   Hypothèse ergodique   Intelligence artificielle   Mathématiques   Matrice (mathématiques)   Matrice d'adjacence   Matrice stochastique   Modèle de Markov caché   Modèle des urnes d'Ehrenfest   Mouvement brownien   PageRank   Partition (mathématiques)   Physique   Physique statistique   Processus de décision markovien   Processus de décision markovien partiellement observable   Processus stochastique   Propriété markovienne   Relation d'équivalence   Statistiques   Théorie de l'information   Théorie des files d'attente   Théorème de Perron-Frobenius   Valeur propre (synthèse)   Variable aléatoire  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^