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 479 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 453 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.