Erwartete Anzahl unsichtbarer Karten beim Ziehen von Karten aus einem Stapel der Größe

Wir haben ein Kartenspiel mit Karten. Wir ziehen einheitlich zufällig Karten mit Ersatz. Wie viele Karten werden nach Ziehungen nie ausgewählt? 2 $n$$2n$

Diese Frage ist Teil 2 von Problem 2.12 in

M. Mitzenmacher und E. Upfal, Wahrscheinlichkeit und Datenverarbeitung : Randomisierte Algorithmen und probabilistische Analyse , Cambridge University Press, 2005.

Auch für das, was es wert ist, ist dies kein Hausaufgabenproblem. Es ist Selbststudium und ich stecke einfach fest.

Meine bisherige Antwort lautet:

Sei die Anzahl der verschiedenen Karten, die nach dem ten Ziehen gesehen werden. Dann:$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))$

Die Idee dabei ist, dass wir jedes Mal, wenn wir ziehen, entweder eine Karte ziehen, die wir gesehen haben, oder eine Karte ziehen, die wir nicht gesehen haben, und dass wir dies rekursiv definieren können.

Schließlich die Antwort auf die Frage, wie viele wir nach Zügen nicht gesehen haben, .n - E [ X 2 n$2n$$n-E[X_{2n}]$

Ich glaube, das ist richtig, aber es muss eine einfachere Lösung geben.

Jede Hilfe wäre sehr dankbar.

Hinweis: Bei jedem Zug ist die Wahrscheinlichkeit, dass eine Karte nicht ausgewählt wird, . Und da wir mit Ersatz zeichnen, können wir davon ausgehen, dass jede Zeichnung unabhängig von den anderen ist. Die Wahrscheinlichkeit, dass eine Karte in Zügen nicht ausgewählt wird, ist also ... 2$\frac{n-1}{n}$$2n$

Danke Mike für den Hinweis.

Das habe ich mir ausgedacht.

Sei eine Bernoulli-Zufallsvariable mit wenn die -Karte noch nie gezogen wurde. Dann ist , aber da für alle , sei .X i = 1 i t h p i = P ( X i = 1 ) = ( n - $X_i$$X_i = 1$$i^{th}$piip=p$p_i = P(X_i=1) = (\frac{n-1}{n})^{2n}$$p_i$$i$$p=p_i$

Nun sei die Anzahl der Karten, die nach Zügen nicht gezogen wurden . 2 $\displaystyle X = \sum_{i=1}^n X_i$$2n$

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

Und das macht es, denke ich.

Hier ist ein R-Code zur Validierung der Theorie.

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