Esercizio - album di 20 figurine, acquisti attesi per completarlo

Soluzione

Struttura. Sia $T_i$ il numero di acquisti necessari per passare da $i-1$ a $i$ figurine distinte. Quando se ne hanno $i-1$, un acquisto è "nuovo" con probabilità $p_i=\frac{20-(i-1)}{20}=\frac{21-i}{20}$, indipendente dal passato: $T_i$ è geometrica di parametro $p_i$ (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 →) e $E[T_i]=\frac1{p_i}=\frac{20}{21-i}$. Per linearità l'attesa del tempo che passa tra $a$ e $b$ distinte si ottiene sommando le $E[T_i]$ relative.

1. Completare l'album. $$E[T]=\sum_{i=1}^{20}\frac{20}{21-i}=20\Big(\frac1{20}+\frac1{19}+\dots+1\Big)=20H_{20}.$$ $H_{20}=3{,}59774$, quindi $E[T]=20\cdot3{,}59774\approx71{,}95$ acquisti.

2. Quindici distinte. Servono $T_1,\dots,T_{15}$, cioè $i=1..15$, con $E[T_i]=\frac{20}{21-i}$ che va da $\frac{20}{20}=1$ a $\frac{20}{6}$: $$\sum_{i=1}^{15}\frac{20}{21-i}=20\,(H_{20}-H_5)=20\,(3{,}59774-2{,}28333)=26{,}29.$$ Restano $T_{16},\dots,T_{20}$, con $E=\frac{20}5+\frac{20}4+\frac{20}3+\frac{20}2+\frac{20}1=4+5+6{,}667+10+20=\frac{137}3\approx45{,}67$ (e $26{,}29+45{,}67=71{,}95$). Le ultime cinque figurine pesano il $63\%$ del totale.

3. Prime dieci distinte. $\sum_{i=1}^{10}\frac{20}{21-i}=20\,(H_{20}-H_{10})=20\,(3{,}59774-2{,}92897)=13{,}38$ acquisti, il $19\%$ del totale: all'inizio quasi ogni figurina è nuova.

4. Simulazione.

import random
def acquisti(n):
    viste, c = set(), 0
    while len(viste) < n:
        viste.add(random.randrange(n)); c += 1
    return c
print(sum(acquisti(20) for _ in range(20000)) / 20000)   # circa 72

Risultato. $E[T]=20H_{20}\approx71{,}95$; $26{,}29$ acquisti per quindici distinte e $\frac{137}3\approx45{,}67$ per le ultime cinque.

Verifica Python: somma esatta con Fraction $=\frac{279175675}{3879876}=71{,}9548$; simulazione con $20\,000$ album: $72{,}20$.