Sujet 2 : Comparaisons de méthodes pour calculer l’état stationnaire

Afin d’évaluer les performances des 3 méthodes, nous appliquerons chacunes de ces méthodes aux 3 figures différentes : lignes, anneau et sucette (ligne+anneau). Lors de la réalisation de ce DM, Antoine Delise, Maxime Chevalier, Raphaël Fustes ainsi que Antoine Blanc étaient présent dans la même salle que moi. Il serait donc normal d’entrevoir des similitudes entre nos travaux bien que nous avons éviter de faire des copier/coller sans reflexion.

Création des 3 matrices de transitions

On commence par définir 3 types de matrices. Pour la matrice Sucette, nous avons simplement décidé de considérer cette matrice comme la concaténation des deux autres.
On positionne sur la machine de transition les probabilités de passer d’un état à l’autre. Ces probabilités sont répartis uniformément entre les états d’arrivée et seront utilisés pour la première méthode.

library(ggplot2)
## Warning: package 'ggplot2' was built under R version 3.3.2
set.seed(1)

#Taille des matrices
#Le but étant de comparer les différentes formes, on ne s'intéressera pas à faire changer N plus tard
N <- 10

#Matrice de transition Ligne ML
ML=matrix(rep(0,N*N),nrow=N)
for(i in 2:N){
  ML[i,i-1] <- 1
  ML[i-1,i] <- 1
}
for(i in 1:N)
  ML[i,] <- ML[i,]/sum(ML[i,])

#Matrice de transition Anneau MA
MA=matrix(rep(0,N*N),nrow=N)
for(i in 2:N){
  MA[i,i-1] <- 1
  MA[i-1,i] <- 1
}
MA[1,N] <- 1
MA[N,1] <- 1
for(i in 1:N)
  MA[i,] <- MA[i,]/sum(MA[i,])

#Matrice de transition Sucette MS
MS=matrix(rep(0,N*N),nrow=N)
for(i in 2:N){
  MS[i,i-1] <- 1
  MS[i-1,i] <- 1
}
MS[1,(N+1)/2] <- 1
MS[(N+1)/2,1] <- 1
for(i in 1:N)
  MS[i,] <- MS[i,]/sum(MS[i,])

#Pour rendre plus agréable les futurs affichages lors des tests
options(digits=3);

#Graphe d'affichage utilisés par toutes les prochaines fonctions
Affichage <- function(liste,N){
  d <- rbind(data.frame(Etats=1:N,Taux=liste))
  ggplot(data=d, aes(x=Etats,y=Taux)) + geom_bar(stat="identity")
}

Marche aléatoire et statistiques sur la fréquence de passage dans chaque état

Dans un premier temps, on va s’intéresser au déplacement aléatoire entre les états des matrices. On utilise un tableau de taille N pour compter le nombre de passages dans chaque états. On divise le nombre de passages par état par la nombre total de changement d’état.

MarcheAlea <- function(M,N,nbI){
  #Nb de passages par états
  nb <- rep(0,N)
  #Determine aléatoirement l'état initial
  j <- sample(1:N,1)
  nb[j] <- nb[j] + 1
  for(i in 1:(nbI-1)){
    j <- sample(1:N,prob=M[j,],1)
    nb[j] <- nb[j]+1
  }
  nb <- nb/(nbI)
  Affichage(nb,N)
}

On applique cette fonction pour différentes itérations et pour chaque matrice, sur 4 cas d’itérations différents (1000,10000,100000,1000000 de gauche à droite).

Matrice ligne

Matrice anneau

Matrice sucette

Conclusion

Cette méthode est loin d’être satisfaisante, sur une matrice de taille 10 et quelle que soit sa forme, 1 million d’itérations est nécessaire pour obtenir un résultat acceptable, mais même dans ce cas, on remarque de légères variations entre les états lorsqu’on s’attend à avoir un taux égal.

Itérer la fonction de transition à partir d’un vecteur de probabilité arbitraire

Ici, on implémente le vecteur de probabilité par une matrice ligne, plus facile pour effectuer les multiplications avec les matrices de transitions. On initialise cette matrice selon 2 cas différent pour identifier leur impact (1/N,…,1/N) et (1,0,…,0).

ItereFct <- function(M,N,nbI,C){
  #Vecteur de proba arbitraire représenté par une matrice ligne
  if(C==1)
    V <- matrix(rep(1/N,N),ncol=N)
  else{
    V <- matrix(rep(0,N),ncol=N)
    V[1] <- 1/2
    V[N] <- 1/2
  }
  
  for(i in 1:nbI){
    V <- V%*%M
  }
  Affichage(as.vector(V),N)
}

Cette fonction sera itérée 4 fois par matrice avec un nombre d’itération variant, de gauche à droite, avec les valeurs 20,50,100,200. Les matrices ligne et sucette utiliseront un vecteur de proba initial valant (1/N,…,1/N) alors que la matrice anneau partira d’un vecteur (1/2,0,…,0,1/2) ((1/N,…,1/N) est le vecteur résultat attendu, il ne serait pas pertinent de commencer avec celui-ci).

Matrice ligne

Matrice anneau

Matrice sucette

Conclusion

Un résultat satisfaisant est obtenu en très peu d’itérations (200) par rapport à la marche aléatoire (1million). Cette méthode est donc à priviligier car elle s’avère plus précise, et plus rapide. Le choix du vecteur de proba a un impact sur le temps nécessaire à l’obtention d’un bon résultat. Pour la matrice anneau, commencer avec un vecteur (1/N,…,1/N), permet de terminer immédiatement, chaque itération supplémentaire n’aura aucun impact. On remarque également que la matrice sucette semble prendre plus de temps que ses homologues pour

Calcul des valeurs propres de la matrice

ValPropres <- function(M,N){
  #Cette partie permettant de calculer les valeurs propres provient directement du cours d'Eval de Perf de 2015
  V <- head(eigen(t(M)))
  val <- V$values
    j <- 1
  for(i in 2:N)
    if(val[i]>=val[j])
      j <- i
  rep=V$vectors[,j];
  rep = Re(rep/(sum(rep)))
  Affichage(rep,N)
}

Matrice ligne

ValPropres(ML,N)

Matrice anneau

ValPropres(MA,N)

Matrice sucette

ValPropres(MS,N)

Conclusion

Cette méthode est de loin la meilleure, un simple calcul de valeurs propres permet d’obtenir l’état stationnaire de la matrice très rapidement, d’autant plus qu’il s’agit des valeurs exactes et non une approximation comme pour les méthodes précédentes.

Bilan sur les formes de matrices

Comme attendu, sur une matrice anneau, chaque état obtient le même taux de passage. L’état stationnaire est réparti uniformément entre les états.
Concernant la matrice ligne, il est intéressant d’observer que seul les états en bout de ligne sont moins parcourus alors que les autres obtiennent une répartition égale. L’état 2 et l’état N/2 ont donc le même taux de passage.
Avec la sucette, on peut identifier un patterne dans l’état stationnaire. En effet, dans le cas d’une sucette avec 10 états, l’état 10 ne possède qu’un lien et obtient 0.05 de taux de passage. Les autres états, hormis l’état 5, en possèdent 2 et obtiennent le taux de passage de 0.1 soit 2x0.05. L’état 5 contient 3 liens dans cette matrice, il relie l’anneau et la ligne de la sucette. Son taux de passage vaut ainsi 0.15=3x0.05. On peut donc en déduire une formule pour connaître l’état stationnaire de chacunes des matrices en fonction de nombre de lien reliant les états aux autres : TauxDePassage = NbLiens/(2xN)