Binôme : Malek MAMMAR & Alexandre LE JEAN

Question 1

Ecrivons un simulateur générant T en fonction de M

set.seed(10)
simulateur <- function (M = 300) {
  album = array(0, c(M));
  nb_Case_Non_Etiquetés = M;
  Tresultat = 0; 
  while (nb_Case_Non_Etiquetés > 0) {
    x = floor(runif(1,1,M+1));
    if (album[x] == 0) {
      album[x] = 1;
      nb_Case_Non_Etiquetés = nb_Case_Non_Etiquetés - 1;
    } 
    Tresultat = Tresultat + 1;
  }
  Tresultat
}
simulateur(M=10);

## [1] 38

Question 2

Etudions la valeur moyenne de T en fonction de M

set.seed(10)
df = data.frame(varM = c(), echant=c())

m = 0
for(k in 1:10){
  m = m + 20
  echantillon = 0;
  for(i in 1:100){
      echantillon = echantillon + simulateur(M=m)
  }
  echantillon = echantillon / 100
  df = rbind(df, data.frame(varM = m, echant = echantillon))
}

barplot(df$echant, names.arg=df$varM, xlab="Albums de taille M", ylab ="Nombre total de vignettes achetées T")

Conclusion :

Sur une dizaine de valeurs de M entre 10 et 200. On peut remarquer que le nombre de vignette T achetées evolue linéairement par rapport a la taille M de l’album.

Question 3

Les hypothèses satistiques sur la suite de variables aléatoires que l’énoncé suggère sont:

• l’indépendance : la séquence d’appels à un générateur aléatoire modélisé par la suite $X1, .., Xn$ de variables aléatoires.

• l’uniformité : en moyenne les valeurs des variables aléatoires sont reparties (homogène) sur ${1,..,M}$

Ainsi il faut que les variables aléatoires soient indépendantes et identiquement distribuée.

Question 4

$Yi$ est une suite de tirages avec $k-1$ échecs (la carte est déjà dans l’album), suivi d’une réussite (la carte n’est pas dans l’album).

Le tirage d’une carte est une loi de Bernoulli de paramètre $p = (M-i+1)/M$ ( avec $M-i+1$ est le nombre de cartes manquantes dans l’album, $M$ le nombre d’emplacements dans l’album).

D’où $Yi$ suit une loi géométrique de paramètre $p = (M-i+1)/M$.

Donc

$$E(Yi) = 1/p$$ et $$Var(Yi) = q/p^2 \text{ , avec q = 1 - p}$$

Les variables $Yi$ sont indépendantes car le nombre de cartes tirées à l’instant où $i$ cartes sont présentes dans l’album ne dépend pas du nombre de cartes tirées à l’intant $i-1$, mais dépend du nombre de cartes $i$ présentes dans l’album.

Calculons $E(T)$ et $Var(T)$ :

$$T = \sum_{i=1}^{M}Yi$$ Car $T$ est le nombre moyen de cartes qu’on aura piochés au total pour avoir toute la collection et $Yi$ est le nombre moyen de cartes à piocher pour avoir une nouvelle carte sachant que l’on en possède $i-1$. Donc $T = \sum_{i=1}^{M}Yi$ est le nombre moyen de cartes à piocher pour avoir toutes les cartes.

$$E(T) = E(\sum_{i=1}^{M}Yi) = \sum_{i=1}^{M}E(Yi) = \sum_{i=1}^{M}1/p$$ Un équivalent quand $M$ est grand serait $o(M)$. Car quand M est grand le terme le plus grand de la somme est $M$ pour $i = M$.

$$Var(T) = Var(\sum_{i=1}^{M}(Yi)) = \sum_{i=1}^{M}(Var(Yi)) = \sum_{i=1}^{M}(q/p^2)$$ Rappelons que la variance est linéaire car les $Yi$ sont indépendants. Un équivalent quand $M$ est grand serait $o(M)$. Car quand $M$ est grand le terme le plus grand de la somme est $M$ pour $i = M$.

Question 5

Pour Vérifier graphiquement les résultats obtenus, nous remarquons que le graphe est linéaire ce qui par calcule coincide par le fait que $\sum_{i=1}^{M}(Yi) \text{ ~ } o(M)$.

Question 6

m = 300
res = 0
for(i in 1:m){
  res = res + (m/(m-i+1))
}
res = res - (res %% 10) + 10 #On arrondie a la dizaine supérieure
res = (res / 10) * 2 #On divise par le nombre de cartes par paquet, multiplié par le prix
res

## [1] 378

Conclusion :

Notre petit cousin doit payer 378 ??? en moyenne si l’album comporte 300 places.

Extension au cas non uniforme

Question 7

Adaptons notre simulateur afin d’étudier les deux cas suivants :

• La probabilité d’obtenir la carte $i$ est égale à $p_i=\frac{1}{a i}$ avec $a=\sum_{k=1}^{M} \frac{1}{k}$ :

set.seed(10)

alpha <- function(M=300) {
  res = 0
  for(k in 1:M){
    res = res + 1/k
  }
  res
}

pi <- function(i = 1, alpha = 1) {
  1/(alpha*i)
}

draw <- function (M=300, alpha){
  r = runif(1)
  acc2 = pi(1, alpha) 
  acc1 = 0
  i = 1
  
  while (!(r >= acc1 && r<acc2)) {
    acc1 = acc2
    i = i + 1
    acc2 = pi(i, alpha) + acc1
  }
  i
}

simulateur2 <- function (M = 300) {
  album = array(0, c(M));
  nb_Case_Non_Etiquetés = M;
  Tresultat = 0; 
  alphas = alpha(M);
  while (nb_Case_Non_Etiquetés > 0) {
    x = draw(M, alphas);
    if (album[x] == 0) {
      album[x] = 1;
      nb_Case_Non_Etiquetés = nb_Case_Non_Etiquetés - 1;
    } 
    Tresultat = Tresultat + 1;
  }
  Tresultat
}

Représentation graphique :

set.seed(10)
df = data.frame(varM = c(), echant=c())

m = 0
for(k in 1:10){
  m = m + 20
  echantillon = 0;
  for(i in 1:25){
      echantillon = echantillon + simulateur2(M=m)
  }
  echantillon = echantillon / 25 #moyenne des echantillons
  df = rbind(df, data.frame(varM = m, echant = echantillon))
}

barplot(df$echant, names.arg=df$varM, xlab="Albums de taille M", ylab ="Nombre total de vignettes achetées T")

• La probabilité d’obtenir la carte $i$ est égale à $p_i=\frac{1}{a i^2}$ avec $a=\sum_{k=1}^{M} \frac{1}{k^2}$ :

set.seed(10)

alpha2 <- function(M=300) {
  res = 0
  for(k in 1:M){
    res = res + 1/(k*k)
  }
  res
}

pi2 <- function(i = 1, alpha = 1) {
  1/(alpha*i*i)
}

draw2 <- function (M=300, alpha){
  r = runif(1)
  acc2 = pi2(1, alpha) 
  acc1 = 0
  i = 1
  
  while (!(r >= acc1 && r<acc2)) {
    acc1 = acc2
    i = i + 1
    acc2 = pi2(i, alpha) + acc1
  }
  i
}

simulateur3 <- function (M = 300) {
  album = array(0, c(M));
  nb_Case_Non_Etiquetés = M;
  Tresultat = 0; 
  alphas = alpha2(M);
  while (nb_Case_Non_Etiquetés > 0) {
    x = draw2(M, alphas);
    if (album[x] == 0) {
      album[x] = 1;
      nb_Case_Non_Etiquetés = nb_Case_Non_Etiquetés - 1;
    } 
    Tresultat = Tresultat + 1;
  }
  Tresultat
}

Représentation graphique :

set.seed(10)
df = data.frame(varM = c(), echant=c())

m = 0
for(k in 1:10){
  m = m + 20
  echantillon = 0;
  for(i in 1:10){
      echantillon = echantillon + simulateur3(M=m)
  }
  echantillon = echantillon / 10 #moyenne des echantillons
  df = rbind(df, data.frame(varM = m, echant = echantillon))
}

barplot(df$echant, names.arg=df$varM, xlab="Albums de taille M", ylab ="Nombre total de vignettes achetées T")

Conclusion :

On peut remarquer que la valeur T augmente de façon exponentielle par rapport à la valeur de M.

Question 8

Vu les résultats précédents, selon nous, la valeur T augmentera de manière beaucoup beaucoup plus rapide puisque

$$2^i >> i^2$$ et que la probabilité $p_i$ d’avoir les dernières cartes tend vers zéro quand M est grand.