set.seed(40);
simulateur = function(M, N) {
album <- logical(M);
reste <- M;
nbPaquets <-0;
while(reste > 0) {
for (i in (1:N)) {
j <- ceiling(runif(1)*M);
if(album[j] == FALSE) {
reste <- reste - 1;
album[j] <- TRUE;
}
}
nbPaquets <- nbPaquets + 1;
}
return(nbPaquets);
}
simulateur_X = function(M,N) {
table <- numeric();
for (i in (1:100)) {
table[i] = simulateur(M,N);
}
return(mean(table));
}
table <- numeric();
for (i in (1:20)) {
table[i*10] = simulateur_X((i*10),1);
}
plot(table, xlab = "M", ylab = "T");
Remarque: On remarque que le rapport entre T et M est presque constant de valeur r = T/M ( r ≈ 5.13)
Ce sont les variables généré uniformément dans [1:M]
\(p_i = \frac{M -i+1}{M}\\ P(Y_i = k) = (1-p)^{k-1}p\\ E(Y_i) = \sum_{k=1}^∞ kP(Y_i=k) = \sum_{k=1}^∞ k(1-p)^{k-1}p = p\sum_{k=1}^∞ k(1-p)^{k-1}\\ Parce\ que\\ \frac{d}{dr}\sum_{k=0}^∞ r^k = \sum_{k=1}^∞ kr^{k-1} = \frac{d}{dr}(\frac{1}{1-r}) = \frac{1}{(1-r)^2}\\ Avec\ r = 1-p, on\ a \\ E(Y_i) = p\sum_{k=1}^∞ k(1-p)^{k-1} = p\frac{1}{ (1-(1-p))^2} = \frac{1}{p}\\ Var(Y_i) = \frac{1-p} {p^2}\\ Y_i\ n'est\ pas\ independent.\\ E(T) = E(\sum_{i=1}^M Y_i) = \sum_{i=1}^M E(Y_i) = \sum_{i=1}^M \frac{1}{p} = \sum_{i=1}^M \frac{M-i+1}{M} \\ Var(T) = Var(\sum_{i=1}^M Y_i) = \sum_{i=1}^M Var(Y_i) = \sum_{i=1}^M \frac{1-p}{p^2} = \sum_{i=1}^M \frac{M*(i-M)}{(M-i+1)^2} \)
set.seed(40);
tirage <- function(M = 300){
album <- c();
num_table <- c();
for(i in (1:M)){
num <- 1;
while(TRUE){
x <- ceiling(runif(1)*M);
if(x %in% album){
num <- num + 1;
}
else{
album[i] <- x;
num_table[i] <- num;
break;
}
++num;
}
}
num_table;
}
try <- seq(from = 0, to = 0, length.out = 100)
for(i in (1:100)){
try <- try + tirage();
}
plot(try/100, xlab = "i", ylab = "Y(i)");
nb <- simulateur_X(300,10)*2 + 4;
print(nb);
## [1] 389.94
proba <- function(N) {
i <- 1:N;
alpha <- sum(1/i[1:max(which(i <= N))]);
x <- runif(1);
res <- 0;
j <- 0;
p <- 0;
while (res == 0 && j <= N) {
j <- j + 1;
p <- p + (1/(j*alpha));
if (x < p) {
res <- 1;
}
}
if (res == 0) {
j <- proba(N);
}
return(j);
}
simulateur2 = function(M, N) {
album <- logical(M);
reste <- M;
nbPaquets <-0;
while(reste > 0) {
for (i in (1:N)) {
j <- proba(M);
if(album[j] == FALSE) {
reste <- reste - 1;
album[j] <- TRUE;
}
}
nbPaquets <- nbPaquets + 1;
}
return(nbPaquets);
}
simulateur2(300,1);
## [1] 6717
simulateur2_X = function(M,N) {
table <- numeric();
for (i in (1:10)) {
table[i] = simulateur2(M,N);
}
return(mean(table));
}
table2 <- numeric();
for (i in (1:20)) {
table2[i*5] = simulateur2_X((i*5),1);
}
plot(table2, xlab="M", ylab="T");
proba2 <- function(N) {
i <- 1:N;
alpha <- sum(1/(i*i)[1:max(which(i <= N))]);
x <- runif(1);
res <- 0;
j <- 0;
p <- 0;
while (res == 0 && j <= N) {
j <- j + 1;
p <- p + (1/(j*j*alpha));
if (x < p) {
res <- 1;
}
}
if (res == 0) {
j <- proba2(N);
}
return(j);
}
simulateur3 = function(M, N) {
album <- logical(M);
reste <- M;
nbPaquets <-0;
while(reste > 0) {
for (i in (1:N)) {
j <- proba2(M);
if(album[j] == FALSE) {
reste <- reste - 1;
album[j] <- TRUE;
}
}
nbPaquets <- nbPaquets + 1;
}
return(nbPaquets);
}
simulateur3_X = function(M,N) {
table <- numeric();
for (i in (1:10)) {
table[i] = simulateur3(M,N);
}
return(mean(table));
}
table3 <- numeric();
for (i in (1:10)) {
table3[i*5] = simulateur3_X((i*5),1);
}
plot(table3, xlab="M", ylab="T");
On remarque qu'il est plus difficile d'avoir les cartes de fin d'album plutot que celles du debut. On remarque que de plus en plus vite, plus le nombre de cartes dans l'album est grand.
Sachant que la probabilité d'avoir une carte grande est de plus en plus faible, le nombre de tirage va augmenter par conséquent. On se retrouvera donc avec un courbe comme celle de la question précédente mais avec un nombre de tirage beaucoup plus élevé.