Corrida de padrões com moeda viciada

• Parte 1: P(HTH aparece antes de HHT) = q/(1 + q) = (1 − p)/(2 − p).

  • Configurar uma cadeia de Markov nos estados de "sufixo útil": S (sem progresso), H, HH, HT. Fato estrutural chave: do estado HH, o padrão HHT certamente vencerá, pois caras nos mantêm em HH e a primeira coroa completa imediatamente HHT antes que HTH possa se formar; então P(HTH primeiro | HH) = 0.
  • Sejam a, b, c a probabilidade de HTH vencer de S, H, HT, respectivamente. Então a = p·b + q·a (então a = b), b = p·0 + q·c, e c = p·1 + q·a. Resolvendo: a = q(p + qa), então a(1 − q²) = pq, resultando em a = pq/(p(1+q)) = q/(1+q).
  • Verificação de sanidade: para uma moeda justa (p = 1/2) isso resulta em 1/3, correspondendo ao resultado bem conhecido de que HHT vence HTH com probabilidade 2/3.

• Parte 2: E[número de lançamentos até o primeiro de HTH ou HHT] = (1 + p q²)/(p² q (1 + q)), com q = 1 − p.

  • Usando os mesmos estados, sejam E_S, E_H, E_HH, E_HT os lançamentos adicionais esperados. Então E_HH = 1 + p·E_HH, então E_HH = 1/q; E_HT = 1 + q·E_S; E_H = 1 + p·E_HH + q·E_HT; e E_S = 1 + p·E_H + q·E_S, ou seja, E_S = 1/p + E_H.
  • Substituindo: E_S(1 − q²) = 1/p + 1 + p/q + q, e como 1 − q² = p(1 + q), isso se simplifica para E_S = (1 + p q²)/(p² q (1 + q)).
  • Verificação de sanidade: para p = 1/2 isso resulta em (1 + 1/8)/((1/4)(1/2)(3/2)) = (9/8)/(3/16) = 6 lançamentos.

• Parte 3: Por que a abordagem de "blocos independentes não sobrepostos de três" falha.

  • Ocorrências de fronteira são perdidas: um padrão pode abranger dois blocos consecutivos (por exemplo, lançamentos 2–4 ou 5–7), como no exemplo T H H T onde HHT termina no lançamento 4. Dividir a sequência em trios desarticulados ignora essas ocorrências, então calcula a distribuição de tempo de espera errada.
  • Destrói a memória na corrida: o processo real carrega estado entre os lançamentos. Em particular, ambos os padrões têm a mesma probabilidade p²q de ocupar qualquer bloco fixo de três lançamentos, então o modelo de bloco preveria uma corrida 50–50 para cada p. Mas a resposta correta q/(1+q) é estritamente menor que 1/2 para todo 0 < p < 1, porque os padrões se sobrepõem de forma assimétrica: uma vez que o prefixo HH ocorre, HHT é garantido para terminar primeiro, enquanto uma tentativa parcial de HTH (HT seguido por T) descarta todo o progresso. Essa estrutura competitiva e sobreposta é exatamente o que o raciocínio de blocos independentes não consegue capturar.

1. Probabilidade de HTH aparecer antes de HHT:
Seja $P(HTH)$ a probabilidade de HTH aparecer antes de HHT. Podemos montar um sistema de equações lineares com base no estado atual da sequência. Seja $E$ o número esperado de lançamentos até que um dos padrões apareça. Seja $E_S$ o número esperado de lançamentos adicionais necessários dado que os últimos lançamentos formam a sequência $S$. Estamos interessados em $P(HTH)$.
Seja $P_S$ a probabilidade de HTH aparecer antes de HHT, dado que os últimos lançamentos formam a sequência $S$. Queremos encontrar $P_{\text{vazio}}$.
Os estados são: vazio, H, HH, HT.
$P_{\text{vazio}} = p P_H + q P_{\text{vazio}}$ (se o primeiro lançamento for T, voltamos ao estado vazio)
$P_H = p P_{HH} + q P_{\text{vazio}}$
$P_{HH} = p P_{HHH} + q P_{HT}$
$P_{HT} = p P_{HTH} + q P_{\text{vazio}}$
Os estados absorventes são HTH e HHT. Se HTH ocorrer, a probabilidade de HTH aparecer antes de HHT é 1. Se HHT ocorrer, a probabilidade é 0.
$P_{HTH} = 1$
$P_{HHT} = 0$
A partir de $P_{HH} = p P_{HHH} + q P_{HT}$, se o próximo lançamento for H, temos HHH. O sufixo relevante é HH, então $P_{HHH} = P_{HH}$. Assim, $P_{HH} = p P_{HH} + q P_{HT}$, o que implica $(1-p)P_{HH} = q P_{HT}$, então $q P_{HH} = q P_{HT}$, o que significa $P_{HH} = P_{HT}$.
Substituindo de volta:
$P_H = p P_{HT} + q P_{\text{vazio}}$
$P_{\text{vazio}} = p P_H + q P_{\text{vazio}} \rightarrow p P_{\text{vazio}} = p P_H \rightarrow P_{\text{vazio}} = P_H$
Portanto, $P_{\text{vazio}} = p P_{HT} + q P_{\text{vazio}} \rightarrow p P_{\text{vazio}} = p P_{HT} \rightarrow P_{\text{vazio}} = P_{HT}$.
Isso implica $P_{\text{vazio}} = P_H = P_{HH} = P_{HT}$. Seja essa probabilidade comum $P$.
Então $P = p P + q P$, que é $P=P$. Essa abordagem parece ter um problema com os estados. Vamos redefinir os estados com base no sufixo mais longo que pode ser um prefixo de qualquer um dos padrões alvo.
Estados: $\emptyset$, H, HH, HT.
Seja $P_S$ a probabilidade de HTH vencer começando do estado $S$.
$P_{\emptyset} = p P_H + q P_{\emptyset}$ (Se T, voltamos para $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (Se HT, estamos no estado HT)
$P_{HH} = p P_{HHH} + q P_{HT}$ (Se HHH, o sufixo é HH, então $P_{HHH} = P_{HH}$. Se HHT, perdemos, $P_{HHT}=0$)
$P_{HT} = p P_{HTH} + q P_{\emptyset}$ (Se HTH, vencemos, $P_{HTH}=1$. Se HTT, voltamos para $\emptyset$)
Assim, $P_{HH} = p P_{HH} + q P_{HT} \rightarrow (1-p)P_{HH} = q P_{HT} \rightarrow q P_{HH} = q P_{HT} \rightarrow P_{HH} = P_{HT}$.
$P_H = p P_{HT} + q P_{\emptyset}$
$P_{\emptyset} = p P_H + q P_{\emptyset} \rightarrow p P_{\emptyset} = p P_H \rightarrow P_{\emptyset} = P_H$.
Assim, $P_{\emptyset} = P_H = P_{HT} = P_{HH}$. Seja isso $P$.
$P = p P + q P$, que é $P=P$. Isso indica um problema com a definição dos estados ou equações.

Vamos usar uma abordagem de martingale mais padrão ou uma definição de estado diferente.
Considere os estados como o sufixo mais longo que é um prefixo de HTH ou HHT.
Estados: $\emptyset$, H, HH, HT.
Seja $P$ a probabilidade de HTH vencer.
$P = p P_H + q P_{\emptyset}$ (se T, voltamos para $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (se HT, estamos no estado HT)
$P_{HH} = p P_{HHH} + q P_{HHT}$ (se HHT, perdemos, $P_{HHT}=0$. Se HHH, o sufixo é HH, então $P_{HHH}=P_{HH}$)
$P_{HT} = p P_{HTH} + q P_{HTT}$ (se HTH, vencemos, $P_{HTH}=1$. Se HTT, o sufixo é T, então voltamos para $\emptyset$, $P_{HTT}=P_{\emptyset}$)
As equações são:
$P = p P_H + q P_{\emptyset}$
$P_H = p P_{HH} + q P_{\emptyset}$
$P_{HH} = p P_{HH} + q \times 0 \rightarrow (1-p)P_{HH} = 0 \rightarrow q P_{HH} = 0$. Como $q \neq 0$, $P_{HH} = 0$.
$P_{HT} = p \times 1 + q P_{\emptyset} = p + q P_{\emptyset}$.
Substituindo $P_{HH}=0$ em $P_H$: $P_H = p \times 0 + q P_{\emptyset} = q P_{\emptyset}$.
Substituindo $P_H$ em $P$: $P = p (q P_{\emptyset}) + q P_{\emptyset} = pq P_{\emptyset} + q P_{\emptyset} = (pq+q) P_{\emptyset} = q(p+1) P_{\emptyset}$. Isso não está correto.

Vamos usar o método de https://math.stackexchange.com/questions/129670/expected-number-of-coin-tosses-to-get-a-sequence-of-heads-and-tails
Seja $P_A$ a probabilidade de o padrão A (HTH) aparecer antes do padrão B (HHT).
Seja $A = HTH$ e $B = HHT$.
Usamos a fórmula $P_A = \frac{B:B - B:A}{A:A - A:B + B:B - B:A}$, onde $X:Y = \sum_{k=1}^{m} I(X_k = Y^{(k)}) 2^{k-1}$ e $X_k$ é o prefixo de comprimento $k$ de $X$, e $Y^{(k)}$ é o sufixo de comprimento $k$ de $Y$. $I$ é a função indicadora.
$A = HTH$, $B = HHT$.
$A:A$: HTH:HTH. $k=1$: H=H (12^0=1). $k=2$: HT=HT (12^1=2). $k=3$: HTH=HTH (12^2=4). $A:A = 1+2+4 = 7$.
$A:B$: HTH:HHT. $k=1$: H=H (12^0=1). $k=2$: HT=HH (0). $k=3$: HTH=HHT (0). $A:B = 1$.
$B:B$: HHT:HHT. $k=1$: H=H (12^0=1). $k=2$: HH=HH (12^1=2). $k=3$: HHT=HHT (12^2=4). $B:B = 1+2+4 = 7$.
$B:A$: HHT:HTH. $k=1$: H=H (12^0=1). $k=2$: HH=TH (0). $k=3$: HHT=HTH (0). $B:A = 1$.
$P_{HTH} = \frac{7 - 1}{7 - 1 + 7 - 1} = \frac{6}{12} = \frac{1}{2}$.

2. Número esperado de lançamentos:
Seja $E$ o número esperado de lançamentos até que HTH ou HHT apareça.
Podemos usar os mesmos estados novamente.
Estados: $\emptyset$, H, HH, HT.
Seja $E_S$ o número esperado de lançamentos adicionais necessários começando do estado $S$.
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset}$ (Se T, voltamos para $\emptyset$)
$E_H = 1 + p E_{HH} + q E_{\emptyset}$ (Se HT, estamos no estado HT)
$E_{HH} = 1 + p E_{HHH} + q E_{HHT}$ (Se HHT, paramos, $E_{HHT}=0$. Se HHH, o sufixo é HH, $E_{HHH}=E_{HH}$)
$E_{HT} = 1 + p E_{HTH} + q E_{HTT}$ (Se HTH, paramos, $E_{HTH}=0$. Se HTT, o sufixo é T, voltamos para $\emptyset$, $E_{HTT}=E_{\emptyset}$)
As equações são:
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset} \rightarrow p E_{\emptyset} = 1 + p E_H \rightarrow E_{\emptyset} = 1/p + E_H$.
$E_H = 1 + p E_{HH} + q E_{\emptyset}$.
$E_{HH} = 1 + p E_{HH} + q \times 0 \rightarrow (1-p)E_{HH} = 1 \rightarrow q E_{HH} = 1 \rightarrow E_{HH} = 1/q$.
$E_{HT} = 1 + p \times 0 + q E_{\emptyset} = 1 + q E_{\emptyset}$.
Substituindo $E_{HH}=1/q$ em $E_H$: $E_H = 1 + p (1/q) + q E_{\emptyset} = 1 + p/q + q E_{\emptyset}$.
Substituindo $E_H$ em $E_{\emptyset}$: $E_{\emptyset} = 1/p + (1 + p/q + q E_{\emptyset}) = 1/p + 1 + p/q + q E_{\emptyset}$.
$E_{\emptyset} (1-q) = 1/p + 1 + p/q \rightarrow p E_{\emptyset} = 1/p + 1 + p/q = (q + pq + p^2)/(pq)$.
$E_{\emptyset} = (q + pq + p^2)/(p^2 q)$.
Este é o número esperado de lançamentos até que HTH ou HHT apareça.
$E = \frac{q + pq + p^2}{p^2 q} = \frac{1-p + p(1-p) + p^2}{p^2 (1-p)} = \frac{1-p + p-p^2 + p^2}{p^2(1-p)} = \frac{1}{p^2(1-p)}$.

Vamos verificar com um exemplo. Se $p=1/2$, $q=1/2$. $E_0 = \frac{1}{(1/2)^2 (1/2)} = \frac{1}{1/8} = 8$.
Isso corresponde a resultados conhecidos para HTH ou HHT.

3. Explicação de por que tratar blocos não sobrepostos como ensaios independentes está errado:
Essa abordagem é falha porque os lançamentos de moeda não são ensaios independentes no contexto de correspondência de padrões. O resultado de um lançamento influencia a probabilidade de formar um padrão nos lançamentos subsequentes. Especificamente, o final de um bloco potencial de três lançamentos pode se sobrepor ao início do próximo bloco potencial. Por exemplo, se tivermos a sequência HHT, este é um dos nossos padrões alvo. Se considerássemos o próximo bloco não sobreposto começando do quarto lançamento, ignoraríamos o fato de que os três primeiros lançamentos já determinaram o resultado. Mais importante ainda, os padrões HTH e HHT podem se sobrepor a si mesmos ou uns aos outros de maneiras que violam a independência. Por exemplo, se a sequência for HTHHT, o primeiro HTH é formado e, em seguida, o padrão HHT começa imediatamente. Tratar esses como ensaios independentes falharia em contabilizar tais sobreposições e a memória inerente ao processo de geração da sequência. O estado da sequência (ou seja, o sufixo da sequência) é importante para determinar a probabilidade de atingir os padrões alvo.