Jumlah kartu tak terlihat yang diharapkan saat menggambar kartu

Kami memiliki setumpuk kartu . Kami mengambil kartu dari seragam secara acak dengan penggantian. Setelah 2 n menarik apa yang diharapkan jumlah kartu tidak pernah dipilih?$n$$2n$

Pertanyaan ini adalah bagian 2 dari masalah 2.12 di

M. Mitzenmacher dan E. Upfal, Probabilitas dan Komputasi: Algoritma Acak dan Analisis Probabilistik , Cambridge University Press, 2005.

Juga, untuk apa nilainya, ini bukan masalah pekerjaan rumah. Ini belajar mandiri dan saya hanya terjebak.

Jawaban saya sejauh ini adalah:

Biarkan menjadi jumlah kartu berbeda yang terlihat setelah undian ke- i . Kemudian:$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))$

Idenya di sini adalah bahwa setiap kali kita menggambar, kita menggambar kartu yang telah kita lihat atau menggambar kartu yang belum kita lihat, dan kita dapat mendefinisikan ini secara rekursif.

Akhirnya, jawaban untuk pertanyaan, berapa banyak yang telah kita tidak terlihat setelah menarik, akan n - E [ X 2 n ] .$2n$$n-E[X_{2n}]$

Saya percaya ini benar, tetapi harus ada solusi yang lebih sederhana.

Bantuan apa pun akan sangat dihargai.

Petunjuk: Pada setiap pengundian yang diberikan, probabilitas bahwa kartu tidak dipilih adalah . Dan karena kita menggambar dengan penggantian, saya berasumsi kita dapat mengatakan bahwa masing-masing undian tidak bergantung pada yang lain. Jadi probabilitas bahwa kartu tidak dipilih dalamundian2nadalah ...$\frac{n-1}{n}$$2n$

Terima kasih Mike atas petunjuknya.

Inilah yang saya pikirkan.

$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$

Dan itu menurut saya.

Berikut adalah beberapa kode R untuk memvalidasi teori.

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