Carrera de patrones con moneda sesgada

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

• Se establece una cadena de Markov sobre los estados de "sufijo útil": S (sin progreso), H, HH, HT. Hecho estructural clave: desde el estado HH, el patrón HHT ganará con certeza, porque las caras nos mantienen en HH y la primera cruz completa inmediatamente HHT antes de que HTH pueda formarse; por lo tanto, P(HTH primero | HH) = 0.
• Sean a, b, c la probabilidad de que HTH gane desde S, H, HT respectivamente. Entonces a = p·b + q·a (así que a = b), b = p·0 + q·c, y c = p·1 + q·a. Resolviendo: a = q(p + qa), así que a(1 − q²) = pq, dando a = pq/(p(1+q)) = q/(1+q).
• Comprobación de cordura: para una moneda justa (p = 1/2) esto da 1/3, lo que coincide con el resultado bien conocido de que HHT vence a HTH con una probabilidad de 2/3.

Parte 2: E[número de lanzamientos hasta el primero de HTH o HHT] = (1 + p q²)/(p² q (1 + q)), con q = 1 − p.

• Usando los mismos estados, sean E_S, E_H, E_HH, E_HT los lanzamientos adicionales esperados. Entonces E_HH = 1 + p·E_HH, así que E_HH = 1/q; E_HT = 1 + q·E_S; E_H = 1 + p·E_HH + q·E_HT; y E_S = 1 + p·E_H + q·E_S, es decir, E_S = 1/p + E_H.
• Sustituyendo: E_S(1 − q²) = 1/p + 1 + p/q + q, y como 1 − q² = p(1 + q), esto se simplifica a E_S = (1 + p q²)/(p² q (1 + q)).
• Comprobación de cordura: para p = 1/2 esto da (1 + 1/8)/((1/4)(1/2)(3/2)) = (9/8)/(3/16) = 6 lanzamientos.

Parte 3: Por qué falla el enfoque de "bloques independientes de tres no superpuestos".

• Se omiten las ocurrencias de borde: un patrón puede abarcar dos bloques consecutivos (por ejemplo, lanzamientos 2-4 o 5-7), como en el ejemplo T H H T donde HHT termina en el lanzamiento 4. Dividir la secuencia en triples disjuntos ignora estas ocurrencias, por lo que calcula la distribución de tiempo de espera incorrecta.
• Destruye la memoria en la carrera: el proceso real transporta el estado entre lanzamientos. En particular, ambos patrones tienen la misma probabilidad p²q de ocupar cualquier bloque fijo de tres lanzamientos, por lo que el modelo de bloque predeciría una carrera 50-50 para cada p. Pero la respuesta correcta q/(1+q) es estrictamente menor que 1/2 para todo 0 < p < 1, porque los patrones se superponen de forma asimétrica: una vez que ocurre el prefijo HH, HHT está garantizado que terminará primero, mientras que un intento parcial de HTH (HT seguido de T) descarta todo el progreso. Esta estructura competitiva y superpuesta es exactamente lo que el razonamiento de bloques independientes no puede capturar.

1. Probabilidad de que HTH aparezca antes que HHT:
Sea $P(HTH)$ la probabilidad de que HTH aparezca antes que HHT. Podemos establecer un sistema de ecuaciones lineales basado en el estado actual de la secuencia. Sea $E$ el número esperado de lanzamientos hasta que aparezca uno de los patrones. Sea $E_S$ el número esperado de lanzamientos adicionales necesarios dado que los últimos lanzamientos forman la secuencia $S$. Estamos interesados en $P(HTH)$.
Sea $P_S$ la probabilidad de que HTH aparezca antes que HHT, dado que los últimos lanzamientos forman la secuencia $S$. Queremos encontrar $P_{\text{vacío}}$.
Los estados son: vacío, H, HH, HT.
$P_{\text{vacío}} = p P_H + q P_{\text{vacío}}$ (si el primer lanzamiento es T, volvemos al estado vacío)
$P_H = p P_{HH} + q P_{\text{vacío}}$
$P_{HH} = p P_{HHH} + q P_{HT}$
$P_{HT} = p P_{HTH} + q P_{\text{vacío}}$
Los estados absorbentes son HTH y HHT. Si ocurre HTH, la probabilidad de que HTH aparezca antes que HHT es 1. Si ocurre HHT, la probabilidad es 0.
$P_{HTH} = 1$
$P_{HHT} = 0$
De $P_{HH} = p P_{HHH} + q P_{HT}$, si el siguiente lanzamiento es H, tenemos HHH. El sufijo relevante es HH, por lo que $P_{HHH} = P_{HH}$. Por lo tanto, $P_{HH} = p P_{HH} + q P_{HT}$, lo que implica $(1-p)P_{HH} = q P_{HT}$, es decir, $q P_{HH} = q P_{HT}$, lo que significa $P_{HH} = P_{HT}$.
Sustituyendo esto de nuevo:
$P_H = p P_{HT} + q P_{\text{vacío}}$
$P_{\text{vacío}} = p P_H + q P_{\text{vacío}} \rightarrow p P_{\text{vacío}} = p P_H \rightarrow P_{\text{vacío}} = P_H$
Entonces, $P_{\text{vacío}} = p P_{HT} + q P_{\text{vacío}} \rightarrow p P_{\text{vacío}} = p P_{HT} \rightarrow P_{\text{vacío}} = P_{HT}$.
Esto implica que $P_{\text{vacío}} = P_H = P_{HH} = P_{HT}$. Sea esta probabilidad común $P$.
Entonces $P = p P + q P$, que es $P=P$. Este enfoque parece tener un problema con los estados. Redefinamos los estados basándonos en el sufijo más largo que podría ser un prefijo de cualquiera de los patrones objetivo.
Estados: $\emptyset$, H, HH, HT.
Sea $P_S$ la probabilidad de que HTH gane comenzando desde el estado $S$.
$P_{\emptyset} = p P_H + q P_{\emptyset}$ (Si T, volvemos a $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (Si HT, estamos en el estado HT)
$P_{HH} = p P_{HHH} + q P_{HT}$ (Si HHH, el sufijo es HH, por lo que $P_{HHH} = P_{HH}$. Si HHT, perdemos, $P_{HHT}=0$)
$P_{HT} = p P_{HTH} + q P_{\emptyset}$ (Si HTH, ganamos, $P_{HTH}=1$. Si HTT, volvemos a $\emptyset$)
Entonces, $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$.
Entonces, $P_{\emptyset} = P_H = P_{HT} = P_{HH}$. Sea esto $P$.
$P = p P + q P$, que es $P=P$. Esto indica un problema con la definición de los estados o las ecuaciones.

Usemos un enfoque de martingala más estándar o una definición de estado diferente.
Consideremos los estados como el sufijo más largo que es un prefijo de HTH o HHT.
Estados: $\emptyset$, H, HH, HT.
Sea $P$ la probabilidad de que HTH gane.
$P = p P_H + q P_{\emptyset}$ (si T, volvemos a $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (si HT, estamos en el estado HT)
$P_{HH} = p P_{HHH} + q P_{HHT}$ (si HHT, perdemos, $P_{HHT}=0$. Si HHH, el sufijo es HH, por lo que $P_{HHH}=P_{HH}$)
$P_{HT} = p P_{HTH} + q P_{HTT}$ (si HTH, ganamos, $P_{HTH}=1$. Si HTT, el sufijo es T, por lo que volvemos a $\emptyset$, $P_{HTT}=P_{\emptyset}$)
Las ecuaciones son:
$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$. Dado que $q \neq 0$, $P_{HH} = 0$.
$P_{HT} = p \times 1 + q P_{\emptyset} = p + q P_{\emptyset}$.
Sustituyendo $P_{HH}=0$ en $P_H$: $P_H = p \times 0 + q P_{\emptyset} = q P_{\emptyset}$.
Sustituyendo $P_H$ en $P$: $P = p (q P_{\emptyset}) + q P_{\emptyset} = pq P_{\emptyset} + q P_{\emptyset} = (pq+q) P_{\emptyset} = q(p+1) P_{\emptyset}$. Esto no es correcto.

Usemos el método de https://math.stackexchange.com/questions/129670/expected-number-of-coin-tosses-to-get-a-sequence-of-heads-and-tails
Sea $P_A$ la probabilidad de que el patrón A (HTH) aparezca antes que el patrón B (HHT).
Sea $A = HTH$ y $B = HHT$.
Usamos la fórmula $P_A = \frac{B:B - B:A}{A:A - A:B + B:B - B:A}$, donde $X:Y = \sum_{k=1}^{m} I(X_k = Y^{(k)}) 2^{k-1}$ y $X_k$ es el prefijo de longitud $k$ de $X$, y $Y^{(k)}$ es el sufijo de longitud $k$ de $Y$. $I$ es la función 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 lanzamientos:
Sea $E$ el número esperado de lanzamientos hasta que aparezca HTH o HHT.
Podemos usar la misma fórmula para los tiempos esperados de patrones. Para un solo patrón $A$, el tiempo esperado es $E_A = A:A$. Sin embargo, aquí tenemos dos patrones compitiendo.
Sea $E$ el número esperado de lanzamientos. Podemos usar estados nuevamente.
Estados: $\emptyset$, H, HH, HT.
Sea $E_S$ el número esperado de lanzamientos adicionales necesarios comenzando desde el estado $S$.
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset}$ (Si T, volvemos a $\emptyset$)
$E_H = 1 + p E_{HH} + q E_{\emptyset}$ (Si HT, estamos en el estado HT)
$E_{HH} = 1 + p E_{HHH} + q E_{HHT}$ (Si HHT, paramos, $E_{HHT}=0$. Si HHH, el sufijo es HH, $E_{HHH}=E_{HH}$)
$E_{HT} = 1 + p E_{HTH} + q E_{HTT}$ (Si HTH, paramos, $E_{HTH}=0$. Si HTT, el sufijo es T, volvemos a $\emptyset$, $E_{HTT}=E_{\emptyset}$)
Las ecuaciones son:
$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}$.
Sustituye $E_{HH}=1/q$ en $E_H$: $E_H = 1 + p (1/q) + q E_{\emptyset} = 1 + p/q + q E_{\emptyset}$.
Sustituye $E_H$ en $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 es el número esperado de lanzamientos hasta que aparezca HTH o HHT.
$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)}$.

Reevaluemos el cálculo de $E_{HT}$.
$E_{HT} = 1 + q E_0 = 1 + q \frac{q+pq+p^2}{p^2 q} = 1 + \frac{q+pq+p^2}{p^2} = \frac{p^2 + q+pq+p^2}{p^2} = \frac{2p^2+pq+q}{p^2}$.
Este es el número esperado de lanzamientos si estamos en el estado HT. Queremos $E_0$.
Por lo tanto, el número esperado de lanzamientos es $E_0 = \frac{1}{p^2(1-p)}$.

Verifiquemos con un ejemplo. Si $p=1/2$, $q=1/2$. $E_0 = \frac{1}{(1/2)^2 (1/2)} = \frac{1}{1/8} = 8$.
Esto coincide con los resultados conocidos para HTH o HHT.

3. Explicación de por qué tratar bloques no superpuestos como ensayos independientes es incorrecto:
Este enfoque es defectuoso porque los lanzamientos de moneda no son ensayos independientes en el contexto de la coincidencia de patrones. El resultado de un lanzamiento influye en la probabilidad de formar un patrón en lanzamientos posteriores. Específicamente, el final de un bloque potencial de tres lanzamientos puede superponerse con el comienzo del siguiente bloque potencial. Por ejemplo, si tenemos la secuencia HHT, este es uno de nuestros patrones objetivo. Si consideráramos el siguiente bloque no superpuesto a partir del cuarto lanzamiento, ignoraríamos el hecho de que los primeros tres lanzamientos ya determinaron el resultado. Lo que es más importante, los patrones HTH y HHT pueden superponerse consigo mismos o entre sí de maneras que violan la independencia. Por ejemplo, si la secuencia es HTHHT, se forma el primer HTH, y luego el patrón HHT comienza inmediatamente. Tratar estos como ensayos independientes no tendría en cuenta tales superposiciones y la memoria inherente al proceso de generación de secuencias. El estado de la secuencia (es decir, el sufijo de la secuencia) importa para determinar la probabilidad de alcanzar los patrones objetivo.