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

10

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?n2n

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:Xii

E[Xi]=k=1nk(knP(Xi1=k)+nk1nP(Xi1=k1))

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á .2nnE[X2n]

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

Qualquer ajuda seria muito apreciada.

Craig Wright
fonte
Você simulou e comparou resultados?
Adam

Respostas:

10

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 é ... 2nn1n2n


fonte
3
(+1) Isso dá um bom primeiro começo. Combinar isso com linearidade de expectativa leva a uma solução econômica e elegante.
cardeal
6

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 - 1XiXi=1ithpiip=pipi=P(Xi=1)=(n1n)2npiip=pi

Agora seja o número de cartas que não foram sorteadas após draws. 2 nX=i=1nXi2n

EntãoE[X]=E[i=1nXi]=i=1nE[Xi]=i=1np=np

E é isso que eu acho.

Craig Wright
fonte
4
(+1) Observe também que, para grande, . p e - 2npe2
Dilip Sarwate
Pode ser um pouco mais complicado que isso. A probabilidade de falta do cartão (i) é como você escreveu. No entanto, uma vez que sabemos que a carta (i) foi perdida, a probabilidade de falta da carta (j) muda. Não sei se a questão da independência mudará o resultado final, mas complica a derivação.
Emil Friedman
@Emil Friedman: A expectativa é linear, independentemente de as somas serem independentes ou não. A falta de independência afeta quantidades como a variação, mas não a expectativa.
Douglas Zare
4

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