Oczekiwana liczba niewidzialnych kart przy dobieraniu

10

Mamy talię kart. Losujemy z niego karty jednolicie losowo z wymianą. Po losowaniach, jakiej oczekiwanej liczby kart nigdy nie wybrałeś? $n$ $2n$

To pytanie jest częścią 2 problemu 2.12 w

M. Mitzenmacher i E. Upfal, Prawdopodobieństwo i obliczenia: randomizowane algorytmy i analiza probabilistyczna , Cambridge University Press, 2005.

Co więcej, nie jest to zadanie domowe. To samokształcenie i po prostu utknąłem.

Moja dotychczasowa odpowiedź brzmi:

Niech być liczba oddzielnych kart traktowany po th rysować. Następnie: $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))$

Chodzi o to, że za każdym razem, gdy dobieramy, albo dobieramy kartę, którą widzieliśmy, albo dobieramy kartę, której nie widzieliśmy, i że możemy to zdefiniować rekurencyjnie.

$2n$ $n-E[X_{2n}]$

Uważam, że jest to poprawne, ale musi istnieć prostsze rozwiązanie.

Każda pomoc byłaby bardzo mile widziana.

probability expected-value

— Craig Wright
źródło

Symulowałeś to i porównywałeś wyniki?

— Adam,

10

$\frac{n-1}{n}$ $2n$

3

(+1) To dobry początek. Połączenie tego z liniowością oczekiwań prowadzi do ekonomicznego i eleganckiego rozwiązania.

— kardynał

6

Dziękuję Mike za podpowiedź.

Właśnie to wymyśliłem.

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

I to chyba tak.

— Craig Wright
źródło

4

n

$n$

p \approx e^{- 2}

$p \approx e^{-2}$

To może być trochę bardziej skomplikowane. Prawdopodobieństwo, że karta (i) zostanie pominięta, jest takie, jak napisałeś. Jednak gdy wiemy, że karta (i) została pominięta, prawdopodobieństwo braku karty (j) zmienia się. Nie wiem, czy kwestia niezależności zmieni ostateczny wynik, ale komplikuje wyprowadzenie.

— Emil Friedman,

@Emil Friedman: Oczekiwanie jest liniowe niezależnie od tego, czy lata są niezależne, czy nie. Brak niezależności wpływa na wielkości takie jak wariancja, ale nie na oczekiwania.

— Douglas Zare

4

Oto trochę kodu R do weryfikacji teorii.

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
źródło