Esercizio - Chebyshev sul collezionista, 50 tipi di figurine

Teoria: Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → (collezionista e Chebyshev); il valore atteso è in Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →. L'esercizio sull'album da 20 figurine, che calcola solo la media, è in Esercizio - album di 20 figurine, acquisti attesi per completarlo.

Testo. Ci sono $n=50$ tipi di figurine, e a ogni acquisto se ne ottiene uno uniforme e indipendente dai precedenti. $T$ è il numero di acquisti necessari per averli tutti.

1. Calcolare $E[T]$ e $\mathrm{Var}(T)$.
2. Limitare $P(T\ge375)$ con Markov e con Chebyshev.
3. Limitarla con l'unione sugli eventi "il tipo $j$ manca dopo $374$ acquisti".
4. Calcolare il valore esatto con un programma e trovare il più piccolo $t$ con $P(T>t)\le0{,}05$ secondo ciascun metodo.

Soluzione

1. Media e varianza. $T=\sum_{i=1}^{50}T_i$, con $T_i$ geometrica di parametro $p_i=\frac{50-i+1}{50}$ (quando si hanno $i-1$ tipi, ne mancano $51-i$), indipendenti (Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →). Da $E[T_i]=1/p_i$ e $\mathrm{Var}(T_i)=(1-p_i)/p_i^2$: $$E[T]=50\sum_{k=1}^{50}\frac1k=50\cdot4{,}4992=224{,}96,\qquad\mathrm{Var}(T)=\sum_{i=1}^{50}\frac{1-p_i}{p_i^2}=3837{,}87,\quad\sigma=61.95.$$ (Il limite $n^2\pi^2/6=4112{,}3$ è appena più grande.)

2. Markov e Chebyshev. Markov: $P(T\ge375)\le\frac{224{,}96}{375}=0{,}600$. Per Chebyshev lo scostamento è $375-224{,}96=150{,}04$: $$P(T\ge375)\le P(|T-E[T]|\ge150{,}04)\le\frac{3837{,}87}{150{,}04^2}=0.1705.$$

3. Unione. Dopo $t$ acquisti il tipo $j$ manca con probabilità $(1-\frac1{50})^t$. Poiché $T\ge375$ vuol dire che dopo $374$ acquisti manca almeno un tipo, $$P(T\ge375)\le50\,(0{,}98)^{374}=0.0262.$$ È circa $6{,}5$ volte meglio di Chebyshev: l'unione sfrutta la forma esponenziale della coda che Chebyshev ignora.

4. Valore esatto e soglie. Sia $D_t$ il numero di tipi distinti dopo $t$ acquisti: $D_t$ passa da $d$ a $d+1$ con probabilità $\frac{50-d}{50}$. Con un programma dinamico su $D_t$ si trova $P(T\le t)=P(D_t=50)$ e quindi $P(T\ge375)=\mathbf{0{,}0259}$. L'unione (0,0262) è quasi esatta, Chebyshev (0,1705) no.

Soglie per $P(T>t)\le0{,}05$:

Con 502 acquisti Chebyshev ne chiede il $47\%$ in più del necessario; l'unione solo l'$1{,}5\%$. Una simulazione di $40000$ collezioni dà media $224{,}7$ e $P(T\ge375)=0{,}0251$.

Risultato. $E[T]=224{,}96$, $\mathrm{Var}(T)=3837{,}87$; $P(T\ge375)$: Markov $0{,}60$, Chebyshev $0{,}171$, unione $0{,}0262$, esatto $0{,}0259$.

Verifica.

n = 50
dp = [0.0] * (n + 1); dp[0] = 1.0
cdf = {}
for t in range(1, 600):                       # dp[d] = P(d tipi distinti dopo t acquisti)
    nuovo = [0.0] * (n + 1)
    for d, p in enumerate(dp):
        if d < n: nuovo[d + 1] += p * (n - d) / n
        nuovo[d] += p * d / n
    dp = nuovo; cdf[t] = dp[n]               # P(T <= t)
print(1 - cdf[374], n * 0.98 ** 374)          # 0.02587 0.02615
print(min(t for t in range(1, 599) if 1 - cdf[t] <= 0.05))   # 341
E = sum(n / (n - i) for i in range(n))
V = sum((i / n) / ((n - i) / n) ** 2 for i in range(n))
print(E, V)                                   # 224.96 3837.87