Oczekiwana liczba niewidzialnych kart przy dobieraniu

Mamy talię kart. Losujemy z niego karty jednolicie losowo z wymianą. Po 2 n losowaniach, jakiej oczekiwanej liczby kart nigdy nie wybrałeś?$n$$2n$

To pytanie jest częścią 2 problemu 2.12 w

M. Mitzenmacher i E. Upfal, Prawdopodobieństwo i obliczenia: randomizowane algorytmy i analiza probabilistyczna , Cambridge University Press, 2005.

Co więcej, nie jest to zadanie domowe. To samokształcenie i po prostu utknąłem.

Moja dotychczasowa odpowiedź brzmi:

Niech być liczba oddzielnych kart traktowany po I th rysować. Następnie:$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))$

Chodzi o to, że za każdym razem, gdy dobieramy, albo dobieramy kartę, którą widzieliśmy, albo dobieramy kartę, której nie widzieliśmy, i że możemy to zdefiniować rekurencyjnie.

$2n$$n-E[X_{2n}]$

Uważam, że jest to poprawne, ale musi istnieć prostsze rozwiązanie.

Każda pomoc byłaby bardzo mile widziana.

$\frac{n-1}{n}$$2n$

Dziękuję Mike za podpowiedź.

Właśnie to wymyśliłem.

$X_i$$X_i = 1$$i^{th}$$p_i = P(X_i=1) = (\frac{n-1}{n})^{2n}$$p_i$$i$$p=p_i$

$\displaystyle X = \sum_{i=1}^n X_i$$2n$

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

I to chyba tak.

Oto trochę kodu R do weryfikacji teorii.

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);
}