Número de lanzamientos de moneda requeridos para obtener al menos 60 caras en una ventana deslizante de longitud 100

Question

He estado luchando con el siguiente problema (no una tarea), que me pareció bastante fácil de plantear pero difícil (para mí) de resolver.

Supongamos que tienes una moneda justa con probabilidad de 1/2 de obtener cara o cruz, y comienzas una serie de lanzamientos. Dado un número de caras (digamos 60 por ejemplo), ¿cuál es la expectativa del número de lanzamientos que tendré que realizar para obtener 60 caras/40 cruces en una "ventana deslizante" de 100 lanzamientos?

es decir: si escribo $S_n=(HHTHTTHT...H)_n=(u_{0}u_{1}...u_{n})$, ¿cuál es el valor esperado para $T_{60}=\{min(k)$ tal que $(u_{k}..u_{k+100})$ contiene 60 caras}.

Intenté razonar con Cadenas de Markov pero $(u_{k}...u_{k+100})$ claramente no es una cadena de Markov ya que tiene memoria.

Otra forma de verlo, podría ser calcular la probabilidad de alcanzar 60 en los primeros 100 lanzamientos, y luego las siguientes "ventanas deslizantes" de longitud 100 parecen seguir casi un paseo aleatorio, pero esto no es cierto ya que, por ejemplo, cuando alcanzas 100 caras, no puedes obtener más.

Creo que hay fórmulas para encontrar el tiempo esperado de un patrón dado, pero sería tedioso escribirlo para una cadena de longitud 100, e incluso si tengo el tiempo esperado para todos los patrones que contienen 60 caras, no puedo deducir el tiempo esperado para la unión de todos los patrones.

Entonces, creo que un método que podría funcionar es escribir explícitamente la probabilidad $P_k$ de alcanzar 60 caras en el tiempo $k$, y no haber alcanzado 60 caras antes. Luego desarrollar por condicionamiento => $P_k = P($alcanzar 60 caras en el tiempo k$|$no hemos alcanzado 60 caras en ningún momento $k'*$P($no hemos alcanzado 60 caras en ningún momento $k'

$P($no hemos alcanzado 60 caras en ningún momento $k' es computable por simples argumentos de conteo (cuento todas las series de lanzamientos de monedas de longitud n que contienen al menos un patrón de 60 caras).

$P($alcanzar 60 caras en el tiempo k$|$no hemos alcanzado 60 caras en ningún momento $k' depende solo de $k'\geq k-100$ (las ventanas deslizantes superpuestas de longitud 100). Entonces parece computable, nuevamente por argumentos de conteo pero parece muy tedioso...

Así que estoy buscando ideas sobre esto:

• ¿Es correcto mi razonamiento por argumentos de conteo?
• ¿Hay otra forma más elegante de resolver este problema?

PD: Hice simulaciones de monte carlo para poder resolver este problema numéricamente pero estoy interesado en soluciones en forma cerrada

Answer 1

Usando el hecho de que esto es, de hecho, una cadena de Markov. Puedo escribir las ecuaciones de los primeros tiempos de paso $$k_i = 0, i \in A$$ $$k_i =1 + \sum_j{p_{ij}k_j}, i \in A^c$$ Lo cual parece ser bastante complejo de resolver incluso si todas las ecuaciones solo tienen 2 términos en el lado derecho. Mi intento:

1. Para un estado $(HHT...THT)$ que reescribo como $(a_0a_1...a_{99})$ con $a_k=1$ si la tirada es Caras, y $a_k=0$ si la tirada es Escudos. Atribuyo el número $i=a_0+2*a_1+...+2^{99}*a_{99}$, para que todos los estados estén numerados de $0$ a $ 2^{100}-1$
2. Ahora mis ecuaciones se convierten en: $$k_i=0, \text{ si } \sum_k{a_k}\geq60$$ $$k_i=1+k_{\frac{i-a_0}{2}}*0.5+k_{\frac{i-a_0}{2}+2^{99}}*0.5, \text{ si } \sum_k{a_k}<60$$ Esto parece algo que se puede resolver, pero en la práctica estoy perdido al escribir explícitamente las soluciones (¿tal vez usando una numeración más agradable que la que propongo?).

NB: Escribí las ecuaciones para un problema de menor dimensión (tiempo esperado para llegar a 2 caras de una serie en curso de 3 lanzamientos de moneda) y encuentro una solución, a saber: $$k_3=k_5=k_6=k_7=0$$ $$k_0=k_1=\frac{14}{3}$$ $$k_2=\frac{10}{3}$$ $$k_4=\frac{8}{3}$$ Después de eso, solo es cuestión de probabilizar con el estado inicial siendo $i$, y todos tienen la misma probabilidad de $\frac{1}{8}$. Por otro lado, no logro generalizar a dimensiones más altas...

Answer 2

Siguiendo la sugerencia de empy2, intento simplificar el problema asumiendo que la suma de las caras es una cadena de Markov con probabilidades de "reversión a la media".

A continuación, se muestran los resultados de las simulaciones.

Para $n = 3$ lanzamientos y $k= 2$ caras obtengo:

1. número esperado de lanzamientos = 4.914 a través de simulaciones MCL (10000 dibujos) usando la modelización exacta
2. número esperado de lanzamientos = 5.237 a través de simulaciones MCL (10000 dibujos) usando la modelización de la suma de las caras

Cabe destacar que 1) está en línea con la solución exacta que calculé anteriormente ($=3+\frac{1}{8}×\frac{46}{3}$)

Para $n = 100$ lanzamientos y $k= 60$ caras obtengo:

1. número esperado de lanzamientos = 848.705 a través de simulaciones MCL (10000 dibujos) usando la modelización exacta
2. número esperado de lanzamientos = 1062.42 a través de simulaciones MCL (10000 dibujos) usando la modelización de la suma de las caras

Por lo tanto, la modelización simplificada no parece converger, incluso si no es "demasiado mala".