Probabilità di completare un album di figurine
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
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
"cenzo":
Ribadisco che questa è la probabilità di completare la sequenza in esattamente 12 lanci.
Ok. Avevo inteso che tu cercavi la probabilità dopo il sesto lancio. Ovvero: Ho effettuato 6 lanci, se ho completato l'album mi fermo, se NON ho completato l'album, mi fumo una sigaretta, e mentre sto fumando mi chiedo: Quale è la % che ho tirando la settima volta ? Quindi una % che non teneva conto "del passato" ma che si riferiva al presente, ovvero un attimo prima del tiro. Notavo che questa % aumenta sempre di piu', fino a sfiorare con n --> infinito ad $1/6$.
A questo punto, mi aspetto che la tua strada porti allo stesso risultato (almeno cosi' sembra) della formula proposta da rggb, generalizzata poi da me. Quindi, non ci resta nulla altro da "scoprire".... o mi sfugge qualcosa ?
"Umby":
A questo punto, mi aspetto che la tua strada porti allo stesso risultato (almeno cosi' sembra) della formula proposta da rggb, generalizzata poi da me. Quindi, non ci resta nulla altro da "scoprire"
Credo sia proprio così. C'è solo stato un "misunderstanding", prob. causato da un po' di confusione in miei post precedenti.
Ho riportato su un foglio excel una sintesi dei risultati:
di Cenzo (colonna D e E), e quelli prodotti dalla soluzione di rggb (colonna H).
Come sospettavo.... sono gli stessi.
Album
"Umby":
Ho riportato su un foglio excel una sintesi dei risultati:
Bello! Però hai scritto $n!$ invece di $6^n$ nella colonna potenza di sei
Comunque rifacendo un ragionamento analitico - ne sto preparando la descrizione - la formula mi sembra corretta.
Intanto sto anche scrivendo un programmino di verifica numerica; non è che qualcuno lo ha già fatto, e ha già verificato i risultati dado-sei almeno fino a 10/11? Così magari risparmio tempo.
"Sergio":
Trovata. Ed è anche molto più semplice del conto dei casi sfavorevoli di Rggb
...
$sum_(i=0)^(5)(-1)^i((6),(i))(6-i)^n$
A me sembra UGUALE alla mia... la semplicità è dovuta al fatto che è scritta come sommatoria?
"Sergio":
Quasi uguali. Praticamente uguale la prima versione, ma non la seconda:
$"casi sfavorevoli prima versione"=((6),(5))*5^n-((6),(4))*4^n+((6),(3))*3^n-((6),(2))*2^n+((6),(1))*1^n$
$"casi sfavorevoli seconda versione"=((6),(5))*5^n-1*((6),(4))*4^n+2*((6),(3))*3^n-3*((6),(2))*2^n+4*((6),(1))$
$"casi favorevoli"=((6),(0))6^n-((6),(1))5^n+((6),(2))4^n-((6),(3))3^n+((6),(4))2^n-((6),(5))1^n$
Si, ma come ho già detto in merito alla mia prima soluzione (auto-quoting):
Comunque rifacendo un ragionamento analitico - ne sto preparando la descrizione - la formula mi sembra corretta.
Descrizione che ora eviterò di finire. Lavoro risparmiato
1) la prima versione funzionava (tanto che ho cancellato quel mio messaggio che ho cancellato), ma non appariva evidente la correttezza del procedimento seguito per ricavarla (tanto che avevo scritto quel messaggio che poi ho cancellato e mi avevi detto che avevo trovato una falla);
Infatti: il fatto che i doppioni si "ripetessero" era una considerazione basata sul presupposto (corretto) che ogni gruppo contenesse i successivi e sul conteggio (erroneo) "le combinazioni si ripetono due volte perché ce ne sono due ognuna".
L'ho rifatta, in sintesi è che ogni insieme di combinazioni "contiene" l'inferiore. Va bene, forse mi spiego un tanto al chilo, ora mi guardo la spiegazione di cui hai postato il link.
2) in ogni caso, ci eravamo messi tutti a "reinventare la ruota", in particolare tu a contare i doppioni e io a sommare prodotti di fattoriali, mentre si tratta di un risultato arcinoto e arcidocumentato. Bastava pensare al conto delle funzioni suriettive...
Abbiamo ricavato una formula, "partendo da zero", che è arcinota? Però! Mica male, eh?
"Sergio":
una formulazione che fosse anche semplice e suscettibile di un'implementazione efficiente.
...
Ecco la semplice implementazione in R (senza ottimizzazioni) e un esempio di esecuzione:
> semplice <- function(lanci, facce=6) { + fav <- 0 + for (i in 0:facce-1) + fav <- fav + (-1)^i * choose(facce, i) * (facce - i)^lanci + return(list(fav=fav, p=fav/facce^lanci)) + } > semplice(c(7,10,26,27,115)) \$fav [1] 1.512000e+04 1.643544e+07 1.617085e+20 9.790569e+20 3.071806e+89 \$p [1] 0.05401235 0.27181213 0.94798274 0.95658638 1.00000000
Un'ottima intuizione: complimenti! Comunque penso che è sempre bene avere più "strade" per raggiungere la meta.
Un'ultima domanda, poi non ti scoccio più
Ho provato il tuo codice per facce=734 (l'album). Ci sono problemi di calcolo numerico... non mi meraviglio visti i numeri in gioco!
Come si potrebbe implementare la formula in modo da avere la soluzione ?
Dalla simulazione che ho fatto (anche questa inizia a diventare "pesante" e meno affidabile visto che mi devo accontentare di -relativamente- poche prove) dovrebbe uscire un numero intorno ai 7000 lanci (per avere una prob. di 0.95)
Grazie!
"Sergio":
Ora come ora direi che la cosa migliore sarebbe usare un software particolarmente adatto per il calcolo numerico... senza limiti, come Pari/gp. Non l'ho mai usato per queste cose, ma calcola $743^7000$ senza batter ciglio.
Magari ci pensiamo un po' su, ok?
Grazie per il link.
Per la pizza, siete ufficialmente invitati!
"Sergio":
Punti di vista
Dal mio, abbiamo perso un sacco di tempo per carenza di teoria.
Parlavo soprattutto per me... visto che la mia cultura matematica è limitata, vuol dire che non sono poi così arrugginito, tee-hee
Intendiamoci: la discussione è stata fantastica, non mi era mai capitato di cimentarmi insieme ad altri nella ricerca di una soluzione ed è stata una bellissima esperienza (sarebbe davvero il caso di festeggiarla con una pizza
Concordo sulla pizza, anche se la vedo difficile
Ma sul fatto che trovare risultati già noti, ignorando che lo sono, non ci sia progresso, non sarei così drastico. A me non pareva fosse un risultato banale, e far lavorare la testolina o "incaponirsi su un problema" finché non si trova la soluzione" (come uso dire) mi sembra sia sempre utile.
Almeno ora ho imparato una cosa in più. E visto me la sono "ragionata" da solo, non me la scordo sicuro.
PS. Per calcoli brutali normalmente uso GMP http://gmplib.org/
"Rggb":
Abbiamo ricavato una formula, "partendo da zero", che è arcinota? Però! Mica male, eh?
Direi proprio di no..
anzi, un topic molto bello, proprio per la collaborazione reciproca, e che ci si è arrivati pian piano alla soluzione.
Ho appena letto che Sergio ha risolto anche quello di 700 figurine...
Il mio "povero Cobol" mi andava in overflow per numeri cosi' grandi (non è adatto a questi tipi di calcolo..)
"Sergio":
Quanto a GMP.... ti va di provare? Mi piacerebbe vedere la libreria all'opera...
Se usi PARI/GP l'hai già vista, usa GMP:
http://gmplib.org/#PROJECTS
Vuoi un po' di codice per la risoluzione di questo problema? Non dovrebbe essere difficile, l'ho usato non proprio di recente (calcolo di fattorizzazioni per numeri RSA, bestiale) ma non mi dovrebbe essere difficile.
Puoi provare anche te, ho visto usi Perl, usa Math::BigInt o Math::GMP
Credo di capire il punto, ma per me è (stato) differente. Anzitutto non conoscevo il principio di I-E (e mi mancano tanti altri blablabla di teoria), e magari mi manca anche altra teoria che mi avrebbe potuto farci arrivare. Tutto sommato ho ripreso a studiare da poco...
E quindi ho ripiegato sul metodo classico, che il mio professore di Probabilità&Statistica delle superiori mi ha insegnato: "contare". Anche se sono passati tanti anni i metodi per contare me li ricordo, li ho dovuti anche rispolverare per alcuni esami, e dopo un po' sono arrivato alla soluzione. E a quanto ho capito c'è arrivato anche Umby più o meno allo stesso modo.
Probabilmente ti ho anche sviato, mi hai fatto una osservazione pertinente, ovvero che c'era un passaggio non corretto nel ragionamento: era vero, ed in quel modo non "corrispondeva" al principio di I-E. Ho impiegato due giorni a cercare una soluzione differente, e tornavo sempre lì, finché ho capito l'errore e ho "ricostruito" una dimostrazione.
[Nota: La spiegazione del conteggio data su http://www2.dm.unito.it/paginepersonali ... i/bell.pdf è praticamente uguale, ma MOLTO più elegante della mia che recitava tipo << i gruppi $G_5$ contengono anche tutti i gruppi $G_4$ che a loro volta quack quack ... >> ho già detto che ho carenze, sto studiando]
Lascia a me la chiosa dell'argomento, visto che si è parlato di calcolo, teoria e pizza: "Nulla teoria sine hosteria" (Leopold Mapple in "Terra!" di S. Benni)
E quindi ho ripiegato sul metodo classico, che il mio professore di Probabilità&Statistica delle superiori mi ha insegnato: "contare". Anche se sono passati tanti anni i metodi per contare me li ricordo, li ho dovuti anche rispolverare per alcuni esami, e dopo un po' sono arrivato alla soluzione. E a quanto ho capito c'è arrivato anche Umby più o meno allo stesso modo.
Probabilmente ti ho anche sviato, mi hai fatto una osservazione pertinente, ovvero che c'era un passaggio non corretto nel ragionamento: era vero, ed in quel modo non "corrispondeva" al principio di I-E. Ho impiegato due giorni a cercare una soluzione differente, e tornavo sempre lì, finché ho capito l'errore e ho "ricostruito" una dimostrazione.
[Nota: La spiegazione del conteggio data su http://www2.dm.unito.it/paginepersonali ... i/bell.pdf è praticamente uguale, ma MOLTO più elegante della mia che recitava tipo << i gruppi $G_5$ contengono anche tutti i gruppi $G_4$ che a loro volta quack quack ... >> ho già detto che ho carenze, sto studiando]
Lascia a me la chiosa dell'argomento, visto che si è parlato di calcolo, teoria e pizza: "Nulla teoria sine hosteria" (Leopold Mapple in "Terra!" di S. Benni)
"Rggb":
E a quanto ho capito c'è arrivato anche Umby più o meno allo stesso modo.
Piu' o meno... infatti a pag. 4 era già apparsa la formuletta (anche se con qualche imperfezione...
... )Si ma ora ???
Ci fermiamo qui ?
Considerato che, fin ad ora, non abbiamo "scoperto" nulla di nuovo, continuiamo , no ?
Mi sono incuriosito alla domanda perchè ho visto che è stata visitata numerossissime volte ed ho deciso di intromettermi in una lunga diatriba che ha visto, in realtà, non molti protagonisti. ho visto alcune delle vostre risposte ma non ho letto tutto perchè era troppo (e le troppe idee portano in confusione). A giudicare dall'ultimo messaggio non avete risolto il problema (anche se in realtà non so se in uno dei messaggi intermedi l'avete trovata).
Il problema del completamento dell'album delle figurine e un problema evidentemente classico perchè mi sembrava di averlo già sentito ed in effetti in: Sheldon Ross "Calcolo delle probabilità" APOGEO edizione 2004; il problema (che direi è particolarmente complicato) è affrontato e risolto a pagg. 122-124.
Riassumendo: abbiamo da completare un album con $N$ figurine distinte; ogni figurina esce con uguale probabilità; comprare una alla volta (come nel caso del libro) o tutte in blocco le figurine credo non generi problemi, se nei pacchetti ci possono essere doppioni credo proprio che il problema sia ancora equivalente.
Indicando con $T$ il numero di figurine da comprare per completare l'album (ovvero la T-esime è l'ultima figurina mancante):
$P(T>n)=sum_(i = 1)^(N-1)*((N!)/((N-i)!*i!))*((N-i)/N)^n*(-1)^(i+1)$
dove $n$ deve essere $>0$ e se $n
con $N=734$ figurine $P(T>n)=5%$ (circa) quando $n=7019$ per cui quasi 10 volte la capienza dell'album.
Per il dado $P(T>n)=4,34%$ quando $n=27$
notate che se N è troppo grande si possono avere problemi di approssimazione perchè
i termini della sommatoria oscillano tra positivi e negativi abbassandosi in valore assoluto e se si perde in precisione troppo presto non è garantita la convergenza, in Excel ho avuto qualche problema.
Il problema del completamento dell'album delle figurine e un problema evidentemente classico perchè mi sembrava di averlo già sentito ed in effetti in: Sheldon Ross "Calcolo delle probabilità" APOGEO edizione 2004; il problema (che direi è particolarmente complicato) è affrontato e risolto a pagg. 122-124.
Riassumendo: abbiamo da completare un album con $N$ figurine distinte; ogni figurina esce con uguale probabilità; comprare una alla volta (come nel caso del libro) o tutte in blocco le figurine credo non generi problemi, se nei pacchetti ci possono essere doppioni credo proprio che il problema sia ancora equivalente.
Indicando con $T$ il numero di figurine da comprare per completare l'album (ovvero la T-esime è l'ultima figurina mancante):
$P(T>n)=sum_(i = 1)^(N-1)*((N!)/((N-i)!*i!))*((N-i)/N)^n*(-1)^(i+1)$
dove $n$ deve essere $>0$ e se $n
con $N=734$ figurine $P(T>n)=5%$ (circa) quando $n=7019$ per cui quasi 10 volte la capienza dell'album.
Per il dado $P(T>n)=4,34%$ quando $n=27$
notate che se N è troppo grande si possono avere problemi di approssimazione perchè
i termini della sommatoria oscillano tra positivi e negativi abbassandosi in valore assoluto e se si perde in precisione troppo presto non è garantita la convergenza, in Excel ho avuto qualche problema.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo