Expliquées visuellement
Par Victor Powell
avec un texte de Lewis Lehe
Les chaînes de Markov, nommées d’après Andrey Markov, sont des systèmes mathématiques qui sautent d’un « état » (une situation ou un ensemble de valeurs) à un autre. Par exemple, si vous faites un modèle de chaîne de Markov du comportement d’un bébé, vous pourriez inclure » jouer « , » manger « , » dormir » et » pleurer » comme états, qui, avec d’autres comportements, pourraient former un » espace d’états » : une liste de tous les états possibles. En outre, en plus de l’espace d’état, une chaîne de Markov vous indique la probabilité de sauter, ou de « transitionner », d’un état à un autre, par ex, la probabilité qu’un bébé en train de jouer s’endorme dans les cinq prochaines minutes sans pleurer d’abord.
Une chaîne de Markov simple, à deux états, est illustrée ci-dessous.
vitesse
Avec deux états (A et B) dans notre espace d’état, il y a 4 transitions possibles (et non 2, parce qu’un état peut se retransformer en lui-même). Si nous sommes à ‘A’, nous pouvons faire une transition vers ‘B’ ou rester à ‘A’. Si nous sommes en ‘B’, nous pouvons passer en ‘A’ ou rester en ‘B’. Dans ce diagramme à deux états, la probabilité de transition de tout état vers tout autre état est de 0,5.
Bien sûr, les vrais modélisateurs ne dessinent pas toujours des diagrammes de chaînes de Markov. Ils utilisent plutôt une « matrice de transition » pour comptabiliser les probabilités de transition. Chaque état de l’espace d’état est inclus une fois en tant que ligne et une autre fois en tant que colonne, et chaque cellule de la matrice vous indique la probabilité de transition de l’état de sa ligne à l’état de sa colonne. Ainsi, dans la matrice, les cellules font le même travail que les flèches dans le diagramme.
A B
Si l’espace d’état ajoute un état, nous ajoutons une ligne et une colonne, en ajoutant une cellule à chaque colonne et ligne existante. Cela signifie que le nombre de cellules croît de manière quadratique lorsque nous ajoutons des états à notre chaîne de Markov. Ainsi, une matrice de transition s’avère assez rapidement utile, à moins que vous ne souhaitiez dessiner un diagramme de chaîne de Markov de type jungle gym.
Une utilisation des chaînes de Markov consiste à inclure des phénomènes du monde réel dans des simulations informatiques. Par exemple, on peut vouloir vérifier la fréquence de débordement d’un nouveau barrage, qui dépend du nombre de jours de pluie consécutifs. Pour construire ce modèle, nous partons du schéma suivant de jours pluvieux (R) et ensoleillés (S) :
Une façon de simuler ce temps serait de dire simplement « La moitié des jours sont pluvieux. Par conséquent, chaque jour de notre simulation aura cinquante pour cent de chances de pluie. » Cette règle générerait la séquence suivante dans la simulation :
Avez-vous remarqué comment la séquence ci-dessus ne ressemble pas tout à fait à l’originale ? La deuxième séquence semble sauter dans tous les sens, alors que la première (les données réelles) semble avoir une certaine « viscosité ». Dans les données réelles, s’il y a du soleil (S) un jour, alors le jour suivant est aussi beaucoup plus susceptible d’être ensoleillé.
Nous pouvons minifier cette « stickyness » avec une chaîne de Markov à deux états. Lorsque la chaîne de Markov est dans l’état « R », elle a une probabilité de 0,9 de rester sur place et une chance de 0,1 de partir pour l’état « S ». De même, l’état « S » a 0,9 probabilité de rester sur place et 0,1 chance de passer à l’état « R ».
Dans les mains des météréologues, des écologistes, des informaticiens, des ingénieurs financiers et d’autres personnes qui ont besoin de modéliser de grands phénomènes, les chaînes de Markov peuvent devenir assez grandes et puissantes. Par exemple, l’algorithme utilisé par Google pour déterminer l’ordre des résultats de recherche, appelé PageRank, est un type de chaîne de Markov.
Ci-avant, nous avons inclus un « terrain de jeu » de chaîne de Markov, où vous pouvez créer vos propres chaînes de Markov en jouant avec une matrice de transition. En voici quelques-unes à titre d’exemple : ex1, ex2, ex3 ou générez-en une au hasard. Le texte de la matrice de transition deviendra rouge si la matrice fournie n’est pas une matrice de transition valide. Le total des lignes de la matrice de transition doit être égal à 1. Il doit également y avoir le même nombre de lignes que de colonnes.
Vous pouvez également accéder à une version plein écran sur setosa.io/markov
.