¿Cuántos pasos se requieren para el patrón 0-0-1-1..

Question

Así que estoy haciendo este ejercicio donde se pide encontrar el número de pasos para obtener el patrón 0-0-1-1 Una secuencia de 0s y 1s es generada por una cadena de Markov con matriz de transición:

$$ P= \begin{pmatrix} 1/4 & 3/4 \\ 3/4 & 1/4 \\ \end{pmatrix} $$ con los estados 0,1.

El primer elemento de la secuencia se decide mediante el lanzamiento de una moneda justa. En promedio, ¿cuántos pasos son necesarios para que aparezca por primera vez el patrón 0-0-1-1?

Estaba pensando en utilizar la expectativa condicional, pero estoy viendo que se alarga demasiado. ¿Hay alguna forma rápida de encontrar la respuesta?

Answer 1

La forma rápida es considerar una cadena de Markov relacionada con 5 estados: $$\{ \varnothing, 0, 00, 001, 0011\}$$ que representa la parte del patrón que se ha alcanzado hasta ahora. (Una observación no muy obvia es que en el estado $\varnothing$ la última moneda lanzada es una $1$ que afecta a las probabilidades de transición).

Dejemos que $H_{\varnothing}$ , $H_0$ , $H_{00}$ , $H_{001}$ denotan los tiempos de golpeo hasta alcanzar el estado $0011$ . Entonces queremos resolver el sistema \begin{align} H_{\varnothing} &= 1 + \frac14 H_{\varnothing} + \frac34 H_0 \\ H_0 &= 1 + \frac34 H_{\varnothing} + \frac14 H_{00} \\ H_{00} &= 1 + \frac14 H_{00} + \frac34 H_{001} \\ H_{001} &= 1 + \frac14 (0) + \frac34 H_0 \end{align} y calcular $\frac12 H_{\varnothing} + \frac12 H_0$ .

Esto está un poco acelerado por la sustitución $H_i' = H_i - H_\varnothing$ después de lo cual (restando $H_\varnothing$ de ambos lados de cada ecuación) obtenemos \begin{align} 0 &= 1 + \frac14 (0) + \frac34 H_0' \\ H_0' &= 1 + \frac34 (0) + \frac14 H_{00}' \\ H_{00}' &= 1 + \frac14 H_{00}' + \frac34 H_{001}' \\ H_{001}' &= 1 + \frac14 (-H_\varnothing) + \frac34 H_0'. \end{align} Ahora podemos resolver para $H_0', H_{00}', H_{001}', H_\varnothing$ en ese orden de cada ecuación.