Lanciamo ripetutamente un dado equo a sei facce.

All'inizio ogni risultato è nuovo. Dopo qualche lancio, invece, iniziamo a vedere facce già uscite.

Continuiamo finché abbiamo osservato almeno una volta:

1 2 3 4 5 6

La domanda è:

Quanti lanci servono in media per vedere tutte e sei le facce?

Il problema è una versione del classico coupon collector problem: ogni prova ci consegna uno fra n tipi equiprobabili e vogliamo sapere quanto dobbiamo aspettare per raccoglierli tutti.

Sei lanci sono il minimo, non la media

Per completare la raccolta servono almeno sei lanci.

Ma sei lanci bastano soltanto se tutte le facce risultano diverse.

Una sequenza come:

1 4 2 6 3 5

completa la raccolta esattamente al sesto lancio.

Una sequenza come:

1 4 2 6 3 3

no: dopo sei lanci manca ancora il 5.

Quindi:

$$ T_6 \ge 6 $$

ma non possiamo concludere:

$$ E[T_6] = 6 $$

Il problema non è raccogliere sei risultati qualunque. È raccogliere sei risultati distinti.

Spezziamo l'attesa in fasi

Il modo più semplice di risolvere il problema non è cercare direttamente la distribuzione completa di T_6.

Conviene chiedersi quanto dura, in media, ciascuna fase.

Chiamiamo:

X_1 = lanci necessari per vedere la prima faccia distinta
X_2 = lanci aggiuntivi per passare da 1 a 2 facce distinte
X_3 = lanci aggiuntivi per passare da 2 a 3 facce distinte
...
X_6 = lanci aggiuntivi per passare da 5 a 6 facce distinte

Il tempo totale è:

T_6
=
X_1 + X_2 + X_3 + X_4 + X_5 + X_6

Questa decomposizione trasforma un problema apparentemente complicato in sei tempi di attesa geometrici.

La prima faccia arriva subito

Al primo lancio qualunque faccia è nuova.

Quindi:

$$ X_1 = 1 $$

con certezza e:

$$ E[X_1] = 1 $$

Da una faccia distinta a due

Supponiamo di aver visto soltanto il 4.

Al lancio successivo abbiamo:

1 faccia già vista
5 facce nuove

La probabilità di ottenere una nuova faccia è quindi:

$$ p = 5/6 $$

Possiamo ripetere più volte il 4, ma ogni nuovo lancio ha sempre probabilità 5/6 di farci passare alla fase successiva.

X_2 è quindi un tempo di attesa geometrico con:

E[X_2]
=
1/p
=
6/5
=
1,2

lanci.

Quando abbiamo già due facce

Ora quattro delle sei facce sono ancora nuove.

Quindi:

$$ p = 4/6 $$

e:

E[X_3]
=
6/4
=
1,5

Le ultime fasi diventano sempre più lente

Procedendo nello stesso modo:

facce già viste   facce nuove   p(nuova)   attesa media
0                 6             6/6        1
1                 5             5/6        6/5
2                 4             4/6        6/4
3                 3             3/6        6/3
4                 2             2/6        6/2
5                 1             1/6        6

L'ultima faccia è la più costosa.

Quando ne abbiamo già viste cinque, ogni lancio ha soltanto probabilità:

$$ 1/6 $$

di completare la raccolta.

Il tempo medio della sola ultima fase è quindi:

6 lanci

Sommiamo i valori attesi

Per linearità del valore atteso:

E[T_6]
=
E[X_1]
+ E[X_2]
+ E[X_3]
+ E[X_4]
+ E[X_5]
+ E[X_6]

quindi:

E[T_6]
=
1
+ 6/5
+ 6/4
+ 6/3
+ 6/2
+ 6

Portando tutto a frazione:

E[T_6]
=
147/10
=
14,7

Servono quindi, in media, 14,7 lanci per osservare almeno una volta tutte le facce di un dado equo.

Non abbiamo bisogno di moltiplicare probabilità fra le fasi per ottenere questo risultato. La linearità del valore atteso permette di sommare le attese dei singoli tempi.

La formula generale

Con n categorie equiprobabili, quando ne abbiamo già raccolte k, ne restano:

$$ n-k $$

La probabilità che la prossima prova aggiunga una categoria nuova è:

$$ (n-k)/n $$

L'attesa media per avanzare di una categoria è quindi:

$$ n/(n-k) $$

Se indicizziamo invece le categorie ancora mancanti con:

$$ m = n, n-1, ..., 1 $$

otteniamo:

E[T_n]
=
n/n
+ n/(n-1)
+ ...
+ n/2
+ n/1

cioè:

$$ E[T_n] = n(1 + 1/2 + 1/3 + ... + 1/n) $$

La somma:

H_n
=
1 + 1/2 + ... + 1/n

si chiama numero armonico.

Quindi la formula compatta è:

$$ E[T_n] = n H_n $$

Per esempio:

n=1 -> E[T_1] = 1
n=2 -> E[T_2] = 3
n=6 -> E[T_6] = 147/10 = 14,7

Perché l'ultima categoria pesa così tanto?

Con sei facce, il tempo medio necessario per arrivare da zero a cinque facce distinte è:

1 + 6/5 + 6/4 + 6/3 + 6/2
=
8,7

Poi, per la sola ultima faccia, servono in media altri:

6

lanci.

Quindi l'ultima categoria rappresenta da sola:

6/14,7
≈
40,82%

dell'attesa totale.

È il meccanismo fondamentale del coupon collector: all'inizio quasi ogni osservazione aggiunge informazione nuova; alla fine la maggior parte delle osservazioni sono duplicati.

Un album vero può avere una regola diversa: sei figurine senza duplicati nella bustina

Il modello classico del coupon collector estrae un oggetto alla volta, con reinserimento fra le estrazioni. Codenotti e Resta mostrano un caso più vicino agli album di figurine: 200 figurine totali, bustine da 6, senza duplicati all'interno della stessa bustina.

Supponiamo che nell'album ne abbiamo già 195 e ne manchino soltanto 5.

La probabilità che una nuova bustina contenga solo doppioni è:

$$ \frac{195}{200} \frac{194}{199} \frac{193}{198} \frac{192}{197} \frac{191}{196} \frac{190}{195}. $$

Equivalentemente:

$$ P(\text{solo doppioni})

\frac{\binom{195}{6}}{\binom{200}{6}} \approx85{,}74%. $$

Quindi la probabilità di trovare almeno una delle cinque figurine mancanti è soltanto:

$$ 1-\frac{\binom{195}{6}}{\binom{200}{6}} \approx14{,}26%. $$

Questo non sostituisce il coupon collector classico: è un modello diverso perché le sei figurine della stessa bustina non sono estrazioni indipendenti con reinserimento.

Il punto generale rimane identico: quando la collezione è quasi completa, una grande parte delle nuove osservazioni non porta categorie nuove. Ma prima di usare una formula dobbiamo verificare le regole reali di generazione dei coupon.

Fonte di contesto: Bruno Codenotti e Giovanni Resta, La logica dell'incertezza, cap. 1, “L'album delle figurine”. Il prodotto e la forma combinatoria sono verificati indipendentemente.

14,7 non significa "entro 15 quasi sicuramente"

Il valore atteso è una media di lungo periodo, non una scadenza.

Possiamo completare la raccolta in soli sei lanci oppure aspettarne molti di più di quindici.

Per capire quanto sia probabile aver già finito entro m lanci, possiamo tornare all'inclusione-esclusione.

Dopo m lanci di un dado esistono:

$$ 6^m $$

sequenze equiprobabili.

Vogliamo quelle in cui compaiono tutte e sei le facce.

Per una faccia fissata, per esempio il 6, le sequenze che non la contengono sono:

$$ 5^m $$

Se scegliamo due facce da escludere, restano:

$$ 4^m $$

sequenze, e così via.

Con inclusione-esclusione:

P(T_6 <= m)
=
1/6^m
[
6^m
- C(6,1)5^m
+ C(6,2)4^m
- C(6,3)3^m
+ C(6,4)2^m
- C(6,5)1^m
]

La formula generale è:

P(T_n <= m)
=
sum(j=0..n)
(-1)^j C(n,j)
((n-j)/n)^m

Questa volta non stiamo calcolando una media: stiamo calcolando la probabilità esatta di avere già completato la raccolta.

Alcuni valori per il dado

Per sei facce:

entro 6 lanci   ->  1,5432%
entro 10 lanci  -> 27,1812%
entro 13 lanci  -> 51,3858%
entro 15 lanci  -> 64,4213%
entro 20 lanci  -> 84,7988%
entro 23 lanci  -> 91,0765%
entro 36 lanci  -> 99,1542%

Questi numeri mostrano bene la differenza fra:

$$ E[T_6] = 14,7 $$

e:

$$ P(T_6 \le 15) \approx 64,42% $$

Dopo 15 lanci abbiamo ancora circa il:

35,58%

di probabilità di non aver visto tutte le facce.

Il primo numero di lanci per cui la probabilità di completamento supera il 50% è:

13

La mediana del tempo di raccolta non coincide quindi con la media 14,7.

Un controllo immediato sul caso minimo

Per completare tutto in esattamente sei lanci, ogni faccia deve comparire una volta.

Le sequenze favorevoli sono le permutazioni delle sei facce:

6!
=
720

Le sequenze totali sono:

6^6
=
46.656

Quindi:

P(T_6=6)
=
720/46656
=
5/324
≈
1,5432%

È esattamente lo stesso valore prodotto dalla formula di inclusione-esclusione per:

$$ P(T_6 \le 6) $$

perché prima del sesto lancio completare la raccolta è impossibile.

Lo stesso calcolo in C#

Lo standalone C# associato a questo articolo è:

CouponCollector.cs

L'attesa media si calcola direttamente dalla somma armonica:

static double AttesaCouponCollector(int categorie)
{
    if (categorie <= 0)
        throw new ArgumentOutOfRangeException(nameof(categorie));

    double attesa = 0.0;

    for (int mancanti = 1; mancanti <= categorie; mancanti++)
        attesa += (double)categorie / mancanti;

    return attesa;
}

Console.WriteLine(AttesaCouponCollector(6));

L'output è:

14,7

L'esempio standalone associato all'articolo fa di più:

calcola l'attesa come frazione esatta
calcola P(T_n <= m) con inclusione-esclusione e BigInteger
verifica i gate n=1, n=2 e n=6
esegue anche una simulazione riproducibile con seed fisso

La simulazione non sostituisce il risultato esatto. Serve a vedere il tempo di raccolta come variabile casuale e a confrontare la media osservata con:

$$ 147/10 $$

Quando n cresce

Il numero armonico cresce lentamente.

Vale il confronto:

ln(n)
<=
H_n
<=
1 + ln(n)

quindi:

n ln(n)
<=
E[T_n]
<=
n(1 + ln(n))

L'ordine di grandezza del tempo necessario per raccogliere tutte le categorie è quindi:

n log n

Non è sufficiente moltiplicare n per una costante fissa: l'ultima parte della raccolta diventa progressivamente più lenta.

Il modello ha ipotesi precise

La formula:

$$ E[T_n] = n H_n $$

richiede che ogni prova:

sia indipendente dalle precedenti
produca una delle n categorie
assegni a ogni categoria probabilità 1/n

Se alcune categorie sono più rare di altre, il problema cambia.

L'intuizione resta valida — le categorie rare possono dominare il tempo di completamento — ma non possiamo più usare automaticamente nH_n.

Allo stesso modo, se i risultati vengono estratti senza reinserimento da una popolazione finita, la probabilità di ottenere una categoria cambia dopo ogni estrazione: è un modello diverso.

Il punto pratico

Il coupon collector mostra perché un tempo di attesa complessivo può essere costruito sommando fasi semplici.

Quando abbiamo già raccolto k categorie su n, il prossimo avanzamento ha probabilità:

$$ (n-k)/n $$

ed è quindi governato da una distribuzione geometrica.

La somma delle attese produce:

E[T_n]
=
nH_n

ma la media non descrive da sola la distribuzione: nel caso del dado, 14,7 lanci di media convivono con appena il 64,42% di probabilità di aver completato tutto entro 15 lanci.

Nel prossimo articolo manterremo l'idea del tempo di attesa, ma cambieremo obiettivo: non aspetteremo di vedere tutte le categorie. Chiederemo quante prove servono per raggiungere il successo numero r. È la distribuzione binomiale negativa.