Initialisation

N<-100
iteration=1000000
set.seed(69)

Différent graphes

ligne = function(taille){
  mat = matrix(0,taille,taille)
  for(i in 2:taille){
    mat[i-1,i]=1
    mat[i,i-1]=1
  }
  
  mat = mat*(1/rowSums(mat))
  
  return(mat)
}

anneau = function(taille){
  mat = matrix(0,taille,taille)
  for(i in 2:taille){
    mat[i-1,i]=1
    mat[i,i-1]=1
  }
  
  mat[taille,1]=1
  mat[1, taille]=1
  
  mat = mat*(1/rowSums(mat))
  
  return(mat)
}

sucette = function(taille){
  mat = matrix(0,taille,taille)
  for(i in 2:taille){
    mat[i-1,i]=1
    mat[i,i-1]=1
  }
  
  mat[taille,(taille)/2]=1
  mat[(taille)/2,taille]=1
  
  mat = mat*(1/rowSums(mat))
  
  return(mat)
}
Affichage des matrices des graphes
l = ligne(N)
a = anneau(N)
s = sucette(N)
Algorithme de la marche aléatoire
marcheAlea = function(mat, nbMarche){
  
  v = sample(1:N, 1)
  res = rep(0,N)
  res[v]=res[v]+1
  for(i in 1:nbMarche){
    v=sample(1:N, size= 1, replace=FALSE,prob=mat[v,])
    res[v]=res[v]+1
  }
  return(res/iteration)
}
Marche aléatoire pour la “ligne”
t=proc.time()
nbPassage= marcheAlea(l, iteration)
t=proc.time()-t
t
##    user  system elapsed 
##    7.61    0.02    7.62
plot(nbPassage)

On constate que les 2 points extrêmes sont plus bas que les autres. C’est a dire qu’il apparaisse moins fréquemment que les autres. Les autres formes une ligne non régulière. Ceci est surement du au fait qu’il n’y ai qu’un seul départ. Il faudrait faire plusieurs fois l’algorithme et faire la moyenne de toutes les courbes pour bien voire le résultat.

Marche aléatoire pour la “anneau”
t=proc.time()
nbPassage= marcheAlea(a, iteration)
t=proc.time()-t
t
##    user  system elapsed 
##    7.64    0.00    7.66
plot(1:N,nbPassage)

Pour l’anneau, les points sont bien répandu sur le graphique. On ne peut pas déterminer la tendance de la courbe.

Marche aléatoire pour la “sucette”
t=proc.time()
nbPassage= marcheAlea(s, iteration)
t=proc.time()-t
t
##    user  system elapsed 
##    7.59    0.02    7.62
plot(1:N,nbPassage)

Pour la sucette on constate qu’il y a tout les points (sauf un) qui varie légèrement autour d’une droite.Le point le plus haut est le noeud ou l’on passe le plus fréquemment. IL correspond au noeud qui relie le cercle de la sucette et ça tige.

Itération

l = ligne(N)

vecteurAlea = function(n){
  return(rep(1/n,n))
}

mulMat = function(mat1, mat2, n){
  for(i in 1:n){
    mat1 = mat1%*%mat2
  }
  

  return(mat1)
}
Pour la “ligne”
t=proc.time()
nbPassage = mulMat(vecteurAlea(N), l, iteration)
t=proc.time()-t
t
##    user  system elapsed 
##   40.96    0.02   41.00
plot(1:N,nbPassage)

On constate que tous les points sont sur la même ligne, sauf les 2 extrèmes.

Pour “l’anneau”
nbPassage = mulMat(vecteurAlea(N), a, iteration)
plot(1:N,nbPassage)

On constate que tous les points sont sur la même ligne. Pas de différence de fréquence de passage entre tous les noeuds.

Pour la “sucette”
nbPassage = mulMat(vecteurAlea(N), s, iteration)
plot(1:N,nbPassage)

On constate que tous les points sont sur la même ligne sauf un qui correspond à la liaison entre le cercle de la sucette et ça tige.

Calcul des valeurs propres

Pour la ligne
#install.packages("DTMCPack")
t=proc.time()
nbPassage = DTMCPack::statdistr(l)
t=proc.time()-t
t
##    user  system elapsed 
##    0.00    0.00    0.11
plot(1:N,nbPassage)

######Pour l’a ligne’anneau

t=proc.time()
nbPassage = DTMCPack::statdistr(a)
t=proc.time()-t
t
##    user  system elapsed 
##       0       0       0
plot(1:N,nbPassage)

Pour la sucette
t=proc.time()
nbPassage = DTMCPack::statdistr(s)
t=proc.time()-t
t
##    user  system elapsed 
##       0       0       0
plot(1:N,nbPassage)

Par le calcul des valeurs propres, on trouve les même résultats que par itération.

L’algorithme de marche aléatoire est le moins préci d’entre eux. Pour améliorer la précision il faudrait partir de plusieurs noeuds différent. Dans mon algorithme, je part que d’un noeud tiré au hasard.

Par valeurs propre ou par itération on trouve des résultats bien plus précis (Par valeur propre résultat exacte). Mais le calcul par itération est bien plus long que celui par valeur propre. Je n’ai pas réussi à déterminer si le calcul par itération était toujours plus long que par valeurs propres.