Éval de perf, DM: Les derniers seront les premiers (RICM4, 2014)

library(ggplot2)
library(plyr)
library(reshape)

## 
## Attaching package: 'reshape'
## 
## The following objects are masked from 'package:plyr':
## 
##     rename, round_any

library(gridExtra)

## Loading required package: grid

set.seed(42);

Lord of the ring

Bon, commençons par une petite fonction qui génère la matrice d’adjacence correspondant à un anneau.

ring = function(N=10) {
  M=matrix(0,nrow=N,ncol=N)
  for(i in 1:N-1) {
    M[i,i+1]=1;
    M[i+1,i]=1;
  }
  M[1,N]=1;
  M[N,1]=1;
  M
}

On peut alors écrire une petite fonction qui réalise la marche aléatoire sur le graphe jusqu’à ce qu’on revienne dans le même état.

waiting = function(M,initial_state=1) {
  t = 0;
  N=dim(M)[1];
  state=initial_state;
  repeat {
     state=sample(1:N,size = 1,prob = M[state,])
     t=t+1
     if(state==initial_state) {break};
  } 
  t
}

Lançons maintenant notre simulation. Pour chacun des états de départ possible, je réalise 100 marches jusqu’à retour dans l’état et je conserve la longueur des marches.

simul = function(M,duration=100) {
  df=data.frame();
  for(state in (1:(dim(M)[1]))) {
    for(rep  in (1:duration)) {
      df=rbind(df,data.frame(state=state,time=waiting(M,state)))
    }
  }
  df
}
df = simul(ring(10),100);

Voyons à quoi cela ressemble:

view_boxplot = function(df) {
  ggplot(data=df,aes(x=state,y=time,group=state))+ geom_boxplot() +geom_jitter(alpha=.4,)
}
view_boxplot(df);

Essayons d’estimer l’espérance:

view_esperence = function(df,plot_orig_data=T) {
  d = ddply(df, c("state"), summarize, num=length(time), mean=mean(time), sd=sd(time));
  d$ci=2*d$sd/sqrt(d$num);
  
  p = ggplot(data=d,aes(x=state,y=mean)) +
        geom_errorbar(aes(ymin=mean-ci,ymax=mean+ci),width=.2) + 
        geom_point(shape=21,fill="white",color="red");
  if(plot_orig_data) {
    p + geom_jitter(data=df,aes(x=state,y=time,group=state),alpha=.3);
  } else {
    p;
  }
}
view_esperence(df,T)

Il y a une variabilité importante mais l’estimation de l’espérance n’a pas l’air trop mauvaise. Comme on pouvait s’y attendre, on ne voit pas de différence significative entre les différents états.

Ligne

Repartons de la fonction ring et adaptons

line = function(N=10) {
  M=matrix(0,nrow=N,ncol=N)
  for(i in 1:N-1) {
    M[i,i+1]=1;
    M[i+1,i]=1;
  }
  M
}

Et réutilisons les fonctions précédentes:

df = simul(line(10),100);
view_boxplot(df);

view_esperence(df)

Ah, là, on voit clairement la différence entre les états du bords et ceux de l’intérieur. Leur espérance est bien sûr plus élevée mais également leur variance… Pour les autres, par contre, ils semblent identiques. Ceux du milieu ne semblent pas plus “favorisés” que les autres.

Lollipop

lollipop = function(head=10,tail=10) {
  M=matrix(0,nrow=head+tail,ncol=head+tail)
  for(i in 1:tail) {
    M[i,i+1]=1;
    M[i+1,i]=1;
  }
  for(i in tail:(head+tail)) {
    for(j in tail:(head+tail)) {
      if(i!=j) { M[i,j]=1; }
    }
  }
  M
}

df = simul(lollipop(10),100);
view_boxplot(df);

Wow, il y a une sacré rupture entre les deux parties. Les valeurs pour la tige sont énormes et ont une variabilité énorme.

view_esperence(df,F);

Quand on est dans la tige, si on a de la chance, on y reste mais si jamais on se retrouve dans la clique, on y reste et on met une éternité à en sortir… Pour bien évaluer les choses, il faudrait donc simuler plus longtemps pour estimer l’espérence du temps de retour dans ces états là.