Número esperado de cartas não vistas ao desenhar cartas de um baralho de tamanho

Temos um baralho de cartas. Tiramos cartas dele de maneira uniforme e aleatória com a substituição. Após o qual é o número esperado de cartas nunca escolhido?$n$$2n$

Esta pergunta faz parte 2 do problema 2.12 no

M. Mitzenmacher e E. Upfal, Probabilidade e Computação: Algoritmos Aleatórios e Análise Probabilística , Cambridge University Press, 2005.

Além disso, pelo que vale a pena, esse não é um problema de lição de casa. É auto-estudo e estou apenas preso.

Minha resposta até agora é:

Seja o número de cartas distintas vistas após o ésimo draw. Então:$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))$

A idéia aqui é que cada vez que compramos, compramos um cartão que vimos ou compramos um cartão que não vimos e que podemos defini-lo recursivamente.

Finalmente, a resposta para a pergunta, quantas não vimos após empates, será .$2n$$n-E[X_{2n}]$

Acredito que isso esteja correto, mas que deve haver uma solução mais simples.

Qualquer ajuda seria muito apreciada.

Dica: em qualquer sorteio, a probabilidade de uma carta não ser escolhida é . E como estamos desenhando com substituição, presumo que possamos dizer que cada empate é independente dos outros. Portanto, a probabilidade de uma carta não ser escolhida em é ... 2$\frac{n-1}{n}$$2n$

Obrigado Mike pela dica.

Isto é o que eu vim com.

Vamos ser uma variável aleatória Bernoulli onde se o cartão nunca foi desenhado. Então , mas como é o mesmo para todos os , seja .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$

Agora seja o número de cartas que não foram sorteadas após draws. 2 $\displaystyle X = \sum_{i=1}^n X_i$$2n$

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

E é isso que eu acho.

Aqui está um código R para validar a teoria.

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