So che mme volete bbene...

[panurgo]

...perciò vi piazzo questa senza fare soverchi tentativi per verificare che non sia già in uno degli altri $19105$ messaggi dei $2002$ argomenti di questo forum

Se lanciamo $n$ volte una moneta “onesta” qual è la probabilità che non escano mai due teste di seguito?

PS: se la trovate in uno dei post precedenti, fatemi sapere in quale...

[delfo52]

provo a ragionare.
se la moneta è onesta, su n estrazioni, ci sono n/2 Teste.
Per ottemperare il dettato, occorre che a ogni T segua una Croce (probabilità 1/2)
perciò, direi: (1/2) elevato alla n/2
Che per n=10 fa 1/32; per n=20 1/1024
SE&Stupidaggini

[Gianfranco]

Pare che ad ogni lancio successivo sopravviva un numero di Fibonacci di nodi...

maiTT.png (56.15 KiB) Visto 1128 volte

...e muoia un numero di Fibonacci di nodi.
Dal che si deduce che ogni potenza di 2 è uguale alla somma di due numeri di Fibonacci.
Ma va? Non ci credo!

[panurgo]

Gianfranco, occhio che ogni "morto" continua a figliare in rosso per avere un grafo binomiale completo...

[Gianfranco]

Gianfranco, occhio che ogni "morto" continua a figliare in rosso per avere un grafo binomiale completo...

Sì, ma ogni "morto" va avanti in automatico con le successive potenze di 2. Giusto?
P.S. Hai ragione, il discorso sulle potenze di due - Fibonacci è una bufala.
Ma per il calcolo della probabilità richiesta interessano i superstiti.

[panurgo]

Esatto...

[Gianfranco]

Allora, ad ogni nuovo nodo verde si applica questa struttura (ricorsivamente o frattalmente?)

maiTT_2.png (30.93 KiB) Visto 1102 volte

[panurgo]

In modo più formale, possiamo considerare le successioni di lanci come parole di lunghezza $n$ tratte dall’alfabeto di due lettere $\left\{\text{C},\text{T}\right\}$: tali parole sono $\epsilon,\text{C},\text{T},\text{CC},\text{TC},\text{CT},\text{TT},\ldots$, dove $\epsilon$ è la parola di lunghezza zero; come è ovvio, le parole di lunghezza $n$ sono $2^n$: dobbiamo contare le parole che non contengono $\text{TT}$ per calcolarne la frequenza.
Se una parola non termina con $\text{T}$ possiamo aggiungere sia $\text{C}$ sia $\text{T}$; viceversa, se una parola termina con $\text{T}$, possiamo aggiungere solo $\text{C}$. Siano $c_n$ e $t_n$ il numero di parole valide che terminano con $\text{C}$ e $\text{T}$ rispettivamente, e $a_n=c_n+t_n$ il numero totale di parole valide: vale la seguente relazione ricorsiva

$\left\{\begin{array}{lC}
c_n=c_{n-1}+t_{n-1} \\
t_n=c_{n-1} \\
c_0=1 \\
t_0=0
\end{array}\right.$

(se una parola non termina con $\text{T}$ possiamo aggiungere sia $\text{C}$ sia $\text{T}$, ovvero le $c_{n-1}$ parole che terminano per $\text{C}$ diventano $c_{n-1}$ parole che terminano per $\text{C}$ e $c_{n-1}$ parole che terminano per $\text{T}$; viceversa, se una parola termina con $\text{T}$, possiamo aggiungere solo $\text{C}$, ovvero le $t_{n-1}$ parole che terminano per $\text{T}$ diventano $t_{n-1}$ parole che terminano per $\text{C}$ ; la parola di lunghezza zero NON termina con $\text{T}$, ecco perché $c_0=1$ e $t_0=0$).
Dal fatto che $t_{n-1}=c_{n-2}$ ricaviamo $c_n=c_{n-1}+c_{n-2}$: osserviamo che la parola valida di una lettera che termina con $\text{C}$ è $\text{C}$ quindi $c_1=1$. La relazione ricorsiva per $c_n$ è dunque

$\left\{\begin{array}{lC}
c_n=c_{n-1}+c_{n-2} \\
c_0=1 \\
c_1=1
\end{array}\right.$

Ma $t_n=c_{n-1}=c_{n-2}+c_{n-3}$ e quindi $t_n=t_{n-1}+t_{n-2}$; come sopra, $\text{T}$ è la parola valida di una lettera che termina con $\text{T}$ quindi la relazione ricorsiva di $t_n$ è

$\left\{\begin{array}{lC}
t_n=t_{n-1}+t_{n-2} \\
t_0=0 \\
t_1=1
\end{array}\right.$

Concludiamo osservando che $a_n=c_n+t_n=\left(c_{n-1}+t_{n-1}\right)+\left(c_{n-2}+t_{n-2}\right)=a_{n-1}+a_{n-2}$ e quindi

$\left\{\begin{array}{lC}
a_n=a_{n-1}+a_{n-2} \\
a_0=1 \\
a_1=2
\end{array}\right.$

Questa è la definizione ricorsiva dei numeri di Fibonacci con un offset di due, $F_{n+2}$: in base al Principio di Indifferenza assegniamo dunque la probabilità

$\displaystyle \Pr\left(\overline{\text{TT}}\middle|n\wedge\top\right)=\frac{F_{n+2}}{2^n}$

cioè

$\displaystyle \frac{1}{1},\frac{2}{2},\frac{3}{4},\frac{5}{8},\frac{8}{16},\ldots$

[Gianfranco]

In modo più formale, possiamo considerare le successioni di lanci come parole di lunghezza $n$ tratte dall’alfabeto di due lettere $\left\{\text{C},\text{T}\right\}$: tali parole sono $\epsilon,\text{C},\text{T},\text{CC},\text{TC},\text{CT},\text{TT},\ldots$, dove $\epsilon$ è la parola di lunghezza zero; come è ovvio, le parole di lunghezza $n$ sono $2^n$: dobbiamo contare le parole che non contengono $\text{TT}$ per calcolarne la frequenza.
Se una parola non termina con $\text{T}$ possiamo aggiungere sia $\text{C}$ sia $\text{T}$; viceversa, se una parola termina con $\text{T}$, possiamo aggiungere solo $\text{C}$. Siano $c_n$ e $t_n$ il numero di parole valide che terminano con $\text{C}$ e $\text{T}$ rispettivamente, e $a_n=c_n+t_n$ il numero totale di parole valide: vale la seguente relazione ricorsiva

$\left\{\begin{array}{lC}
c_n=c_{n-1}+t_{n-1} \\
t_n=c_{n-1} \\
c_0=1 \\
t_0=0
\end{array}\right.$

Bella dimostrazione, come sempre.
E anche chiara, per me: l'ho capita e questo mi rende felice. Grazie.
Ma... vorrei continuare con i miei ragionamenti "informali" parzialmente visivi e darmi una dimostrazione della relazione ricorsiva che hai scritto.
Spero di aver tempo di scriverli, chissà quando.

[Pasquale]

Questa discussione mi era sfuggita, ma appare evidente che aumentando il numero di lanci entro i quali si vorrebbe che non venissero sortite due teste consecutive, l'evento diviene sempre meno probabile e con tendenza allo zero.
L'approccio matematico puro non è nelle mie corde, ma non potendo rinunciare ad un po' di passatempo, ho comunque proceduto a delle verifiche col mezzo delle simulazioni.
Chi mi ha dato una mano con il lancio della moneta ed il conteggio dei risultati? Indovina un po' ?

Seguono valori medi approssimati di probabilità di successo, ottenuti su 1.000.000 di ripetizioni per ogni serie di lanci, con uleriori ripetizioni delle ripetizioni, onde cavarne una media.

Seguono dunque i risultati sui successi osservati, espressi con valori medi:

2 lanci: 75 %
3 lanci: 62,5 %
10 lanci: 14 %
20 lanci: 1,7 %
30 lanci: 0,2 %
40 lanci: 0,02 %
50 lanci: 0,003 %
60 lanci: 0,0003
70 lanci: 0,00004
75 lanci: 0,00002
80 lanci: 0,00001
90 lanci: 0,000002

Aggiungo per completezza che, non avendo avuto a disposizione una moneta da lanciare al momento delle prove da effettuare, sono stato costretto ad affidare il compito all'amico Decimal ed al suo RANDOMIZE, pur se con le sue limitazioni.
Di seguito un esempio velocizzato, con riduzione delle ripetizioni del ciclo FOR-NEXT a 100.000, modificabile a piacere, nei limiti di un'accettabilità circa l'approssimazione dei risultati (quelli sopra sono stati ottenuti con nun ciclo da 1 milione).

!'1=Testa
!'2=Croce
DIM a(2)

INPUT PROMPT "Numero di lanci consecutivi ":n
PRINT

!'ripeti per 10 volte il procedimento di seguito, per ottenere una media
!'dei valori casuali riscontrati

LET med = 0
FOR q=1 TO 10

LET T=0
RANDOMIZE

FOR m=1 TO 100000 !'ripeti l 'esperimento di n lanci per 100000 volte
MAT a=ZER
FOR Lanci=1 TO n
LET a(2)=1+INT(RND*2)
IF a(1)=1 AND a(2)=1 THEN
LET T=T+1
GOTO 50
ELSE
LET a(1)=a(2)
end if
NEXT LANCI
50
NEXT M
LET pu=T/1000 !'probabilità uscita
LET pnu=100-pu !'probabilità di non uscita (cioè quella cercata)
PRINT "probabilità di non sortita di 2 TESTE consecutive su";n;"lanci ="; pnu;"%"
LET med=med+pnu
NEXT Q
PRINT
PRINT "prob. media su";n;"lanci ="; pnu;"%"

PRINT
PRINT "FINE"

END