Avant toutes choses, on initialise la graine du générateur aléatoire :

set.seed(42);

Approche expérimentale

Question 1

La première chose à faire est d’écrire une fonction simulant le tirage d’une vignette parmi un ensemble de \(M\) vignettes différentes et respectant une loi uniforme:

tirer_vignettes = function(m, x = 1) {
  floor(runif(1)*(m+1));
}

On écrit ensuite une fonction simulant \(T\). On commence par créer un tableau de \(M\) cases initialisées à 0 (représentant l’album de vignettes), puis, à chaque tirage d’une vignette, on met 1 dans la case correspondante. On s’arrête lorsqu’il n’y a plus de cases à 0 (album remplit) et l’on retourne le nombre de tirages qui ont été nécessaires :

gen_T = function(m) {
  t = 0; #Compteur de tirages
  album = rep(0,m); #Initialisation d'un album vide
  while(0 %in% album){ #Tant que l'album n'est pas plein
    album[tirer_vignettes(m)] = 1; #On place la vignette tirée dans l'album
    t = t+1; 
  }
  t;
}

Question 2

On teste la valeur moyenne de \(T\) en fonction de \(M\) en faisant varier \(M\) et en répétant l’expérience 300 fois pour chaque valeur. On prend \(M \in \{ 10,25,50,75,100,125,150,175,190,200 \}\).

moy_T = function(m, n) { # Fonction répétant l'expérience n fois pour un M donné
  tab_res = c();
  for(i in 1:n) {
    tab_res[i] = gen_T(m);
  }
  mean(tab_res); # On retourne le T moyen observé
}

tab_moy = c();

for(m in c(10,25,50,75,100,125,150,175,190,200)) {
  tab_moy[m] = moy_T(m, 300);
}

plot(tab_moy, xlab="Nombre de vignettes dans la collection", ylab="Nombre moyen de tirages", main="Nombre de vignettes à acheter pour remplir un album")

On observe que la courbe à une pente non régulière qui croit légèrement, elle n’est donc pas linéaire. ## Modélisation ### Question 3 L’énoncé suggère que les variables \(X_1, X_2, ..., X_n\) sont indépendantes : les vignettes obtenues n’influent pas sur les prochaines.

Question 4

La valeur prise par \(Y_i\) dépend d’une épreuve de Bernouilli. On enchaine \(k-1\) échecs \((X_1...X_{k-1})\) puis \(X_k\) correspond à une vignette que l’on ne possède pas encore.

\(P(Y_i=k) = (1-p)^{k-1} \times p\) avec \(p = \frac{M-i+1}{M}\) correspondant à la probabilité de tirer une carte que l’on ne possède pas encore. On en déduit que la loi suivie par \(Y_i\) est une loi géométrique.

Son espérance est \(\mathbb{E}(Y_i)=\frac{1}{p}=\frac{M}{M-i+1}\).

Sa variance est \(Var(Y_i)=\frac{p-1}{p^2}=\frac{1}{\frac{(M-i+1)^2}{M^2}}\times\frac{i-1}{M}=\frac{M(i-1)}{(M-i+1)^2}\)

Chaque \(Y_i\) suit une loi géométrique propre, elles sont donc indépendantes.

\(\mathbb{E}(T)=\sum\limits_{i=1}^{M}\mathbb{E}(Y_i)=\sum\limits_{i=1}^{M}\frac{M}{M-i+1}=\frac{M}{M}+\frac{M}{M-1}+...+\frac{M}{M-M+1}=\frac{M}{1}+\frac{M}{2}+...+\frac{M}{M}=M\sum\limits_{i=1}^{M}\frac{1}{i}\)

Donc \(\mathbb{E}(T)\approx M\log{M}\) lorsque \(M\) est grand (suite harmonique).

\(Var(T)=\sum\limits_{i=1}^{M}Var(Y_i)=\sum\limits_{i=1}^{M}\frac{M(i-1)}{(M-i+1)^2}\)

Synthèse

Question 5

Pour vérifier que nos simulations et nos calculs sont cohérents, on calcul l’espérance de T :

# Fonction calculant l'espérance
esp_T = function(m) {
  res = 0;
  for(i in 1:m) {
    res = res + (m/i);
  }
  res;
}

tab = c();

# Calcul de l'espérance pour M de 1 à 200
for(j in 1:200) {
  tab[j] = esp_T(j);
}

plot(tab, type="l", xlab="Nombre de vignettes dans la collection", ylab="Nombre moyen de tirages", main="Espérance de T")

On constate que l’espérance correspond aux valeurs obtenues par simulation concernant le nombre moyens de vignettes à acheter en fonction de \(M\).

Question 6

En utilisant l’espérance, on peut estimer le nombre moyen de paquets à acheter pour remplir une collection de \(M=\) 300 vignettes.

nb_moy_vignettes = esp_T(300); # On calcul le nombre moyen de vignettes à acheter
nb_moy_paquets = (ceiling(nb_moy_vignettes/10)) # On calcul ensuite le nombre de paquets en arrondissant à la dizaine de vignettes supérieur
prix_moy = nb_moy_paquets*2 # Finalement, on obtient le prix moyen correspondant

Le coût moyen à dépenser pour obtenir l’intégralité de la collection est donc de 378 euros.

Extension au cas non uniforme

Question 7

On écrit un code en R permettant de simuler le remplissage d’un album avec le premier marchand malhonnête. Ce code utilise la méthode de découpage d’un segment en sections de plus ou moins grande taille (proportionnels à la probabilité) afin de trouver quelle vignette a été tirée.

On ne fait le test que pour \(M \in \{ 10,25,40,55,70,85 \}\) et sur 100 essais à chaque valeur de \(M\) afin d’accélérer les calculs.

nbVignettesAcheteesMalhonnete1 <- function(m){
  t = 0 # Nombre de tirages nécessaires
  alpha = 0 # Coefficient alpha
  tab = rep(0,m) # Album de vignettes
  for (i in c(1:m)){
    alpha = alpha + (1/i)
  }
  while (0 %in% tab){
    alea = runif(1) # On tire un réel aléatoire entre 0 et 1
    p = 0
    case = 0
    while (alea >= p){ # On test dans quelle portion du "segment" se trouve le réel aléatoire
      case = case + 1
      p = p + (1 / (alpha * case)) 
    }
    tab[case] <- 1 # On "met" la vignette obtenue dans l'album
    t <- t + 1 # On augmente le nombre de vignettes achetées
  }
  t;
}

# Comme précédemment, on répète plusieurs fois l'expérience pour un M donné et l'on fait une moyenne
moy_T = function(m, n) {
  tab_res = c();
  for(i in 1:n) {
    tab_res[i] = nbVignettesAcheteesMalhonnete1(m);
  }
  mean(tab_res);
}

tab_moy = c();

for(m in c(10,25,40,55,70,85)) {
  tab_moy[m] = moy_T(m, 100);
}

plot(tab_moy, xlab="Nombre de vignettes dans la collection", ylab="Nombre moyen de tirages", main="Nombre de vignettes à acheter (Vendeur malhonnête 1)")

On réitère l’expérience avec la 2ième loi de probabilité.

nbVignettesAcheteesMalhonnete2 <- function(m){
  t = 0 # Nombre de tirages nécessaires
  alpha = 0 
  tab = rep(0,m)
  for (i in c(1:m)){
    alpha = alpha + (1/(i*i))
  }
  while (0 %in% tab){
    alea = runif(1) # On tire un réel aléatoire entre 0 et 1
    p = 0
    case = 0
    while (alea >= p){ # On test dans quelle portion du "segment" se trouve le réel aléatoire
      case = case + 1
      p = p + (1 / (alpha * case*case)) 
    }
    tab[case] <- 1
    t <- t + 1
  }
  t;
}

moy_T = function(m, n) {
  tab_res = c();
  for(i in 1:n) {
    tab_res[i] = nbVignettesAcheteesMalhonnete2(m)
  }
  mean(tab_res);
}

tab_moy = c();

for(m in c(10,25,40,55,70,85)) {
  tab_moy[m] = moy_T(m, 100);
}

plot(tab_moy, xlab="Nombre de vignettes dans la collection", ylab="Nombre moyen de tirages", main="Nombre de vignettes à acheter (Vendeur malhonnête 2)")

On peut remarquer que ce type de système favorise très nettement le vendeur car \(T\) devient vraiment très grand comparativement à \(M\).

Question 8

Avec la 3ième loi, on peut supposer que \(T\) devient encore plus grand pour un \(M\) donné car la probabilité de certaines cartes devient très petite.