Probabilità di completare un album di figurine

cenzo1
Salve! Mi sono posto un problema che non riesco ad affrontare. Vi chiedo una mano.
Il problema è il seguente:

Quante bustine occorre comperare (ogni bustina contiene 6 figurine) per avere una probabilità del 95% di completare un album di 734 figurine ?

Ho assunto le seguenti ipotesi:
- l'album è inizialmente vuoto;
- l'acquisto delle bustine avviene in una sola e unica occorrenza;
- non vi sono figurine "rare": ogni figurina ha eguale probabilità di far parte di una bustina;
- la bustina è composta estraendo a caso 6 figurine tra le 734, dunque è anche possibile che sia presente qualche "doppione" all'interno della bustina.

Ho iniziato a ragionare in tal modo:
1. Per calcolare il numero di bustine richiesto mi è sufficiente calcolare quante figurine occorrono e poi dividere per 6.
2. Per calcolare quante figurine occorrono per avere una probabilità P=0.95 di completare l'album si potrebbe immaginare di fissare il numero di figurine N (>734) e calcolare quanto vale la probabilità P(N) di completare l'album. Potrei poi ricavare N in funzione di P (da fissare pari a 0.95) come funzione inversa.
3. Fisso N>734. La probabilità di completare l'album con tali figurine corrisponde alla probabilità di avere 734 figurine diverse e le restanti N-734 come "doppioni". Credo sia opportuno utilizzare la definizione classica di probabilità come rapporto tra casi favorevoli e casi totali.
I casi totali sono $ 734^N $ (disposizioni con ripetizione, dato che ognuna delle N figurine estratte può appartenere ad una delle 734 diverse figurine).

Il problema è che non riesco ad enumerare in modo corretto i casi favorevoli.

Ho provato a ragionare anche su numeri più piccoli, cercando di rispondere al seguente problema equivalente:
Quanti lanci di un dado occorrono per avere una probabilità del 95% che escano tutte le 6 facce ?
Però mi blocco allo stesso punto.

Credete che il problema sia ben posto?

Suggerimenti per la risoluzione ?

Grazie mille!

cenzo

Risposte
clrscr
Io ho ragionato così...vediamo se sta in piedi :) .

Prendo il caso dei dadi che si adatta facilmente al caso più generale.

Voglio calcolare la probabilità che con $k>=6$ lanci escano tutte le facce.
Questo significa che nei primi $k-1$ lanci, sono apparse $5$ delle possibili facce, mentre nel lancio k-esimo è apparsa la faccia mancante.

Usiamo i casi favorevoli su quelli possibili:

Casi favorevoli:
$((k-1),(5)) 6*5*4*3*2*5^(k-1-5)*1$

dove $6*5*4*3*2*5^(k-1-5)*1$ indica che i primi 5 numeri sono tutti diversi mentre i k-1-5 possono anche ripetere i precedenti, infine c'è il numero mancante "1". $((k-1),(5))$ indica il fatto che i le facce posso essere sparse tra i k-1 lanci.

Casi possibili:
$6^k$

Da cui:
$P[\text{al k-esimo lancio sono apparse tutte le facce}]=(((k-1),(5)) 6*5*4*3*2*5^(k-1-5)*1)/6^k$

Rggb1
Come al solito mi viene in mente la distribuzione bernoulliana. Proviamo a trasformare il problema del dado con $P(faccia)=1/6$ cercando di stabilire in quante prove la probabilità di NON ottenere mai quella faccia viene meno del 5%:
$P=((n),(k))p^k*(1-p)^(n-k)$ ovvero visto che k è zero $P=(1-p)^n$ per un opportuno n.

A me viene n=17. In soldoni, la probabilità che NON esca mai un dato numero (faccia del dado) in 17 lanci è meno del 5%, quindi la probabilità che esca almeno una volta è oltre il 95%. E questo vale ovviamente per tutte le facce del dado.

Sto cercando un metodo alternativo (basato possibilmente sul contare) per una verifica: mi rendo conto di aver fatto assunzioni che magari sono forzate, ci sarà pure qualcosa di meglio.

cenzo1
"clrscr":
Io ho ragionato così...vediamo se sta in piedi :) .

Prendo il caso dei dadi che si adatta facilmente al caso più generale.

Voglio calcolare la probabilità che con $k>=6$ lanci escano tutte le facce.
Questo significa che nei primi $k-1$ lanci, sono apparse $5$ delle possibili facce, mentre nel lancio k-esimo è apparsa la faccia mancante.

Usiamo i casi favorevoli su quelli possibili:

Casi favorevoli:
$((k-1),(5)) 6*5*4*3*2*5^(k-1-5)*1$

dove $6*5*4*3*2*5^(k-1-5)*1$ indica che i primi 5 numeri sono tutti diversi mentre i k-1-5 possono anche ripetere i precedenti, infine c'è il numero mancante "1". $((k-1),(5))$ indica il fatto che i le facce posso essere sparse tra i k-1 lanci.

Casi possibili:
$6^k$

Da cui:
$P[\text{al k-esimo lancio sono apparse tutte le facce}]=(((k-1),(5)) 6*5*4*3*2*5^(k-1-5)*1)/6^k$


Grazie clrscr per la pronta risposta!

Non avevo pensato alla possibilità di ragionare come te, per avere al k-esimo lancio la faccia mancante.
Il tuo ragionamento mi sembra convincente.
Però ci deve essere qualcosa che non funziona.
Se uso la tua formula per k>10 ottengo valori di probabilità > 1.
Ad esempio per k=12 si avrebbe P=2.39, che non è possibile.
(spero di non aver sbagliato il calcolo..)
Credo che i casi favorevoli siano sopravvalutati.

Comunque ti ringrazio perchè mi hai fatto vedere un modo di ragionare che non conoscevo. :)

Rggb1
Trovare il numero di casi favorevoli e quello dei casi possibili è un metodo ottimo per calcolare una probabilità "one-shot". In questo problema mi sembra meglio cercare una opportuna distribuzione, e quella bernoulliana delle prove ripetute mi sembra la migliore candidata.

cenzo1
"Rggb":
Come al solito mi viene in mente la distribuzione bernoulliana. Proviamo a trasformare il problema del dado con $P(faccia)=1/6$ cercando di stabilire in quante prove la probabilità di NON ottenere mai quella faccia viene meno del 5%:
$P=((n),(k))p^k*(1-p)^(n-k)$ ovvero visto che k è zero $P=(1-p)^n$ per un opportuno n.

A me viene n=17. In soldoni, la probabilità che NON esca mai un dato numero (faccia del dado) in 17 lanci è meno del 5%, quindi la probabilità che esca almeno una volta è oltre il 95%. E questo vale ovviamente per tutte le facce del dado.

Sto cercando un metodo alternativo (basato possibilmente sul contare) per una verifica: mi rendo conto di aver fatto assunzioni che magari sono forzate, ci sarà pure qualcosa di meglio.


Ciao Rggb,
il tuo approccio mi sembra molto più semplice, tuttavia mi domando se risponda al problema posto oppure ad un altro problema.
Mi spiego. La tua soluzione risponde alla domanda: qual è il numero di lanci tale che si abbia una probabilità del 95% che una certa faccia del dado esca almeno una volta?
Il fatto che una certa faccia esca almeno una volta con probabilità 95% non garantisce però che escano TUTTE le facce.

cenzo1
Ho provato a fare una simulazione con R per capire quanti lanci del dado sono necessari.
Dalla simulazione sembrerebbe che ci vogliono 27 lanci per avere una probabilità del 95% che escano tutte le facce.

Posto il codice che ho usato in R (spero di non avere commesso orrori)
> count<-0 #distribuzione del numero di lanci del dado
> for (i in 1:100000) {  #faccio 100000 simulazioni
+   x<-rep(0,6)
+   n<-0 #conta il numero di lanci necessari per ogni simulazione
+   while (sum(x)<6) { #continuo ad estrarre mentre non sono uscite tutte le facce
+     a<-ceiling(runif(1,0,6)) #estraggo un numero intero compreso tra 1 e 6
+     x[a]<-1 #contrassegno la faccia uscita
+     n<-n+1 #aggiorno il numero di lanci
+   }
+   count[i]<-n #memorizzo il numero di lanci necessari per la simulazione corrente
+ }
> quantile(count,0.95) #calcolo il quantile 0.95 della distribuzione simulata
95% 
 27 

Mi interessa comunque sapere come risolvere il problema analiticamente.
Non capisco perchè l'approccio di clrscr -che mi sembra corretto- non funziona.

itpareid
non vorrei sparare una castronata, ma questo dovrebbe essere uno degli esempi in cui si utilizza la legge degli eventi rari

cenzo1
Ciao Sergio,
se ho interpretato correttamente il tuo codice, il secondo programma che hai scritto calcola quanti lanci (di 6 dadi) ci vogliono, in media, per ottenere un lancio in cui sono presenti tutte le 6 facce. E risulta circa 65.

Il problema posto però è (o mi sembra) diverso. Richiede quanti lanci di UN dado devo ripetere per avere una probabilità del 95% che siano uscite tutte le 6 facce in tutta la sequenza.
Cioè, comincio a lanciare un dado e registro quello che esce. Mi fermo quando in tutta la sequenza compare almeno una volta ciascuna faccia. Come notava clrscr, mi fermo quando all'ultimo lancio esce per la prima volta l'ultimo numero che ancora mancava. Ovviamente, in generale, saranno presenti dei "doppioni" per quanto riguarda le altre facce (quelle diverse dal'ultima che completa la sequenza).

Se chiamiamo N il numero di questi lanci che ci vogliono, questa dovrebbe essere una variabile aleatoria che ha una certa distribuzione di probabilità ignota. Il problema quindi, in pratica, chiede il quantile 0.95 di tale v.a.

Rggb1
"Sergio":
La probabilità di ottenere 6 lanciando un dato è $p=1/6$. Di quanti lanci ho bisogno per avere almeno il 95% di probabilità di fare 6?
La probabilità di non fare 6 è $q=5/6$. Se i lanci sono 2, $q^2=0.69$, quindi $p=0.31$. Se sono 3 ecc.
Ad esempio (il problema di De Méré): qual è la probabilità di fare 6 in 4 lanci? $q^4=0.482$, $1-q=0.518$.

Non mi torna: la P. di fare 6 in quattro lanci non si calcola con la binomiale? E' data da 1-P(mai_sei)
Per esempio, la tua simulazione calcola che mediamente occorrono sei lanci; cosa ha a che fare con la probabilità del 95%? C'è relazione con la curva di Gauss? :?
Passiamo a sei dadi. La probabilità di ottenere 6 numeri determinati in un lancio si ottiene ricorrendo alla distribuzione multinomiale (non binomiale: in termini di urne e palline, è come estrarre 6 palline da 6 urne contenenti ciascuna 6 palline di 6 colori diversi): $(n!)/(1!1!1!1!1!1!)(1/6)^6=n!(1/6)^6=0.0154321$.
La probabilità di non ottenere quei 6 numeri è $q=0.9845679$.
Impostiamo quindi la disuguaglianza $q^n<=0.35$ e otteniamo $n>=67.5$, quindi 68 lanci.

Anche io stavo cercando di passare alla multinomiale (di cui la binomiale è caso generale). Ancora: così come hai impostato di dove viene il 95%?

Umby2
"Sergio":


e mi pare che ci siamo.
Sbaglio secondo voi?


puoi dirmi quanto ti esce la simulazione fatta con i 6 dadi ?

Mi aspettavo un valore intorno al 64,8

cenzo1
"Umby":
[quote="Sergio"]

e mi pare che ci siamo.
Sbaglio secondo voi?


puoi dirmi quanto ti esce la simulazione fatta con i 6 dadi ?

Mi aspettavo un valore intorno al 64,8[/quote]

A me simulando il codice di Sergio esce 64.5.
Però, come ho scritto tre post addietro, il codice di Sergio non risolve il problema posto.

Ciao

cenzo1
"Sergio":
Comincerei da un caso più semplice.
..per calcolare i lanci necessari per avere almeno il 95% di probabilità di fare 6, si deve risolvere la disuguaglianza $q^n<=0.35$: $n log(q)<=log(0.35)$, essendo $log(q)<0$, $n>=(log(0.35))/(log(q))=5.76$. Occorrono sei lanci.

Passiamo a sei dadi. La probabilità di ottenere 6 numeri determinati in un lancio si ottiene ricorrendo alla distribuzione multinomiale (non binomiale: in termini di urne e palline, è come estrarre 6 palline da 6 urne contenenti ciascuna 6 palline di 6 colori diversi): $(n!)/(1!1!1!1!1!1!)(1/6)^6=n!(1/6)^6=0.0154321$.
La probabilità di non ottenere quei 6 numeri è $q=0.9845679$.
Impostiamo quindi la disuguaglianza $q^n<=0.35$ e otteniamo $n>=67.5$, quindi 68 lanci.


Per quanto riguarda la variante del problema proposto da Sergio, sintetizzerei così:

1. Caso di un solo dado
In media occorrono 6 lanci per avere un 6 (o qualsiasi altra faccia)
Per avere una probabilità del 95% di avere quella faccia occorrono $n>=(log(0.05))/(log(5/6))=16.4$, quindi 17 lanci
Per avere una probabilità del 50% (mediana) di avere quella faccia occorrono $n>=(log(0.5))/(log(5/6))=3.8$, quindi 4 lanci

2. Caso in cui ogni volta lancio 6 dadi assieme
In media occorrono 64.5 lanci per avere una sestina tutta diversa (da simulazione)
Per avere una probabilità del 95% di avere tale sestina occorrono $n>=(log(0.05))/(log(0.9845679))=192.6$, quindi 193 lanci
Per avere una probabilità del 50% (mediana) di avere tale sestina occorrono $n>=(log(0.5))/(log(0.9845679))=44.6$, quindi 45 lanci

Rggb1
Stessi miei calcoli: 17 prove per il 95% che esca almeno una volta un dato numero (già spiegato), 193 per avere il 95% che mi capiti la sestina almeno una volta. Sto appunto cercando di sintetizzare il tutto: voglio trovare un metodo per ricavare una prova bernoulliana da poter usare (ci sto ancora pensando) :-k

Rggb1
Butto nel mucchio un'altra idea (senza prove bernoulliane), partendo sempre dall'esperimento più semplice del dado.

Il numero di disposizioni possibili dei risultati dopo $n$ prove è $6^n$
Considero un numero di prove maggiore di 6:
- su $n$ possibili ho $5^n$ disposizioni senza l'uno
- ancora, $5^n$ senza il due
e via così.
Pertanto la probabilità che dopo $n$ prove NON siano usciti tutti è
$p=6*(5^n)/6^n = (5^n)/(6^n-1)$

Devo trovare il valore di $n$ per il quale $p$ è minore od uguale a 0.05 - mi viene 27.

Problema: per $n<10$ mi viene un numero maggiore di 1... E' giusto: fra le disposizioni "senza l'uno" ve ne sono anche "senza il due" e via così.

Passo la palla, quindi: come togliere i doppioni? :-k

Rggb1
Sergio, abbiamo postato allo stesso tempo? ;)

La tua soluzione tiene conto dei doppioni?
[MOD]
Se non ho calcolato male, servono almeno 95 lanci per avere la probabilità richiesta... che mi sembrano parecchi.

Rggb1
Ritorno sull'argomento.
Il numero di disposizioni possibili dei risultati dopo $n$ prove è $6^n$
Considero un numero di prove maggiore di 6:
- su $n$ possibili ho $5^n$ disposizioni senza l'uno
- ancora, $5^n$ senza il due
e via così.

Ovviamente non tenevo conto dei doppioni, fra le disposizioni senza "2" ve ne sono senza "1" e viceversa... dunque:

- Le disposizioni senza "1" sono in totale $5^n$
- Le disposizioni senza "2" sono in totale $5^n$, però questo numero comprende quelle anche senza "1" che ho già contato. Queste combinazioni sono quelle dei rimanenti quattro numeri e quindi sono $4^n$.
- Le disposizioni senza "3" sono, ancora in totale, $5^n$. Ovviamente ho in questo numero sia quelle senza "1" sia quelle senza "2" (e naturalmente senza entrambi) che ho contato prima. Proviamo a vedere quante sono: senza "1" sono $4^n$ e fra queste ve ne sono senza "2", in totale $3^n$.
...
Proseguo in questo modo, e riassumendo ho
- $5^n$ numeri senza "1"
- fra i rimanenti, $5^n - 4^n$ numeri senza "2"
- fra i rimanenti, $5^n - 4^n - 3^n$ numeri senza "3"
- fra i rimanenti, $5^n - 4^n - 3^n - 2^n$ numeri senza "4"
- fra i rimanenti, $5^n - 4^n - 3^n - 2^n - 1$ numeri senza "5"
... e qui mi sono decisamente incartato, o ho sbagliato ragionamento oppure i passaggi non sono corretti: quanti sono quelli senza "6"? :(

Chi mi dà una mano adesso?

Umby2
"Rggb":


Chi mi dà una mano adesso?


La formula è alquanto complessa, almeno cosi' sembra...
per ora ti passo qualche dato, ma temo che questa strada non ci porti molto lontano.. :roll:

6Lanci 720 Disposizioni dove sono presenti tutti i 6 numeri
7-15120
8-191520
9-1905120
10-16435440
11-129230640
12-953029440

Umby2
"Sergio":


> gioco(26)\$p
[1] 0.9479827
> gioco(27)\$p
[1] 0.9565864



Se ho ben capito, hai simulato le varie disposizioni, fin quando hai stabilito che dopo 27 lanci, ottieni una probabilita' superiore a questo "limite" che ci siamo posti pari al 95%

Avevo raggiunto esattamente gli stessi tuoi risultati trovando una formula, che mi calcolasse (quindi in modo istantaneo) questa percentuale.
La stessa formula mi dice (ad esempio) che se sposto il limite al 99%, avro' bisogno di ben 36 lanci per raggiungere questo obiettivo.

La formula è stata fatta per un dado a 6 facce, se si riuscisse a generalizzarla per un dado a n facce, diciamo che ci avviciniamo alla soluzione.

Rggb1
Scusate, provo a fare un backtrace. Contiamo tutti i modi in cui posso disporre (permutazioni) i numeri 1..6 in $n$ lanci.

- Per un solo numero c'è una sola permutazione, e un totale di 6 per i sei differenti numeri: 1111... 2222... eccetera.
- Per due numeri, ho $2^n$ permutazioni, e un totale di 15 combinazioni differenti dei due numeri: 12.. 13.. 14.. 15.. 16.. 23.. eccetera.
- Per tre numeri, ho $3^n$ permutazioni, e un totale di 20 combinazioni differenti dei tre numeri: 123.. 124.. 125.. 126.. 134.. eccetera.
- Per quattro numeri, ho $4^n$ permutazioni, e un totale di 14 combinazioni differenti dei quattro numeri: 1234.. 1235.. 1236.. 1245.. eccetera.
- Per cinque numeri, ho $5^n$ permutazioni, e un totale di 6 combinazioni differenti dei cinque numeri: 12345.. 12346.. eccetera.
- Per tutti i sei numeri, ho $6^n$ permutazioni, e una sola combinazione dei sei numeri: 123456.
[Nota: la sequenza di numeri 1 15 20 14 6 1 vi dice nulla? ;)]

I numeri "senza tutte le cifre" dovrebbero essere quindi $6*5^n-14*4^n-20*3^n-15*2^n-6$. E cercando $n$ tale che il rapporto fra questi e il numero totale sia uguale o inferiore al 5% mi vengono 27 lanci (e MAI il rapporto è negativo per $n>=6$). E ancora, per avere il rapporto uguale o inferiore al 1% mi tornano 36 lanci (il rapporto è circa 0.0085)

Se non è corretto, mi sapete dire dove sbaglio?

cenzo1
"Rggb":
Scusate, provo a fare un backtrace.
...
I numeri "senza tutte le cifre" dovrebbero essere quindi $6*5^n-14*4^n-20*3^n-15*2^n-6$. E cercando $n$ tale che il rapporto fra questi e il numero totale sia uguale o inferiore al 5% mi vengono 27 lanci (e MAI il rapporto è negativo per $n>=6$). E ancora, per avere il rapporto uguale o inferiore al 1% mi tornano 36 lanci (il rapporto è circa 0.0085)

Se non è corretto, mi sapete dire dove sbaglio?


Per n=6 risulterebbe che i numeri "senza tutte le cifre" dovrebbero essere quindi $6*5^n-14*4^n-20*3^n-15*2^n-6=20860$
e quindi i casi favorevoli essere $6^6-20680=25796$
Ciò però non è corretto in quanto con n=6 i casi favorevoli sono 6!=720
Con n=6 ti uscirebbe una probabilità molto alta, pari a 0.55
Con n=7 addirittura diminuirebbe la probabilità (a 0.31)

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.