À propos de cette expérience
Une chaîne de Markov passe aléatoirement d’un état à l’autre, mais la probabilité de chaque transition dépend uniquement de son état actuel, et non de la façon dont elle y est arrivée. Le temps de demain dépend de celui d’aujourd’hui, la prochaine page consultée par un internaute dépend de la page actuelle, et la prochaine forme d’une molécule dépend de sa forme présente. Quel que soit son point de départ, une chaîne bien comportée oublie son origine et converge vers un état stationnaire π. Modifiez les probabilités de transition, lancez la chaîne et observez la convergence vers π des fréquences à long terme comme de la distribution pₙ.
Objectifs pédagogiques
- Écrivez la matrice de transition d’une chaîne de Markov et vérifiez que la somme des éléments de chaque ligne vaut 1
- Calculez la distribution après n étapes sous la forme p₀Pⁿ
- Trouvez la distribution stationnaire en résolvant πP = π
- Reliez la vitesse de convergence à la deuxième plus grande valeur propre de P
- Reconnaissez les chaînes qui ne convergent pas, comme les chaînes périodiques
Comment l’utiliser
- 1Dans la chaîne météo, appuyez sur « Exécuter » et observez le jeton. Appuyez ensuite sur « 1000 étapes ». À quelle distance les barres se trouvent-elles des lignes pointillées ?
- 2Modifiez l’état initial. L’état stationnaire change-t-il ? La partie initiale du graphique supérieur change-t-elle ?
- 3Vérifiez l’état stationnaire à la main : multipliez π par la matrice et montrez que vous obtenez à nouveau π.
- 4Choisissez « Mélange lent ». De combien d’étapes le graphique supérieur a-t-il besoin pour se stabiliser ? Comparez avec |λ₂| et la valeur affichée.
- 5Choisissez « Cycle périodique ». Pourquoi le graphique supérieur ne se stabilise-t-il jamais, alors que la proportion du temps passé dans chaque état, elle, se stabilise ?
- 6Choisissez « Oublie immédiatement ». Pourquoi la distribution atteint-elle π après une seule étape ?
Le modèle
Hypothèses
- Trois états et des probabilités de transition homogènes dans le temps. Chaque ligne se modifie à l’aide de deux curseurs ; la probabilité de rester dans le même état est le reste.
- Le chemin échantillonné provient d’un générateur aléatoire initialisé avec une graine ; le même numéro d’exécution donne donc toujours le même chemin. « Nouvelle exécution » change la graine.
- L’état stationnaire est obtenu en résolvant exactement les équations linéaires. Le nombre d’étapes nécessaires pour s’approcher à 1 % près est estimé par ln 100 / (-ln |λ₂|).
À essayer en classe
- Q1Pour P = [[0.9, 0.1], [0.5, 0.5]], trouvez la distribution stationnaire.
- Q2Montrez que la distribution uniforme est stationnaire dès lors que chaque colonne de P a également une somme égale à 1.
- Q3Une chaîne a |λ₂| = 0.95. De combien d’étapes a-t-elle besoin environ pour oublier son état initial ?
- Q4Expliquez pourquoi la chaîne à cycle périodique possède une distribution stationnaire, mais que pₙ ne converge pas vers celle-ci.
- Q5Le PageRank original de Google est la distribution stationnaire d’un internaute aléatoire. Pourquoi a-t-il ajouté une faible probabilité de sauter vers n’importe quelle page ?
Foire aux questions
Que signifie ici « sans mémoire » ?
Le futur dépend du passé uniquement par l’intermédiaire de l’état présent. Si vous savez qu’il pleut aujourd’hui, savoir qu’il faisait beau la semaine dernière ne vous apprend rien de plus sur demain.
Toute chaîne a-t-elle un état stationnaire ?
Toute chaîne finie possède au moins une distribution stationnaire. Celle-ci est unique si chaque état est accessible depuis tous les autres, et pₙ converge vers cette distribution quel que soit l’état de départ si, de plus, la chaîne n’est pas périodique.
Où utilise-t-on les chaînes de Markov ?
Dans les modèles de files d’attente et de fiabilité, en génétique, en reconnaissance vocale, en prédiction de texte et en finance, ainsi que dans la méthode de Monte-Carlo par chaînes de Markov, qui construit une chaîne dont la distribution stationnaire est celle à partir de laquelle on souhaite tirer des échantillons.