N<-100
iteration=1000000
set.seed(69)
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)
}
l = ligne(N)
a = anneau(N)
s = sucette(N)
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)
}
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.
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.
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.
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)
}
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.
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.
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.
#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)
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.