Question 1:

Principe : Un tableau de booléen indique si la carte i (indice du tableau) a été trouvé. Lorsque tout le tableau est rempli de TRUE, le carnet est complet et l’on connait le nombre de cartes qui ont dues être tirées.

t_en_fonction_M <-function(n){


M=c();
t=0;
for(k in c(1:n)){
  M[k]=FALSE;
}
while(sum(M)!=n){
 t=t+1; 
 P=runif(1);
 i=0;
 while(i<=n &(P>((i+1)/n))){
   i=i+1;
   k
 }
 M[i+1]=TRUE;
}
t;
}

Question 2

Fonction d’affichage graphique donnant l’histogramme et les différentes valeurs de T

graphical_check <-function(x){
  
  par(mfrow=c(1,2))
  hist(x)
  plot(x[1:length(x)-1],x[2:length(x)])
}

Fonction donnant un affichage graphique et la moyenne du nombre de carte pour n le nombre d’échantillon et m le nombre de cartes distinctes

nb_carte_moy<-function(n,m){
x=c()
for(i in c(1:n)){
  x[i]=t_en_fonction_M(m)
}
graphical_check(x)
res=sum(x)/n
res
}

Fonction qui est la même que la précédente sans l’appel à graphical check

nb_carte_moy_sg<-function(n,m){
x=c()
for(i in c(1:n)){
  x[i]=t_en_fonction_M(m)
}
res=sum(x)/n
res
}

On fait une expérience sur 100 échantillons et un nombre de cartes M égale à 10.

res=nb_carte_moy(100,10)

plot of chunk unnamed-chunk-5

res
## [1] 30.09

On augmente le nombre d’échantillons Nb= 1000

nb_carte_moy(1000,10)

plot of chunk unnamed-chunk-6

## [1] 29.37

On en conclu que la valeur moyenne est autour de 30 pour M=10

M=30

nb_carte_moy(100,30)

plot of chunk unnamed-chunk-7

## [1] 115
nb_carte_moy(1000,30)

plot of chunk unnamed-chunk-8

## [1] 121

L’écart entre 390 pour 100 échantillons et 120 pour 1000 nous incite fortement à renouveler le test avec plus d’échantillons.

nb_carte_moy(2000,30)

plot of chunk unnamed-chunk-9

## [1] 120.2

On en conclu d’après cette exprience que la moyenne de cartes necessaires converge vers 120 pour M=30

M=50

nb_carte_moy(100,50)

plot of chunk unnamed-chunk-10

## [1] 221.7

Résultat non significatif car le nombre T peut être grand. Ainsi il suffit de quelques grandes valeurs sur 100 échantillons pour que la moyenne soit biaisée.

nb_carte_moy(1000,50)

plot of chunk unnamed-chunk-11

## [1] 224.9

On réitère l’expérience une 3ème fois

nb_carte_moy(2000,50)

plot of chunk unnamed-chunk-12

## [1] 224.3

L’écart étant encore grand entre 1000 et 2000 échantillons on recommence avec 3000.

nb_carte_moy(3000,50)

plot of chunk unnamed-chunk-13

## [1] 224.9

Au vu des résultats on en conclu que T converge vers 225 pour M=50

M=100

nb_carte_moy(100,100)

plot of chunk unnamed-chunk-14

## [1] 526.5
nb_carte_moy(1000,100)

plot of chunk unnamed-chunk-15

## [1] 519

On en conclu qu’il faut environ 520 cartes pour une collection en comptant 100.

M=200

nb_carte_moy(100,200)

plot of chunk unnamed-chunk-16

## [1] 1173
nb_carte_moy(1000,200)

plot of chunk unnamed-chunk-17

## [1] 1166

On déduit de ces résultats que pour M=200 le nombre de vignettes à acheter est 1150

D’après les expériences ci-dessus on pense pouvoir relier M à T de la façon suivante : Il semblerait qu’il y ait une certaine linéarité reliant M à T. Le coefficient, avec les expériences précédentes ne peut être donné avec précision. Nous supposons qu’il se situe autour de 5.

Question 3:

L’énoncé suggère que les variables aléatoires Xi sont indépendantes et suivent une loi uniforme.

Question 4:

Afin de déterminer la loi que suivent les variables aléatoires Yi, nous avons raisonner sur de petites valeurs de M. Nous avons pu déterminer que P(Yi=k)=Ek-1*Rk c’est à dire l’échec des K-1 tirages précédents multiplié par la probabilité de réussite de kième tirage. Nous sommes face à une expérience “succès-échec” et nous supposons des tirages indépendants. Nous avons donc une loi géométrique. Dès lors la probabilité d’un échec E d’indice k-1 est égale à E1^(k-1).

La probabilté d’échec quelque soit i, est (i-1)/M. En effet on a déjà i-1 cartes sur le nombre total M. Il reste M-(i-1) cartes qui ne sont pas encore dans la collection. La probabilité d’en tirer une sachant les Xi sont indépendants et suivent une loi uniforme est (M-i+1)/M. Donc P(Yi=K)=((i-1)/M)^(K-1)*(M-i+1)/M

Nous savons que la loi que suivent les varaibles Yi est géométrique. On en déduit que l’espérance est : 1/R=M/(M-i+1) et que la variance est : (i-1)*M/(M-i+1)²

P(Yi=K) ne dépend pas de P(Yi-1). Les variables Yi sont donc indépendantes.

E(T)=E(Somme_de_1_a_M(Yi)) = Somme_de_1_a_M(E(Yi)) car Yi sont indépendantes et E() est liénaire. En effet chaque Yi vaut le nombre de carte tiré pour ajouter une ième carte à la collection. E(T)=M/M+M/(M-1)+..+M/(M-M+1) En ré ordonnant : E(T) = M/1 + M/2 + … + M/M On factorise par M : E(T)=M*Somme_de_1_a_M(1/i)

Or si M tend vers l’infini on a la suite des 1/k ce qui est équivalent à ln(M) Donc pour M très grand E(T)=M*ln(M)

X et Y sont indépendant alors cov(X,Y)=0. Donc Var(X+Y) = Var(X) +Var(Y) + 2 cov(X,Y) Par linéarisation : Var(T)=Var(Somme_de_1_a_M(Yi))= Somme_de_1_a_M(Var(Yi)) Var(T)=-M/(M+1)² + 2M/(M-2)² + … + M(M-1)

Question 5:

x=c()
i=10;
k=0;
while(i<=200){
x[k]=nb_carte_moy_sg(100,i)
i=i+((200-10)/5)
k=k+1}


plot(x[1:length(x)-1],x[2:length(x)])

plot of chunk unnamed-chunk-18 On doit voir ici une courbe quasi linéraire légérement courbé à cause du ln(m). Ainsi nous vérifions les calculs précédents par l’expérience en trçant la courbe qui doit être du m*ln(m)

Question 6:

Il devra payer le prix de p=2E(T)/10 +4 €. Pour M=300 E(T)=300ln(300)=1712 p=346,4€

Question 7:

t_en_fonction_M_truque <-function(n){
M=c();
t=0;
alpha=0
for(k in c(1:n)){
  M[k]=FALSE;
  alpha=alpha+1/k;
}

while(sum(M)!=n){
 t=t+1; 
 P=runif(1);
 i=0;
 while(i<=n &(P>(i+1)/(alpha*(i+1)))){
   i=i+1;
 }
 M[i+1]=TRUE;
}
t;
}

On change ici la condition d’entrée dans le tableau par 1/(alpha*(i+1)) qui est la probabilité à laquelle correspond pi.

nb_carte_moy_truque<-function(n,m){
x()
for(i in c(1:n)){
  x[i]=t_en_fonction_M_truque(m)
}
graphical_check(x)
res=sum(x)/n
res
}