Tiempo necesario para golpear un patrón de caras y colas en una serie de lanzamientos de monedas.

Inspirado por la charla de Peter Donnelly en TED , en la que analiza cuánto tiempo le tomaría a un cierto patrón aparecer en una serie de lanzamientos de monedas, creé el siguiente guión en R. Dados dos patrones 'hth' y 'htt', calcula cuánto tiempo tarda (es decir, cuántos lanzamientos de monedas) en promedio antes de alcanzar uno de estos patrones.

coin <- c('h','t')

hit <- function(seq) {
    miss <- TRUE
    fail <- 3
    trp  <- sample(coin,3,replace=T)
    while (miss) {
        if (all(seq == trp)) {
            miss <- FALSE
        }
        else {
            trp <- c(trp[2],trp[3],sample(coin,1,T))
            fail <- fail + 1
        }
    }
    return(fail)
}

n <- 5000
trials <- data.frame("hth"=rep(NA,n),"htt"=rep(NA,n))

hth <- c('h','t','h')
htt <- c('h','t','t')

set.seed(4321)
for (i in 1:n) {
    trials[i,] <- c(hit(hth),hit(htt))    
}
summary(trials)

Las estadísticas resumidas son las siguientes,

      hth             htt        
 Min.   : 3.00   Min.   : 3.000  
 1st Qu.: 4.00   1st Qu.: 5.000  
 Median : 8.00   Median : 7.000  
 Mean   :10.08   Mean   : 8.014  
 3rd Qu.:13.00   3rd Qu.:10.000  
 Max.   :70.00   Max.   :42.000 

En la charla se explica que el número promedio de lanzamientos de monedas sería diferente para los dos patrones; como se puede ver en mi simulación. A pesar de ver la charla algunas veces, todavía no entiendo por qué este sería el caso. Entiendo que 'hth' se superpone e intuitivamente pensaría que presionarías 'hth' antes que 'htt', pero este no es el caso. Realmente agradecería que alguien me explicara esto.

Piensa en lo que sucede la primera vez que obtienes una H seguida de una T.

Caso 1: estás buscando HTH y has visto HT por primera vez. Si el próximo lanzamiento es H, ya está. Si es T, volverá al punto de partida: dado que los dos últimos lanzamientos fueron TT, ahora necesita el HTH completo.

Caso 2: estás buscando HTT y has visto HT por primera vez. Si el próximo lanzamiento es T, ya está. Si es H, esto es claramente un revés; sin embargo, es menor ya que ahora tiene la H y solo necesita -TT. Si el próximo lanzamiento es H, esto no empeora su situación, mientras que T lo mejora, y así sucesivamente.

Dicho de otra manera, en el caso 2, la primera H que ves te lleva 1/3 del camino, y desde ese momento nunca tienes que empezar desde cero. Esto no es cierto en el caso 1, donde un TT borra todo el progreso que ha realizado.

Supongamos que arroja la moneda veces y cuenta la cantidad de veces que ve un patrón "HTH" (incluidas las superposiciones). El número esperado es . Pero también es para "HTT". Dado que puede superponerse y "HTT" no puede, esperaría más aglomeración con "HTH", lo que aumenta el tiempo esperado para la primera aparición de . n n H T H H T $8n+2$$n$$n$$HTH$$HTH$

Otra forma de verlo es que después de llegar a "HT", una "T" enviará "HTH" de regreso al inicio, mientras que una "H" comenzará a avanzar hacia un posible "HTT".

Puede calcular las dos veces esperadas utilizando el algoritmo de Conway [creo], observando las superposiciones: si las primeras tiradas del patrón coinciden con las últimas , entonces agregue . Entonces, para "HTH" obtienes como la expectativa y para "HTT" obtienes , confirmando tu simulación.k 2 k 2 + 0 + 8 = 10 0 + 0 + 8 = $k$$k$$2^k$$2+0+8=10$$0+0+8=8$

La rareza no se detiene allí. Si tiene una carrera entre los dos patrones, tienen la misma probabilidad de aparecer primero, y el tiempo esperado hasta que aparezca uno de ellos es (uno más del tiempo esperado para obtener "HT", después del cual debe aparecer uno de ellos) . $5$

Se pone peor: en el juego de Penney, eliges un patrón para competir y luego elijo otro. Si elige "HTH", elegiré "HHT" y tendré 2: 1 de probabilidades de ganar; si elige "HTT", elegiré "HHT" nuevamente y aún tendré probabilidades 2: 1 a mi favor. Pero si eliges "HHT", elegiré "THH" y tendré una probabilidad de 3: 1. El segundo jugador siempre puede sesgar las probabilidades, y las mejores opciones no son transitivas.

Me gusta hacer dibujos.

Estos diagramas son autómatas de estado finito (FSA). Son pequeños juegos infantiles (como Chutes y Ladders ) que "reconocen" o "aceptan" las secuencias HTT y HTH, respectivamente, moviendo una ficha de un nodo a otro en respuesta a los lanzamientos de monedas. El token comienza en el nodo superior, señalado por una flecha (línea i ). Después de cada lanzamiento de la moneda, la ficha se mueve a lo largo del borde etiquetado con el resultado de esa moneda (H o T) a otro nodo (al que llamaré "nodo H" y "nodo T", respectivamente). Cuando la ficha cae en un nodo terminal (sin flechas salientes, indicadas en verde), el juego termina y la FSA ha aceptado la secuencia.

Piense en cada FSA como progresando verticalmente por una pista lineal. Lanzar la secuencia "correcta" de cara y cruz hace que la ficha progrese hacia su destino. Lanzar un valor "incorrecto" hace que el token retroceda (o al menos se quede quieto). El token retrocede al estado más avanzado correspondiente a los lanzamientos más recientes. Por ejemplo, la HTT FSA en la línea ii permanece en la línea ii al ver una cabeza, porque esa cabeza podría ser la secuencia inicial de una HTH eventual. No se remonta al principio, ya que eso ignoraría por completo esta última cabeza.

Después de verificar que estos dos juegos corresponden a HTT y HTH como se afirma, y ​​compararlos línea por línea, y ahora debería ser obvio que HTH es más difícil de ganar . Difieren en su estructura gráfica solo en la línea iii , donde una H lleva HTT de vuelta a la línea ii (y una T acepta) pero, en HTH, una T nos lleva de vuelta a la línea i (y una H acepta). La penalización en la línea iii al jugar HTH es más severa que la penalidad al jugar HTT.

Esto puede ser cuantificado. He etiquetado los nodos de estos dos FSA con el número esperado de lanzamientos necesarios para la aceptación. Llamemos a estos el nodo "valores". El etiquetado comienza por

(1) escribir el valor obvio de 0 en los nodos de aceptación.

Deje que la probabilidad de caras sea p (H) y la probabilidad de colas sea 1 - p (H) = p (T). (Para una moneda justa, ambas probabilidades equivalen a 1/2.) Debido a que cada lanzamiento de moneda agrega uno al número de lanzamientos,

(2) el valor de un nodo es igual a uno más p (H) multiplicado por el valor del nodo H más p (T) multiplicado por el valor del nodo T.

Estas reglas determinan los valores . Es un ejercicio rápido e informativo para verificar que los valores etiquetados (suponiendo una moneda justa) sean correctos. Como ejemplo, considere el valor de HTH en la línea ii . La regla dice que 8 debe ser 1 más que el promedio de 8 (el valor del nodo H en la línea i ) y 6 (el valor del nodo T en la línea iii ): efectivamente, 8 = 1 + (1/2) * 8 + (1/2) * 6. También puede verificar fácilmente los cinco valores restantes en la ilustración.

Algunas buenas respuestas. Me gustaría tomar un rumbo ligeramente diferente y abordar la cuestión de la contraintitividad. (Estoy bastante de acuerdo, por cierto)

Así es como le doy sentido. Imagine una columna de resultados aleatorios secuenciales de lanzamiento de monedas impresos en una cinta de papel, que consta de las letras "H" y "T".

Corte arbitrariamente una sección de esta cinta y haga una copia idéntica.

En una cinta dada, la secuencia HTH y la secuencia HTT ocurrirán con la misma frecuencia, si la cinta es lo suficientemente larga.

Pero ocasionalmente las instancias de HTH se ejecutarán juntas, es decir, HTHTH. (o incluso muy ocasionalmente HTHTHTH)

Esta superposición no puede ocurrir con instancias HTT.

Use un resaltador para seleccionar las "franjas" de resultados exitosos, HTH en una cinta y HTT en la otra. Algunas de las rayas HTH serán más cortas debido a la superposición. En consecuencia, los espacios entre ellos, en promedio, serán un poco más largos que en la otra cinta.

Es un poco como esperar un autobús, cuando en promedio hay uno cada cinco minutos. Si se permite que los autobuses se superpongan entre sí, el intervalo será un poco más de cinco minutos, en promedio, porque en algún momento dos pasarán juntos.

Si llega en un momento arbitrario, esperará un poco más de tiempo el próximo (para usted, primero) autobús, en promedio, si se les permite superponerse.

Estaba buscando la intuición para esto en el caso de enteros (mientras estoy revisando la Introducción de Ross a los Modelos de Probabilidad). Entonces estaba pensando en casos enteros. Encontré que esto ayudó:

$A$

$B$

$A=B$$P(A \cap \tilde{B})=0$

$A \ne B$$P(A \cap \tilde{B}) \ge 0$

Entonces, déjame imaginar que tengo la oportunidad de terminar el patrón en el próximo sorteo. Dibujo el siguiente símbolo y no termina el patrón. En el caso de que mi patrón no se superponga, el símbolo dibujado aún podría permitirme comenzar a construir el patrón desde el principio nuevamente.

En el caso de una superposición, el símbolo que necesitaba para terminar mi patrón parcial era el mismo que el símbolo que necesitaría para comenzar a reconstruir. Por lo tanto, tampoco puedo hacerlo y, por lo tanto, definitivamente tendré que esperar hasta el próximo sorteo para tener la oportunidad de comenzar a construir nuevamente.