Ожидаемое количество невидимых карт при вытягивании карт из колоды размером

У нас есть колода из карт. Мы вытягиваем карты из него равномерно наугад с заменой. Какое ожидаемое количество карт никогда не выбирается после 2n тиражей?2 $n$$2n$

Этот вопрос является частью 2 проблемы 2.12 в

М. Митценмахер и Э. Упфал, Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ , издательство Кембриджского университета, 2005.

Кроме того, для чего это стоит, это не проблема домашней работы. Это самообучение, и я просто застрял.

Пока что мой ответ:

Пусть $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))$

Идея в том, что каждый раз, когда мы рисуем, мы либо рисуем карту, которую видели, либо карту, которую не видели, и что мы можем определить это рекурсивно.

Наконец, ответ на вопрос, сколько мы не видели после $2n$ розыгрышей, будет $n-E[X_{2n}]$ .

Я считаю, что это правильно, но должно быть более простое решение.

Любая помощь будет принята с благодарностью.

Подсказка: на любом данном розыгрыше вероятность того, что карта не выбрана, равна . И поскольку мы рисуем с заменой, я предполагаю, что мы можем сказать, что каждая ничья не зависит от других. Таким образом, вероятность того, что карта не выбрана в розыгрышах, равна ...2 $\frac{n-1}{n}$$2n$

Спасибо, Майк, за подсказку.

Это то, что я придумал.

Пусть будет случайной величиной Бернулли, где если карта никогда не была разыграна. Тогда , но поскольку одинаково для всех , пусть .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$

Теперь пусть будет количеством карт, которые не были разыграны после розыгрышей. 2 $\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$

И это все, я думаю.

Вот некоторый R-код для проверки теории.

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