Esercizio - tempo atteso per vedere HH, HT e HHH nei lanci di una moneta

Soluzione

Si definiscono gli stati come la lunghezza del più lungo prefisso della sequenza cercata che coincide con la fine dei lanci fatti, e per ogni stato l'attesa del numero di lanci ancora da fare.

1a. $HH$. Stati: $0$ (nessun progresso, o ultimo lancio $T$), $1$ (ultimo lancio $H$). Sia $E_0$, $E_1$ l'attesa dei lanci mancanti.

• Da $0$: si lancia (costo $1$); con probabilità $\frac12$ esce $H$ e si passa a $1$, con $\frac12$ esce $T$ e si resta in $0$: $E_0=1+\frac12E_1+\frac12E_0$, cioè $E_0=2+E_1$.
• Da $1$: si lancia; con $H$ si ha $HH$ e si finisce, con $T$ si torna a $0$: $E_1=1+\frac12\cdot0+\frac12E_0$, cioè $E_1=1+\frac{E_0}2$.

Si sostituisce: $E_0=2+1+\frac{E_0}2$, quindi $\frac{E_0}2=3$ e $E[N_{HH}]=E_0=6$.

1b. $HT$. Stessi stati, ma il lancio $H$ da stato $1$ mantiene lo stato $1$ (l'ultimo lancio è ancora $H$): $E_1'=1+\frac12\cdot0+\frac12E_1'$, da cui $E_1'=2$. Da $0$: $E_0'=1+\frac12E_1'+\frac12E_0'$, cioè $E_0'=2+E_1'=4$. Quindi $E[N_{HT}]=4$.

2. Perché $HH$ aspetta di più. In $HH$, dopo aver visto $H$ un $T$ azzera tutto il progresso: si torna a $0$. In $HT$, dopo $H$ un altro $H$ non fa perdere nulla: si resta in "ultimo lancio $H$". Un'altra lettura: due occorrenze di $HH$ possono sovrapporsi ($HHH$ contiene due $HH$) e perciò le occorrenze arrivano a gruppi; per avere la stessa frequenza media ($\frac14$ per posizione) i gruppi devono essere più radi, con un'attesa iniziale più lunga.

3. $HHH$. Stati $0,1,2$ (numero di $H$ finali): da ogni stato un $T$ riporta a $0$, un $H$ avanza.

• $E_2=1+\frac12\cdot0+\frac12E_0$;
• $E_1=1+\frac12E_2+\frac12E_0$;
• $E_0=1+\frac12E_1+\frac12E_0\Rightarrow E_0=2+E_1$.

Sostituendo $E_2=1+\frac{E_0}2$ in $E_1$: $E_1=1+\frac12+\frac{E_0}4+\frac{E_0}2=\frac32+\frac34E_0$. Poi $E_0=2+\frac32+\frac34E_0$, cioè $\frac14E_0=\frac72$ e $E_0=14$.

In generale $E[N_{H^k}]=2^{k+1}-2$ ($k=1$: $2$; $k=2$: $6$; $k=3$: $14$).

4. Simulazione.

import random
def attesa(pat, T=100000):
    tot = 0
    for _ in range(T):
        s, c = "", 0
        while not s.endswith(pat):
            s += random.choice("HT"); c += 1
        tot += c
    return tot / T
print(attesa("HH"), attesa("HT"), attesa("HHH"))   # circa 6, 4, 14

Risultato. $E[N_{HH}]=6$, $E[N_{HT}]=4$, $E[N_{HHH}]=14$; in generale $E[N_{H^k}]=2^{k+1}-2$.

Verifica Python: sistema lineare risolto con Fraction per i pattern $HH,HT,HHH,HTH$ ($6,4,14,10$); simulazioni $5{,}99,\ 3{,}99,\ 13{,}96$.