El tiempo tomado para golpear un patrón de cabeza y la cola en una serie de monedas arrojadas

Question

Inspirado por Peter Donnelly la charla en TED, en la que él habla de cuánto tiempo tomaría para que un determinado patrón de aparecer en una serie de lanzar una moneda, he creado el siguiente script en el R. Dado dos patrones "hth' y 'htt', calcula cuánto tiempo se necesita (es decir, cuántas lanzar una moneda), en promedio, antes de llegar a 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)

El resumen de las estadísticas son como sigue,

      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 lanzar una moneda iba a ser diferente para los dos patrones; como puede verse en mi simulación. A pesar de ver la charla de un par de veces no estoy recibiendo por qué esto sería el caso. Entiendo que 'hth" se superpone a sí mismo y de forma intuitiva me gustaría pensar que usted podría golpear 'hth' antes que 'htt', pero este no es el caso. Yo realmente apreciaría si alguien podría explicar esto a mí.

Answer 1

Pensar acerca de lo que sucede la primera vez que se obtiene un H seguido por una T.

Caso 1: usted está buscando para el H-T-H, y has visto H-T por primera vez. Si el próximo tiro es H, ya está hecho. Si es T, estás de vuelta a la casilla de salida: desde las últimas dos tiros fueron T-T ahora se necesita el pleno del H-T-H.

Caso 2: usted está buscando para el H-T-T, y has visto H-T por primera vez. Si el próximo tiro es T, ya está hecho. Si es H, esto es claramente un retroceso; sin embargo, es menor, ya que ahora tiene la H y sólo necesita -T-T. Si el próximo tiro es H, esto hace que su situación no es peor, mientras que T hace mejor, y así sucesivamente.

Dicho de otra manera, en el caso 2, el primer H que ver lo lleva 1/3 de la forma, y a partir de ese punto, usted nunca tendrá que empezar de cero. Esto no es cierto en el caso 1, donde un T-T borra todo el progreso que ha hecho.

Answer 2

Me gusta dibujar.

Estos diagramas son autómatas de estado finito (Fsa). Ellos son pequeños juegos de los niños (como Rampas y Escaleras) que "reconocer" o "aceptar" HTT y HTH secuencias, respectivamente, por el movimiento de un símbolo (token) de un nodo a otro en respuesta a la moneda gira. El token comienza en el nodo superior, señalado por una flecha (línea i). Después de cada lanzamiento de la moneda, el token se mueve a lo largo del borde de la etiqueta con la moneda del resultado (ya sea H o T) a otro nodo (que voy a llamar a la "H nodo" y "T nodo", respectivamente). Cuando la ficha cae en un nodo terminal (sin flechas salientes, indica en verde), el juego es largo y la FSA ha aceptado la secuencia.

Pensar de cada FSA avanza verticalmente hacia abajo una pista lineal. Lanzando el "derecho" de la secuencia de caras y cruces hace que el token para avanzar hacia su destino. Lanzando un "mal" valor hace que el token de copia de seguridad (o al menos estar quieto). El símbolo de la espalda hasta los más avanzados estado, correspondiente a los más recientes lanzamientos. Por ejemplo, el HTT FSA en la línea ii queda en la línea ii , al ver una cabeza, porque la cabeza podría ser la secuencia inicial de una eventual HTH. Sí no ir todo el camino de vuelta al principio, porque eso sería ignorar efectivamente esta última la cabeza por completo.

Después de la verificación de estos dos juegos, de hecho, corresponden a HTT y HTH como se afirma, y la comparación de ellos, línea por línea, y ahora debería ser obvio que HTH es más difícil ganar. Difieren en su gráfica de la estructura sólo en la línea iii, donde una H en HTT regresar a la línea ii (y un T acepta) pero, en HTH, un T que nos lleva todo el camino de regreso a la línea i (y un H acepta). La pena en la línea iii en el juego del HTH es más grave que la pena jugar HTT.

Esto puede ser cuantificado. Me han etiquetado a los nodos de estos dos Fsa con el número esperado de lanzamientos necesarios para su aceptación. Que nos llame a estos el nodo "valores". El etiquetado comienza por

(1) escrito el evidente valor de 0 en la aceptación de los nodos.

Deje que la probabilidad de cabezas ser p(H) y la probabilidad de que las colas 1 - p(H) = p(T). (Para una feria de la moneda, ambas probabilidades igual a 1/2.) Porque cada tirón de la moneda agrega una el número de lanzamientos,

(2) el valor de un nodo es igual a un plus p(H) veces el valor de la H nodo plus p(T) veces el valor de la T de nodo.

Estas reglas determinan los valores. Se trata de un corto e informativo ejercicio para comprobar que la etiqueta de valores (suponiendo una moneda no trucada) son correctas. Como un ejemplo, considere el valor de HTH en línea ii. La regla dice que 8 debe ser 1 más que el promedio de 8 (el valor de la H nodo en la línea i) y 6 (el valor de la T de nodo en la línea iii): bastante seguro, 8 = 1 + (1/2)*8 + (1/2)*6. Usted puede apenas como fácilmente comprobar que los cinco restantes valores de la ilustración.

Answer 3

Supongamos que lanzan la moneda $8n+2$ veces y contar el número de veces que usted ve un "HTH" patrón (incluyendo las superposiciones). El número esperado es $n$. Pero también es $n$ "HTT". Desde $HTH$ pueden traslaparse y "HTT" no, usted tendría que esperar más de aglutinación con "HTH", lo que aumenta el tiempo de espera para la primera aparición de $HTH$.

Otra forma de verlo es que después de alcanzar la "HT", una "T" enviar "HTH" de regreso al inicio, mientras que una "H", se inicia el progreso de una posible "HTT".

Usted puede trabajar fuera de los dos espera que los tiempos de uso de Conway algoritmo [creo], buscando las coincidencias: si la primera $k$ tira de el patrón coincide con el último $k$, a continuación, agregue $2^k$. Así que para "HTH" se obtiene el $2+0+8=10$ como la expectativa y para "HTT" se obtiene el $0+0+8=8$, lo que confirma su simulación.

La rareza no se detiene ahí. Si usted tiene una carrera entre los dos modelos, tienen la misma probabilidad de aparecer en primer lugar, y el tiempo de espera hasta que uno de ellos aparece es $5$ (uno más que el tiempo de espera para obtener "HT", después de que uno de ellos debe aparecer).

Empeora: en Penney del juego que usted elija un patrón de carrera y luego elegir otro. Si usted elige "HTH", a continuación, voy a elegir "HHT" y disponen de 2:1 probabilidades de ganar; si elige "HTT", a continuación, voy a elegir "HHT" de nuevo y todavía tiene 2:1 probabilidades a mi favor. Pero si usted elige "HHT", a continuación, voy a elegir "THH" y tiene 3:1 probabilidades. El segundo jugador siempre puede sesgo de las probabilidades, y las mejores opciones no son transitivas.

Answer 4

Algunos grandes respuestas. Me gustaría tomar un poco diferente de la tachuela, y abordar la cuestión de la lucha contra el intuitivity. (Estoy bastante de acuerdo, por CIERTO)

He aquí cómo puedo hacer sentido de ella. Imaginar una columna de azar secuencial de la moneda-mezcle los resultados se imprimen en una cinta de papel, que consiste en las letras "H" y la "T".

Arbitrariamente corte una sección de esta cinta, y hacer una copia idéntica.

En una cinta, la secuencia de HTH y la secuencia HTT cada ocurrir tan a menudo, si la cinta es lo suficientemente largo.

Pero de vez en cuando el HTH instancias se ejecutan juntos, es decir HTHTH. (o incluso muy de vez en cuando HTHTHTH)

Esta superposición no puede suceder con HTT instancias.

Usa un marcador para recoger las "rayas" de los resultados exitosos, HTH en una cinta y HTT en el otro. Algunos de los HTH rayas serán más cortos debido a la superposición. En consecuencia, las brechas entre ellos, en promedio, será un poco más largo que en la otra cinta.

Es un poco como esperando un autobús, cuando en la media hay uno cada cinco minutos. Si los autobuses se pueden superponerse unos con otros, el intervalo será de algo más de cinco minutos, en promedio, porque en algún momento de los dos va a pasar juntos.

Si al llegar a un tiempo arbitrario, que tendrás que esperar un tiempo ligeramente mayor para el siguiente (primer lugar) en autobús, en promedio, si se les permite que se superponen.

Answer 5

Yo estaba buscando la intuición de este en el entero caso (como estoy obstinado a través de Ross' Intro. para los Modelos de Probabilidad). Así que yo estaba pensando entero de los casos. He encontrado esto ayudó:

Deje $A$ ser el símbolo necesario para empezar con el patrón que estoy esperando.

Deje $B$ ser el símbolo necesario para completar el patrón estoy esperando.

En el caso de una superposición de aproximadamente el$A=B$$P(A \cap \tilde{B})=0$.

Mientras que en el caso de que no se superponen $A \ne B$$P(A \cap \tilde{B}) \ge 0$.

Por lo tanto, vamos me imagino que tengo una oportunidad para acabar con el patrón en el siguiente sorteo. Yo dibuje el siguiente símbolo y no termine el patrón. En el caso de que mi patrón no se superponen, el símbolo dibujado podría todavía me permiten comenzar a construir el patrón nuevamente desde el principio.

En el caso de una superposición, el símbolo que necesitaba para terminar mi parcial patrón era el mismo que el símbolo como sería necesario para iniciar la reconstrucción. Así que no puedo hacer tampoco, y por lo tanto se tendrá que esperar hasta el próximo sorteo para tener la oportunidad de empezar a construir de nuevo.