Nombre attendu de cartes invisibles lors du tirage de cartes d'un paquet de taille

Nous avons un jeu de cartes. Nous en tirons des cartes uniformément au hasard avec remplacement. Après tirages, quel est le nombre attendu de cartes jamais choisies?$n$$2n$

Cette question fait partie du problème 2.12 de

M. Mitzenmacher et E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis , Cambridge University Press, 2005.

De plus, pour ce que ça vaut, ce n'est pas un problème de devoirs. C'est l'auto-apprentissage et je suis juste coincé.

Jusqu'à présent, ma réponse est:

Soit le nombre de cartes distinctes vues après le ème tirage. Alors:$X_i$$i$

$E[X_i] = \displaystyle \sum_{k=1}^{n} k (\frac{k}{n}P(X_{i-1}=k) + \frac{n-k-1}{n} P(X_{i-1}=k-1))$

L'idée ici est qu'à chaque fois que nous tirons, nous tirons soit une carte que nous avons vue, soit une carte que nous n'avons pas vue, et que nous pouvons définir cela de manière récursive.

Enfin, la réponse à la question, combien n'avons-nous pas vu après tirages, sera .$2n$$n-E[X_{2n}]$

Je pense que c'est correct, mais qu'il doit y avoir une solution plus simple.

Toute aide serait grandement appréciée.

Astuce: à tout tirage, la probabilité qu'une carte ne soit pas choisie est . Et puisque nous dessinons avec remplacement, je suppose que nous pouvons dire que chaque tirage est indépendant des autres. Donc, la probabilité qu'une carte ne soit pas choisie en tirages est ...$\frac{n-1}{n}$$2n$

Merci Mike pour l'astuce.

C'est ce que j'ai trouvé.

Soit une variable aléatoire de Bernoulli où si la carte n'a jamais été tirée. Alors , mais comme est le même pour tout , soit .$X_i$$X_i = 1$$i^{th}$$p_i = P(X_i=1) = (\frac{n-1}{n})^{2n}$$p_i$$i$$p=p_i$

Soit maintenant le nombre de cartes non tirées après tirages.$\displaystyle X = \sum_{i=1}^n X_i$$2n$

Alors$\displaystyle E[X] = E[\sum_{i=1}^n X_i] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n p = np$

Et c'est ce que je pense.

Voici du code R pour valider la théorie.

evCards <- function(n) 
{
    iter <- 10000;
    cards <- 1:n;
    result <- 0;
    for (i in 1:iter) {
        draws <- sample(cards,2*n,T);
        uniqueDraws <- unique(draws,F);
        noUnique <- length(uniqueDraws);
        noNotSeen <- n - noUnique;
        result <- result + noNotSeen;
    }
    simulAvg <- result/iter;
    theoryAvg <- n * ((n-1)/n)^(2*n);
    output <-list(simulAvg=simulAvg,theoryAvg=theoryAvg);
    return (output);
}