Problema del collezionista

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Grafico del numero di oggetti, n contro il numero atteso di prove (cioè il tempo) necessarie per raccoglierli tutti, E(T)

Il problema del collezionista (coupon collector's problem in inglese) è un problema di teoria della probabilità e calcolo combinatorio in cui un collezionista intende ottenere tutti gli oggetti di una data collezione (ad esempio, figurine), ma ha modo di espandere la propria raccolta solo tramite estrazioni casuali di un numero finito di copie dalla collezione originale (i pacchetti di figurine).

È possibile formulare il problema come segue: «Se un album contiene n figurine, quanti pacchetti di figurine vanno acquistati in media per poter completare l'album?». Oppure: «Dato un insieme di n elementi distinti, quante estrazioni con ripetizione si prevede di eseguire prima di aver estratto ogni elemento almeno una volta?».Na

Un'analisi formale del problema rivela che il numero atteso di tentativi necessari cresce secondo [1]. Ad esempio, per n = 50 ci vogliono 225[2] tentativi per raccogliere tutte le 50 figurine.

Soluzione[modifica | modifica wikitesto]

Calcolo del valore atteso[modifica | modifica wikitesto]

Sia il tempo T il numero di estrazioni necessarie per ottenere tutte le n figurine, e sia ti il tempo per trovare la i-esima figurina dopo aver raccolto i − 1 figurine. Allora . Si considerino T e ti come variabili casuali . Si osservi che la probabilità di trovare una nuova figurina è . Perciò, è una distribuzione geometrica con valore atteso . Per linearità del valore atteso, si ha:

Qui, Hn è l'n-esimo numero armonico. Utilizzando l'analisi asintotica per i numeri armonici, si ottiene:

dove è la costante di Eulero-Mascheroni.

Quindi, è possibile usare la disuguaglianza di Markov per delimitare l'intervallo di probabilità desiderato:

Quanto sopra può essere modificato leggermente per gestire il caso in cui siano già state raccolte alcune figurine. Sia k il numero di figurine già raccolte, allora:

E per , otteniamo il risultato di partenza.

Calcolo della varianza[modifica | modifica wikitesto]

Sfruttando l'indipendenza delle variabili casuali ti, si ottiene:

poiché (vedi problema di Basilea).

Quindi, è possibile usare la disuguaglianza di Čebyšëv per delimitare l'intervallo di probabilità desiderato:

Stime agli estremi[modifica | modifica wikitesto]

È possibile derivare un limite superiore diverso a partire dalla seguente osservazione. Rappresentiamo con l'evento per cui l'-esima figurina non è stata trovata nelle prime estrazioni. Allora:

Pertanto, per , si ottiene .

.

Note[modifica | modifica wikitesto]

  1. ^ In questo articolo, con "log" ci si riferisce al logaritmo naturale piuttosto che a un logaritmo di base diversa. L'uso di Θ si riconduce alla notazione O grande.
  2. ^ E(50) = 50(1 + 1/2 + 1/3 + ... + 1/50) = 224,9603, il numero di tentativi previsto per collezionare le 50 figurine. L'approssimazione per questo valore atteso risulta in questo caso in .

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]