TP5

Introduction

La classe Markov.java permet de représenter une chaîne de Markov comme une matrice de flottants (double). Elle dispose de deux fonctions:

• Markov(size, U) qui permet de créer une chaîne de Markov à partir d'une matrice de flottants
• display qui affiche la chaîne de Markov (comme une matrice)

Les fichiers sont disponibles ici.

Ce qu'il faut écrire

1. Une fonction stochastic qui teste si la matrice est bien la matrice d'une chaîne de Markov (tous les coefficients entre 0 et 1, la somme de chaque ligne fait 1). Attention, comme il pourrait y avoir des erreurs d'arrondis, tester uniquement si la somme de chaque ligne est plus grande que 0.99.
2. Une fonction P(i,j,n) qui calcule la probabilité qu'on puisse aller de i à j en n étapes. (Ecrire la fonction récursivement).
3. Un constructeur Markov(n) qui crée une chaîne de Markov à n états correspondant à une marche aléatoire (quand on est en i, on a une chance sur deux d'aller en i-1, une chance sur deux d'aller en i+1. Quand on est en 0, on est certain d'aller en 1. De même quand on est en n-1, on est certain d'aller en n-2).
4. Une fonction irreductible qui teste si la chaîne de Markov est irréductible
5. Une fonction station qui calcule la distribution stationnaire en itérant la chaîne de Markov jusque convergence (attendre que tous les coefficients soient à peu près stabilisés). Il sera nécessaire pour cela d'écrire une fonction qui multiplie deux matrices.

Noter que tester l'apériodicité est plus compliqué. Les étudiants motivés et forts en anglais peuvent aller lire le document suivant.

L'algorithme de Propp-Wilson

Cet algorithme permet de tirer au hasard un état selon la distribution stationnaire sans avoir à la calculer. C'est un algorithme exact, contrairement à la fonction station que vous avez écrit avant. L'algorithme fonctionne comme suit.

• On initialise un tableau S avec S[i] = i.
• On fait évoluer S à chaque étape de la façon suivante:
  • On recopie S dans S'
  • Pour chaque état i, on choisit un successeur j tiré selon la loi de la chaîne de Markov. On pose alors S[i] = S'[j].
• L'algorithme s'arrête lorsque S est constant, c'est à dire lorsque S[i] = S[i'] = s pour tout i,i'. On renvoie alors s

1. Ecrire int ProppWilson() qui renvoie un état choisi selon la distribution stationnaire, en utilisant l'algorithme de Propp-Wilson
2. Vérifier que vos algorithmes sont corrects en comparant la sortie de station et de ProppWilson (exécuter 1000 fois Propp-Wilson, et regarder combien de fois chaque état a été tiré). Faites bien attention de partir d'une chaîne de Markov irréductible apériodique.