Newsgroup: it.hobby.enigmi
Titolo: lancio monetina

Ciao ragazzi, da giorni mi arrovello con un calcolo di probabilità,
ovvero, con quale probabilità in 100 lanci di una monetina non truccata si
vedrà almeno una serie di almeno 5 teste? Avevo fatto un ragionamento
semplicissimo ma temo che sia errato, mi son detto: la probabilità di 5
teste consecutive su 5 lanci è 1/2^5 = 1/32, bene, su 100 lanci ho 96
serie di 5 lanci in praticada 1 a 5, da 2 a 6, da 3 a 7 etc. e quindi la
probabilità che esca almeno una serie di 5 consecutive non dovrebbe essere
96*1/32 che diventerebbe persino maggiore di 1 lasciandomi alquanto
confuso?
Chiedo aiuto a voi che mi pare di numeri di capiate ben più di me.
Ovviamente il discorso si estende a un numero diverso di lanci totali dai
100 supposti e ad una serie consecutiva diversa da 5.
Da qualche parte ho letto che la probabiiltà sarebbe 81% ma non so proprio
come arrivarci.
Da notare che dico ALMENO 5 consecutivi, epr cui una serie di 9 andrebbe
benissimo per intenderci.
Grazie, ciao
Archimede
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it


Diversa è la situazione se richiedi la probabilità di avere almeno
5 teste, ma che siano consecutive.
Ciao, Nino

Mi accorgo adesso di aver risposto fischi per fiaschi... :-(
La mia risposta vale per una serie di 10, non di 100 lanci...
Adesso non ho tempo, se non ti verrà data la risposta da qualcun altro,
ti risponderò domani.
Nino

 andrebbe benissimo per intenderci.
Casi possibili:
sono tutte le sequenze di 100 T e C, cioè le disposizioni con ripetizione di 
due elementi presi a 100 a 100 pari a 2^100.
Casi favorevoli:
intanto stabiliamo che, tolta la sequenza TTTTT, gli altri lanci possono dar 
luogo ad un numero di sequenze diverse pari alle disposizioni con 
ripetizione di due elementi presi a 95 a 95.
In ciascuna di queste sequenze la cinquina TTTTT può assumere le posizioni 
da 1..5 fino a 96..100, cioè 96 posizioni diverse.
Quindi i casi favorevoli sono
96*2^95
Dunque:
Probabilità = 2^100 / 96*2^95 = 2^5 / 96 = 1/3
-- 
Ciao, plinius
----------------------------------------------
(Se vuoi scrivermi, fai a meno dell'indirizzo)

 andrebbe benissimo per intenderci.
Nel post precedente avevo detto:
Casi possibili:
sono tutte le sequenze di 100 T e C, cioè le disposizioni con ripetizione di
due elementi presi a 100 a 100 pari a 2^100.
*sono giusti*
Casi favorevoli:
intanto stabiliamo che, tolta la sequenza TTTTT, gli altri lanci possono dar
luogo ad un numero di sequenze diverse pari alle disposizioni con
ripetizione di due elementi presi a 95 a 95.
In ciascuna di queste sequenze la cinquina TTTTT può assumere le posizioni
da 1..5 fino a 96..100, cioè 96 posizioni diverse.
Quindi i casi favorevoli sono
96*2^95
*sono sbagliati*
Dunque:
Probabilità = 2^100 / 96*2^95 = 2^5 / 96 = 1/3
*ho invertito numeratore e denominatore*
*così il risultato mi è sembrato attendibile*
*e ho postato una cavolata*
In realtà nel calcolare i casi favorevoli ho incluso una quantità di 
disposizioni uguali.
Bisogna escogitare un sistema più efficiente per calcolare i casi favorevoli 
e, se ci riesco, posterò quello che riesco a trovare.
Intanto sperimentalmente, con un programmino, ho visto che la frequenza di 
una sequenza di 5 risultati uguali su 100 estrazioni è intorno al 97% (la 
metà se tengo buone sole le sequenze di T o solo quelle di C)
Per altre sequenze ottengo:
sequenza di  6 T o  6 C       80-81%
   "         7 T o  7 C       52-55%
   "         8 T o  8 C       30-32%
   "         9 T o  8 C       15-18%
   "        10 T o 10 C        7- 9%
ecc.


Vi ringrazio e comincio a schiarirmi le idee, vi sarei grato però se mi
sapeste indicare anche dove il mio ragionamento era fallace mannaggia a me
e alle mie cellule ingrigite più che grigie :(


 mannaggia a me e alle mie cellule ingrigite più che grigie :(
Se lanciando una moneta ho probabilita 1/2 di avere T, non è vero che
lanciandola 10 volte ho probabilità di avere almeno una T pari a 1/2*10
che verrebbe, come nel tuo caso, superiore ad 1.
Devo invece calcolare in quanto modi posso avere il risultato delle 10
estrazioni (casi possibili) e sono 2^10
Tra questi senza T ce n'è uno solo CCCCCCCCCC, mentre 2^10-1 contengono
almeno una T
quindi la probabilità di avere almeno una T lanciando 10 volte la monetina è
(2^10-1)/(2^10) = 1023/1024 = 99,90% circa.
Nel problema che poni bisogna seguire lo stesso percorso ma non è semplice
calcolare quante delle 2^100 sequenze di 100 contengano almeno una sequenza 
TTTTT senza incorrere nell'errore che ho fatto io prima di conteggiare 
alcune sequenze 2 volte.


 alcune sequenze 2 volte.
Ti ringrazio per la spiegazione che mostra come il mio approccio di base
fosse sbagliato, ora capisco come l'unica difficoltà effettiva sia proprio
capire quali sequenza conteggiare e come conteggiarle con un algoritmo.
Ho provato a considerare una sequenza CTTTTT e a vederla sposarsi dalla
posizione 1 alla posizione 95, in questa maniera escluderei di conteggiare
5 teste all'interno di una stringa più lunga (visto che parto con una
croce) ma non so come escludere ancora nei 2^94 casi associati a ciascuna
sequenza, quelli che a loro volta contengano una stringa di almeno 5 teste
consecutive e credo sia questo il nocciolo della questione.


Archimede!
ti posto una domanda più facile, così capisci anche l'errore che già ti è 
stato indicato.
qual'è la probabliità che su 10 lanci esca sempre Testa?
Questo roblema si risolve sapendo la probabilità che esca testa in un lancio 
1/2
quindi    p^10 = (1/2)^10
1/2 * 1/2 *1/2 *.......
cioè =  1 / 1024
tutto questo è vero perchè i lanci non sono influenzat il'uno dall'altro e 
quindi possono essere considerati
ognuno indipendente dagli altri.
guardando il tuo problema ti renderai cnoto che la difficoltà sta solo 
nell'enumerare i casi possibili...
quindi usando combinazioni / disposizioni / permutazioni .... questi sono 
gli strumnti matematici che permettono di risolverlo.
Non mi dilungo vistoche già altri hanno dato la strada per la soluzione.
Ciao
T

 come arrivarci.
Ciao,
oltre all'approccio "simulativo" proposto da Plinius (dove calcoli le
probabilità in base ai risultati di un numero sufficientemente alto di
prove) e la solita "brute force", ci sarebbe anche un altro metodo, direi
"ricorsivo", per calcolare il numero di combinazioni favorevoli (quelle con
sequenze di T).
Naturalmente, facendo poi il numero di combinazioni favorevoli diviso il
numero di combinazioni possibili ottieni la probabilità.
Supponi che si stiano cercando sequenze di minimo 2 T in 3 lanci di una
monetina.
Scriviamo [3, 2, 2] dove il primo numero indica il numero di lanci N, il
secondo i risultati possibili 'z' (T o C, cioè 2), il terzo la lunghezza
minima 'k' della sequenza.
Si ha ovviamente [3, 2, 2] --> 3 casi possibili (TTT, TTC, CTT)
Procedendo empiricamente si hanno cioè:
[2, 2, 2] --> 1
[3, 2, 2] --> 3
[4, 2, 2] --> 8
Si vede facilmente che il numero delle combinazioni favorevoli è dato dal
doppio delle favorevoli relative al numero di lanci precedente più la somma
delle precedenti k=2 "eccedenze" (tipo Tartaglia).
[2, 2, 2] --> 1
[3, 2, 2] --> 3 = (1x2) + 1
[4, 2, 2] --> 8 = (3x2) + 2
[5, 2, 2] --> 19 = (8x2) + 3
[6, 2, 2] --> 43 = (19x2) + 5
[7, 2, 2] --> 94 = (43x2) + 8
e così via.
Nel caso in questione, con sequenza di 5 T, si nota che:
[5, 2, 5] --> 1
[6, 2, 5] --> 3
[7, 2, 5] --> 8
[8, 2, 5] --> 20
[9, 2, 5] --> 48
Questi dati sono facilmente estrapolabili con un programmino.
In questo caso il numero delle combinazioni favorevoli è dato dal doppio
delle favorevoli relative al numero di lanci precedente più la somma delle
precedenti k=5 eccedenze. Cioè:
[5, 2, 5] --> 1
[6, 2, 5] --> 3 = (1x2) + 1
[7, 2, 5] --> 8 = (3x2) + 2
[8, 2, 5] --> 20 = (8x2) + 4
[9, 2, 5] --> 48 = (20x2) + 8
[10, 2, 5] --> 112 = (48x2) + 16 dove 16 = 8 + 4 + 2 + 1 + 1
[11, 2, 5] --> 255 = (112x2) + 31 dove 31 = 16 + 8 + 4 + 2 + 1
Provo ad allargare il discorso.
Supponiamo di avere un'urna con 3 palle A, B, C, e di cercare quante
sequenze di minimo 3 palle A consecutive possano uscire in N estrazioni con
reinserimento.
Empiricamente:
[3, 3, 3] --> 1
[4, 3, 3] --> 5
[5, 3, 3] --> 21
[6, 3, 3] --> 81
cioè:
[3, 3, 3] --> 1
[4, 3, 3] --> 5 = (1x3) + 2
[5, 3, 3] --> 21 = (5x3) + 6
[6, 3, 3] --> 81 = (21x3) + 18 con 18 = (6+2+1)*2
[7, 3, 3] --> 295 = (81x3) + 52 con 52 = (18+6+2)*2
[8, 3, 3] --> 1037 = (295x3) + 152 con 152 = (52+18+6)*2
Analizzando questo caso ci si rende conto che non basta sommare le k
precedenti eccedenze, ma occorre moltiplicare tale somma per z - 1.
Questa cosa sfugge se si tiene conto solo dei casi con z=2 (la monetina) che
chiaramente fa moltiplicare la somma per 1, mantenendo invariato il
risultato.
Inoltre mentre con z = 2 si raddoppiava, con z = 3 si dovrà ovviamente
triplicare.
Provo a generalizzare una formula ricorsiva:
Sia C=[N, z, k] il numero C di casi favorevoli in N numero di lanci, z casi
possibili per ciascun lancio, k la lunghezza della sequenza minima
(ovviamente con k<=N).
Inoltre sia p(N, k) la somma delle k "eccedenze precedenti", all'Nmo lancio.
Allora [N, z, k] = ( [N-1, z, k] * z ) + ( p(N-k, k) + p(N-(k-1), k) + ....
+ p(N-1, k) )*(z-1)
Magari ci sarà qualcosa di più semplice e sintetico, che a me sfugge.
Cmq solo facendo altre prove in maniera empirica si potrà dire se
questa roba è coerente o meno.
Ciao
Francesco

 [9, 2, 5] --> 48
Ho fatto un folgio excel con colonna A i numeri da 1 a 100, colonna B come
segue:
B1 0
B2 0
B3 0
B4 0
B5 1
B6 =SOMMA(B1:B5)
B7 =SOMMA(B2:B6) e cosě via
in C
nulla fino a C4
C5 0
C6 =D5*2
C7 = D6*2
in D nulla fino a D4 poi
D5 1
D6 =C6+B6
D7 = C7+B7 e via dicendo
in questa maniera si costruisce il reticolo di numeri secondo la logica
che hai proposto ed effettivametne  prendendo il risultato della cella
D100 e dividendolo per 2^100 ottengo il mitico 0,81011 ovvero l'81% che
cercavo (invano) di ricostruire.
Grazie a tutti soprattutto per avermi dato le indicazioni base su come
procedere e per la spolverata alle poche nozioni di statistica in mio
possesso.


 + p(N-1, k) )*(z-1)
Ciao Francesco, complimenti!
Stavo guardando anch'io il problema (e non mi trovavo con le eccedenze...)
Con la formula che hai proposto, diventa facile trovare la risposta alla
domanda di Archimede
" con quale probabilità in 100 lanci di una monetina non truccata si
vedrà almeno una serie di almeno 5 teste?"
La risposta è:
Casi favorevoli 1,02694E+30
Casi possibili  1,26765E+30        (2^100)
Prob. circa 81,01%
Nino 

 vedrà almeno una serie di almeno 5 teste?
Altro approccio, con un mio vecchio pallino: le catene di Markov
Per quanto interessa il nostro problema, l'unica cosa che ci interessa
sapere in ogni momento è solo quante teste consecutive sono uscite negli
ultimi lanci. Possiamo dire che gli "stati" possibili del sistema sono solo
6:
T0 = ..C         (l'ultimo lancio è stato una croce)
T1 = ..CT        (dopo l'ultima croce è uscita UNA testa)
T2 = ..CTT
T3 = ..CTTT
T4 = ..CTTTT
T5 = ..CTTTTT
Se arriviamo in T5 allora è inutile continuare, perché abbiamo raggiunto lo
scopo (tecnicamente T5 è uno stato assorbente).
Qual è la probabilità di finire dopo n passi nello stato T5 partendo da Ti
(i=0,1,2,3,4,5)?
La chiamiamo Pn(i)
Ovviamente
P1(0)=0
P1(1)=0
P1(2)=0
P1(3)=0
P1(4)=1/2
P1(5)=1
perché solo partendo da T4 si ha il 50% di probabilità di terminare al primo
lancio. continuando:
P2(0)=1/2*P1(0)+1/2*P1(1)=0
P2(1)=1/2*P1(0)+1/2*P1(2)=0
P2(2)=1/2*P1(0)+1/2*P1(3)=0
P2(3)=1/2*P1(0)+1/2*P1(4)=1/4
P2(4)=1/2*P1(0)+1/2*P1(5)=1/2
P2(5)=1
P3(0)=1/2*P2(0)+1/2*P2(1)=0
P3(1)=1/2*P2(0)+1/2*P2(2)=0
P3(2)=1/2*P2(0)+1/2*P2(3)=1/8
P3(3)=1/2*P2(0)+1/2*P2(4)=1/4
P3(4)=1/2*P2(0)+1/2*P2(5)=1/2
P3(5)=1
P4(0)=1/2*P3(0)+1/2*P3(1)=0
P4(1)=1/2*P3(0)+1/2*P3(2)=1/16
P4(2)=1/2*P3(0)+1/2*P3(3)=1/8
P4(3)=1/2*P3(0)+1/2*P3(4)=1/4
P4(4)=1/2*P3(0)+1/2*P3(5)=1/2
P4(5)=1
in generale, partendo da un certo stato, al 50% finiamo nello stato
successivo e al 50% finiamo in T0 (se stiamo in T5 al 100% ci restiamo
perché non ci interessa lanciare ancora)
Con un foglio excel o per ricorsione la coda è semplice da calcolare
Alla fine abbiamo che P100(0)=~.8101096
-- 
Ciao, Silv:o)

 Francesco
Prova fatta!
Funziona perfettamente e tutti i risultati teorici tendono a coincidere con 
le simulazioni. Complimenti per l'analisi eccellente!
Ora provo a semplificare la formula di calcolo.
Limitandomi a considerare l'ipotesi di 2 esiti possibili ("T"/"C"), per 
snellire la formula chiamerò X[N,k] il numero delle combinazioni di N 
elementi che contengono una sequenza di k "T" e E[N,k] l'eccedenza da 
sommare a 2*X[N-1,k] per ottenere X[N,k].
Cominciamo con k=2
Sappiamo che ciascuna eccedenza è uguale alla somma delle 2 precedenti
E[N,2]=E[N-1,2]+E[N-2,2]
X[N,2] = 2*X[N-1,2]+E[N,2] = 2*X[N-1,2]+E[N-1,2]+E[N-2,2]
ma poiché
E[N,2]=X[N,2]-2*X[N-1,2]
possiamo esprimere le eccedenze in funzione dei valori X[...,k] precedenti
X[N,2] = 2*X[N-1,2] + X[N-1,2] - 2*X[N-2,2]
                    + X[N-2,2] - 2*X[N-3,2]
X[N,2] = 3*X[N-1,2] - X[N-2,2] - 2*X[N-3,2]
Possiamo fare la stessa operazione per k=3, k=4, ecc. ed in generale 
ricaviamo che:
X[N,k] = 3*X[N-1,k] - X[n-2,k] - X[N-3,k] - ...... - X[N-k,k] - 2*X[N-k-1,k]
che è più maneggevole da calcolare in un foglio elettronico ed anche da 
esprimere:
"Ciascun termine è uguale al triplo del precedente, detratti ulteriori k 
termini di cui l'ultimo raddoppiato."


 vedrà almeno una serie di almeno 5 teste?
Proviamo a contare le possibili serie che NON REALIZZANO le 5 teste 
consecutive in n lanci. Le indicheremo con F5(n). Ovviamente per n<5 tutte 
le 2^n sequenze possibili sono di quel tipo:
F(0) = 1 = {}
F(1) = 2 = {T,C}
F(2) = 4 = {CC,CT,TC,TT}
F(3) = 8
F(4) = 16
le sequenze di F(5) sono tutte e sole
- le 16 di F(4) precedute da C
- le  8 di F(3) precedute da TC
- le  4 di F(3) precedute da TTC
- le  2 di F(1) precedute da TTTC
- le  1 di F(0) precedute da TTTTC (ovvero la sola sequenza TTTTC)
quindi F(5)=F(4)+F(3)+F(2)+F(1)+F(0)=31
e le sequenze che REALIZZANO 5 teste in 5 lanci sono 2^5 - F(5) = 32-31 = 1 
come è giusto che sia.
I numeri F(n)=F(n-1)+..+F(n-5) non sono altro che una generalizzazione dei 
numeri di Fibonacci
[btw sono gli stessi numeri 1,1,2,4,8,16,31,.. che aveva trovato Francesco 
Di Matteo per le "eccedenze"]
Generalizzando, le sequenze che realizzano 5 teste sono:
A(n) = 2^n - F(n)
e la probabilità richiesta vale A(100)/2^100 che è il valore già trovato per 
altre vie
-- 
Ciao, Silv:o) 

 Ciao, Silv:o)
Ciao Silvio,
molto "istruttiva" questa tua soluzione (come sempre), e anche bella, perchè
va al cuore del problema e calcola direttamente la probabilità, sorvolando
davvero tutti i complicati calcoli combinatori.
Un saluto,
Francesco