Approche expérimentale

Q1

Voici le code permettant de générer le nombre total de vignettes achetées T en fonction du nombre de cartes dans la collection M.

set.seed(42);
gen_vignette <- function(M) {
  continuer <- 1;
  achat <- 0 ;
  album <-rep(0,times=300); # On génère l'album Panini vide
  while(continuer == 1){
    vign <- floor((M+1)*runif(1));
    achat = achat + 1;
    # Lorsqu'on trouve une vignette, on remplit la case du tableau associé
    album[vign] = album[vign]+1;
    parcours = 1;
    # On continue l'exécution tant qu'il reste des cases du tableau vides
    while ((album[parcours] != 0) && (parcours < M)){
      parcours = parcours + 1 ;
    }
    if (parcours == M){
      continuer <- 0;
    }
  }
  achat;
}

Q2

A présent, voyons les différentes valeurs de T obtenues pour M entre 10 et 200. Pour celà, nous établissons une fonction faisant la moyenne de plusieurs échantillons..

#On fait la moyenne sur plusieurs essais
etude_gen_vignette <- function(e,M) {
  res = 0;
   for(i in (1:e)) {
     res = res + gen_vignette(M);
   }
  res/e;
}

Puis nous traçons la courbe obtenues pour les différentes valeurs de M.

XT = c();
XM = c();
for(i in (0:10)) {
  XM[i+1]=(10+i*19);
  XT[i+1] = etude_gen_vignette(100,(10+i*19));
}
plot(XM,XT)

plot of chunk unnamed-chunk-3

Nous constatons une évolution relativement linéaire de T en fonction de M.

Modélisation

Q3

L’énoncé suggère que les Xn sont indépendants et que les probabilités d’apparition sont équivalentes(pas de vignettes plus rares que d’autres). Le problème suit une loi géométrique : on considère une épreuve de Bernouilli dont la probabilité de succès (avoir une nouvelle vignette) est p et celle d’échec q=1-p (retomber sur une vignette déjà possédée). On renouvelle cette épreuve de manière indépendante jusqu’au premier succès.

Q4

Lorsque l’album est vide, la probabilité d’avoir une nouvelle vignette est égale à 1. Lors du prochain achat, la probabilité de retomber sur la même vignette est de \[\frac{1}{M}\] et donc celle d’avoir une nouvelle vignette est égale à \[(\frac{M-1}{M})\] De ce fait, lorsque l’album contient déjà i-1 vignette, la proba d’avoir une nouvelle vignette est égale à \[(\frac{M-i+1}{M})\] On en déduit \[P(Y_{i}=k)\] \[P(Y_{i}=k)=(\frac{1-i}{M})^{^{(k-1)}} (\frac{M-i+1}{M})\] où \[(\frac{i-1}{M})^{^{(k-1)}}\] est la probabilité de retomber (k-1) fois sur une carte déjà entre notre possession. (probabilité d’échec) et \[(\frac{M-i+1}{M})\] est donc la probabilité que le k-ième essai soit le bon (on a une nouvelle carte, probabilité de succès). Ainsi \[E(Y_{i})=\sum_{j=1}^{\propto }j(\frac{M-i+1}{M}) (\frac{i-1}{M})^{^{j}}= \frac{M}{M-i+1}\] et \[Var(Y_{i})= \frac{(\frac{i-1}{M})}{(\frac{(M-i+1)}{M})^{2}}\] Les variables \(Y_i\) sont indépendantes. On en déduit \[E(T)=\sum_{j=1}^{M}(\frac{M}{M-i+1})= 1+\frac{M}{M-1}+\frac{M}{M-2}+\frac{M}{M-3}+...=M(log(M)+0,577)\] où 0,5777 équivaut à la constante d’Euler-Mascheroni et \[Var(T)=Var(Y_{1})+Var(Y_{2})+...+Var(Y_{M})\] \[\leq \frac{M^{2}}{M^{2}}+\frac{M^{2}}{(M-1)^{2}}+...+\frac{M^{2}}{(1)^{2}}\] \[\leq M^{2}(\frac{1}{1^{2}}+\frac{1^{2}}{2^{2}}+...)=\frac{\pi^{2}}{6}M^{2}< 2M^{2}\]

Synthèse

Q5

Dans le test suivant, nous simulons la probabilité \(P(Y_{i}=5)\) dans notre exemple de 300 vignettes et nous la comparons à la formule théorique trouvée avant \(P(Y_{i}=k)=(\frac{1-i}{M})^{^{(k-1)}} (\frac{M-i+1}{M})\)

#Simulation de yi=k
test_unitaire_yi_k <- function(i,k,M){
  vign<-floor((M+1)*runif(1));
  acc<-1;
  #On considère qu'on a trouvé i vignettes sur 300, et que les i premières vignettes sont trouvées
  #Tant qu'on obtient une valeur de vignette inférieure, on doit retenter le lancer afin d'obtenir une nouvelle vignette
  while(vign<i){
    acc<-acc+1;
    vign<-floor((M+1)*runif(1));
  }
  acc==k;
}

#Moyenne de yi=k sur e tentatives
gen_yi_k <- function(e,i,k,M) {
  acc<-0.0;
  for(j in (1:e)) { if(test_unitaire_yi_k(i,k,M)){acc<-acc+1.0;} }
  acc/e;
}

X = c();
Y=c();
for(i in (1:300)) {X[i+1] = gen_yi_k(1000,i,5,300);}
for(i in (1:300)) {Y[i+1] = ((1-i)/300)^(4)*((300-i+1)/300);}
#Affichage sur 2 graphiques
par(mfrow = c(1,2));
plot(X);
plot(Y);

plot of chunk unnamed-chunk-4

Malgré quelques disparités, on constate que l’allure de la courbe de gauche coincide avec celle de droite. Notre formule déterminant \(P(Y_{i}=k)\) semble donc correcte.

A présent, vérifions \(E(Y_{i})\) Selon le même algorithme que le calcul de yi=k, on utilise l’accumulateur durant e essais de yi=k puis on divise par e pour obtenir l’espérance de yi selon ces e essais.

esperance_yi <- function(e,i,M){
  acc<-0;
  for(k in (1:e)){
    acc<-acc+1;
    vign<-floor((M+1)*runif(1));
    while(vign<i){
      acc<-acc+1;
      vign<-floor((M+1)*runif(1));
    }
  }
  acc/e;
}


X = c();
Y=c();
for(i in (1:300)) {X[i] = esperance_yi(1000,i,300);}
for(i in (1:300)) {Y[i] = 300/(300-i+1);}
par(mfrow = c(1,2));
plot(X);
plot(Y);

plot of chunk unnamed-chunk-5

Puis \(Var(Y_{i})\), en prenant pour l’espérance la valeur calculée. Dans cette fonction, on calcule l’écart entre la valeur et l’espérance et on met le tout au carré sur e essais. On fait ensuite la moyenne du tout pour obtenir la variance par la pratique.

var_yi <- function(e,i,M){
  res<-0;
  esp<-M/(M-i+1);
  for(k in (1:e)){
    acc<-1;
    vign<-floor((M+1)*runif(1));
    while(vign<i){
      acc<-acc+1;
      vign<-floor((M+1)*runif(1));
    }
    res<-res+(acc-esp)^2;
  }
  (res/e);
}


X = c();
Y=c();
for(i in (1:300)) {X[i] = var_yi(1000,i,300);}
for(i in (1:300)) {Y[i] = ((i-1)/300)/((300-i+1)/300)^2;}
par(mfrow = c(1,2));
plot(X);
plot(Y);

plot of chunk unnamed-chunk-6

On constate que les valeurs obtenues par le calcul pour la variance et la courbe formée en pratique concordent.

Voici ce que cela donne pour \(E(T)\)

#L'espérance consiste en la moyenne de T, déjà définie
T_simule=etude_gen_vignette(100,300);
T_calcule=300*(log(300)+0.5777);
T_simule;
## [1] 1862
T_calcule;
## [1] 1884

Et enfin Var(T)

var_T <- function(e,M){
  res<-0;
  esp<-M*(log(M)+0.5777);
  for(k in (1:e)){
    res<-res+(esp-gen_vignette(M))^2;
  }
  (res/e);
}

var_T(100,300);
## [1] 124896
2*(300)^2;
## [1] 180000

Selon la théorie, nous devions obtenir un résultat inférieux ou égal à \(2M²\). On constate qu’en pratique, cette tendance est vérifiée.

Q6

Afin de savoir combien notre petit cousin devra payer, il suffit de faire l’étude de génération de vignettes avec un nombre d’échantillons élevé et \(M=300\). On divise cette valeur par 10 afin d’avoir les cartes d’un paquet, on multiplie cette valeur par 2 afin d’avoir leur prix en euros, et enfin on ajoute le prix de l’album de 4€ afin de savoir l’argent dépensé par notre petit cousin.

x=etude_gen_vignette(100,300);
4+2*ceiling(x/10);
## [1] 386

On constate que ça lui revient ma foi très cher. Ce petit con ferait mieux de se faire des amis pour faire des échanges de cartes au lieu de ruiner ses parents.

Extension au cas non uniforme (ou au marchand malhonnête)

Q7

On s’intéresse cette fois au cas où les probabilités sont pipées.

gen_vignette_pipee <- function(M) {
  p = c()
  alpha = 0
  #Calcul de alpha et des probabilités p(i) de l'énoncé. Pour p, les valeurs de la case i sont égalesà à ceci: p(i)=proba(i)+p(i-1)
  for(k in (1:M)) { alpha = alpha + 1/k }
  p[1]=1/alpha
  for(i in (2:M)) { p[i] = p[i-1] + 1/(alpha*i) }
  achat <- 0 ;
  album <-rep(0,times=300); # On génère l'album Panini vide
  continuer<-1
  while(continuer == 1){
    vign <- runif(1);
    achat = achat + 1;
    ind<-1;
    #On détermine l'indice de la vignette en parcourant le tableau, lorsqu'on a une valeur vign supérieure à l'indice de tableau sur lequel on est, le numéro de vignette obtenu n'est pas encore atteint. On boucle jusqu'à ce qu'on ait le bon indice.
    while(vign>p[ind]){ind<-ind+1;}
    album[ind] = album[ind]+1;
    parcours = 1;
    while ((album[parcours] != 0) && (parcours < M)){
      parcours = parcours + 1 ;
    }
    if (parcours == M){
      continuer <- 0;
    }
  }
  achat;
}
etude_gen_vignette_pipee <- function(e,M) {
  res = 0;
   for(i in (1:e)) {
     res = res + gen_vignette_pipee(M);
   }
  res/e;
}
XT = c();
XM = c();
for(i in (0:10)) {
  XM[i+1]=(10+i*19);
  XT[i+1] = etude_gen_vignette_pipee(10,(10+i*19));
}
plot(XM,XT)

plot of chunk unnamed-chunk-12

Ici, on s’aperçoit qu’on doit acheter bien plus de vignettes qu’auparavant. Pour 200 vignettes à acheter, on doit acheter environ 5000 vignettes au lieu de 1200 (question 1). La courbe a la même forme, mais la pente est bien plus importante.

gen_vignette_pipee2 <- function(M) {
  p = c()
  alpha = 0
  for(k in (1:M)) { alpha = alpha + 1/(k^2) }
  #Calcul de alpha et des probabilités p(i) de l'énoncé. Pour p, les valeurs de la case i sont égalesà à ceci: p(i)=proba(i)+p(i-1)^2
  p[1]=1/alpha
  for(i in (2:M)) { p[i] = p[i-1] + 1/(alpha*(i^2)) }
  achat <- 0 ;
  album <-rep(0,times=300); # On génère l'album Panini vide
  continuer<-1
  while(continuer == 1){
    vign <- runif(1);
    achat = achat + 1;
    ind<-1;
    #On détermine l'indice de la vignette en parcourant le tableau, lorsqu'on a une valeur vign supérieure à l'indice de tableau sur lequel on est, le numéro de vignette obtenu n'est pas encore atteint. On boucle jusqu'à ce qu'on ait le bon indice.
    while(vign>p[ind]){ind<-ind+1;}
    album[ind] = album[ind]+1;
    parcours = 1;
    while ((album[parcours] != 0) && (parcours < M)){
      parcours = parcours + 1 ;
    }
    if (parcours == M){
      continuer <- 0;
    }
  }
  achat;
}
etude_gen_vignette_pipee2 <- function(e,M) {
  res = 0;
   for(i in (1:e)) {
     res = res + gen_vignette_pipee2(M);
   }
  res/e;
}
XT = c();
XM = c();
for(i in (0:10)) {
  XM[i+1]=(10+i*10);
  XT[i+1] = etude_gen_vignette_pipee2(10,(10+i*10));
}
plot(XM,XT)

plot of chunk unnamed-chunk-15

Cette fois-ci, T augmente de manière quadratique par rapport à M. Pour seulement 100 vignettes à acheter, on doit en acheter plus de 50 fois plus par rapport aux probabilités calculées précédemment.

Dans le dernier \(p_i\) proposé, nous supposons que l’évolution de T par rapport à M sera exponentielle.