Manera ingeniosa de resolver problemas de tipo P (el patrón A aparece antes que el patrón B) en un proceso de lanzamiento de una moneda

Consideremos una moneda justa y un juego de lanzamiento infinito. Con frecuencia nos preguntaban cómo calcular la probabilidad de patrón A apareciendo antes del patrón B dónde A y B ambos son una de las ocho cuerdas { H , T } 3 . En principio, todos estos pueden resolverse mediante cadenas de Markov o análisis de primer paso. Pero estos dos métodos a veces pueden implicar una buena cantidad de cálculo. Por lo tanto:

Pregunta : ¿existe algún enfoque ingenioso que no requiera muchos cálculos que pueda resolver todo este tipo de problemas? (Vamos a limitarnos a { H , T } 3 por el momento y no considerar patrones más largos)

Un amigo mío sugirió una buena solución para encontrar P(THH antes de TTT):

ingrese la descripción de la imagen aquí

Explicación:

Dado que el primer lanzamiento = H significa empezar de nuevo, no tenemos que manejar este evento. Si el primer lanzamiento = T, el árbol binario de eventos se grafica como arriba, y vemos que entre todos los casos que dan como resultado un resultado determinado (es decir, no reinicios), las posibilidades de T H H apareciendo primero a la de T T T aparecer primero es ( 1 / 4 + 1 / 8 ) : ( 1 / 4 ) = 3 : 2 .

¿Cómo concluimos entonces que la probabilidad requerida = 3 / 5 ? La forma en que lo veo es que el árbol anterior en realidad define una "estructura fractal" en todo el espacio de probabilidad: entre todas las ramas de "comenzar de nuevo", la relación de las posibilidades de T H H apareciendo primero a la de T T T aparecer primero es siempre 3 : 2 . Por lo tanto, la proporción general también es 3 : 2 , de ahí la conclusión.

Sin embargo, lo anterior solo funciona cuando A y B tener un prefijo común. Si en cambio queremos T H H antes H T H entonces no se aplica porque no hay más estados de "comenzar de nuevo", supongo. Además, el enfoque anterior adolece de falta de explicabilidad y claridad matemática (por ejemplo, ¿cómo se supone que uno debe explicar la intuición como "estructura fractal" a alguien que no está familiarizado con este problema?)

Entonces, ¿hay algún enfoque mejor que sea más ampliamente aplicable, más explicable o más eficiente? ¡Gracias!

Sí, un método ingenioso es encontrar una fórmula recursiva para la probabilidad según el método de tu amigo (ver "comenzar de nuevo")
@ZubinMukerjee, lamentablemente, no creo que funcione para patrones con prefijos diferentes. no habría empezar de nuevo.
el método de recursión funciona, pero la transición de estado puede ser mucho más complicada (y si es demasiado complicada, puede que no valga la pena). por ejemplo, en su ejemplo THH vs TTT, todos los "reinicios" vuelven al estado T original. Esto no es necesariamente cierto. por ejemplo, si estuviera comparando TTTT con THTH, una secuencia "no decisiva" como THTT volvería al estado TT, mientras que una secuencia "no decisiva" como THH volvería al estado T original.

Respuestas (1)

Una forma divertida de resolver esto es con martingalas. Voy a dar la explicación intuitiva, aunque no es difícil hacer esto perfectamente matemáticamente riguroso. También me disculpo de antemano por la extensión de esta respuesta, pero trataré de justificar al final por qué esta es una forma útil de pensar.

El esquema: un crupier lanza una secuencia infinita de monedas hasta que aparece la secuencia THH o HTH. Hay dos líneas de apostadores, llámelas línea A y línea B.

La línea A está llena de apostantes que esperan ver THH. Así es como funciona: el apostador n.º 1 ("Aaron") primero se acerca al crupier y coloca una ps 1 apueste a probabilidades iguales a que la primera moneda sea T. Si gana, entonces mantendrá ps 2 , y lo apostará todo a que la próxima moneda será H. Si gana eso , apostará su ps 4 en la siguiente moneda siendo H. Si eso sucediera también, tomará su ps 7 beneficio (ya que uno de los dólares era suyo) y se marcha feliz; todo el juego se cerrará para todos los jugadores.

Detrás del apostador #2 hay otro mejor ("Barb") que apuesta exactamente de la misma manera, pero una moneda detrás de Aaron, y el apostador #3 ("Carl") se comporta de la misma manera; también lo hace cualquier otra persona en la fila.

Examinemos cómo se desarrollaría esto. Supongamos que la cadena de monedas del crupier es THTTHH en ese orden. Aaron apuesta primero; gana su primera apuesta desde que la primera moneda era T! También gana su segunda apuesta... solo para perder su tercera apuesta y salir con una pérdida neta de ps 1 . Barb tiene el mismo destino, pero más rápido; ella pierde su dólar inicial inmediatamente. Carl gana un juego pero pierde el segundo, sufriendo el mismo destino final. El cuarto apostante ("Diana"), sin embargo, está destinado a ganar, y se irá con una red de ps 7 . Tenga en cuenta que la siguen dos apostadores más ("Eva" y "Frank"), quienes pierden inmediatamente su primer dólar.

Ahora, a la línea B. Estos apostadores esperan ver HTH y realizarán los mismos tipos de apuestas con el crupier en la misma secuencia de lanzamientos de monedas... pero lo harán en la dirección opuesta. Es decir, el crupier ofrecerá sus dólares y hará apuestas de doble o nada en H, T, H en ese orden.

Así es como se desarrollaría esto con la secuencia anterior de lanzamientos de monedas. El primer apostador ("Mike") toma inmediatamente un dólar del apostador, porque la primera moneda era una T en lugar de la H que estaba buscando. (Recuerde, es la misma estructura de apuesta que con la línea A, pero la secuencia de monedas es diferente, y la dirección de ganancias y pérdidas se invierte). El segundo apostante ("Nelly") paga un dólar al crupier después de ver H, y luego paga dos dólares al comerciante después de ver a T, pero recupera todo su dinero (más una ganancia en dólares) cuando llega el próximo T. Esperemos que vea la idea clave aquí: el destino de todos los apostantes es el mismo, excepto posiblemente los últimos tres antes de que finalice el juego.En este caso, solo el último apostador de la línea B sigue en juego cuando finaliza el juego, y ese apostador pagará un dólar al apostador (neto).

La otra idea clave es que cada apuesta realizada es justa, lo que significa que, en promedio, las tenencias netas del crupier no cambian (consulte la justificación técnica a continuación). Esto es bastante útil, porque el juego termina precisamente de dos formas que podemos analizar con detenimiento. Nuevamente, tenga en cuenta que todos los apostadores antes de los últimos tres en cualquier línea son irrelevantes; el distribuidor ha tomado ps 1 de cada línea Un apostante y ha dado ps 1 a cada apostador de la línea B. Entonces, ¿qué sucede con los últimos tres en cada línea?

  1. Si el juego termina en una secuencia THH como la anterior, entonces de la línea A los últimos tres apostadores toman 7 , − 1 , y − 1 dólares del distribuidor. Los apostadores de la línea B toman 1 , 1 , y − 1 dólares del distribuidor. Por lo tanto, el distribuidor paga ps 6 en este caso.

  2. Si el juego termina en cambio en una secuencia HTH, entonces los apostantes de las últimas tres líneas A toman − 1 , 3 , y − 1 dólares del crupier mientras que los apostantes de la línea B toman − 7 , 1 , − 1 dólares del crupier (pago total: − ps 6 ).

Dejar pag denote la posibilidad de que THH venga antes que HTH. Entonces, el pago neto esperado del crupier es

mi [ pagar ] = pag ⋅ 6 + ( 1 − pag ) ⋅ ( − 6 )
pero dado que todas las apuestas fueron justas, este pago esperado debe ser 0 . De este modo,
0 = pag ⋅ 6 + ( 1 − pag ) ⋅ ( − 6 ) ⟹ pag = 1 / 2
para estas secuencias particulares.

Por qué me encanta este enfoque: es rápido y fácil de analizar cualquier enfrentamiento cara a cara de cualquier secuencia de 3 monedas. ¡Pero observe lo rápido que podría generalizar esto también a una racha de 4 monedas! Para enfrentamientos cara a cara de norte -rayas de monedas, tu única tarea es analizar cuidadosamente el comportamiento del final norte apostadores

¡Pero espera! ¡Hay más! También puedes usar este esquema de apuestas para pensar en otras preguntas interesantes. ¿Quieres saber el número esperado de lanzamientos antes de ver HTH? Solo considere una línea de apostadores HTH y cuente la ganancia que el crupier ha obtenido al final. ¿Quieres saber el tiempo de espera esperado para el primero de HTH y THH? Tenga dos líneas de apostadores, pero deje que ambas líneas hagan apuestas en la dirección normal (es decir, cómo se comportó la línea A en el ejemplo que describí). ¿Quiere hablar sobre dibujar letras al azar de la A a la Z y esperar la secuencia ABRACADABRA? Juegue el mismo juego, pero ajuste las proporciones de pago de las apuestas para que sean 25:1 en lugar de 1:1. Este es un enfoque increíblemente poderoso que generaliza muy bien y requiere solo una complejidad computacional mínima.

Justificaciones técnicas: El hecho de que cada apuesta realizada con cada apostador sea justa implica que las tenencias netas del crupier constituyen una martingala . El teorema de parada opcional se aplica en este caso porque se puede demostrar que el tiempo de parada tiene una expectativa finita (puede estar dominado por una variable aleatoria geométrica, por ejemplo) y los incrementos de la martingala están acotados.

Una adición más: el problema al que te refieres a menudo se llama el juego de Penney. Si desea ver la matriz completa de ventajas de cualquier secuencia de 3 monedas sobre cualquier otra secuencia de 3 monedas, puede encontrarlas aquí: plus.maths.org/content/os/issue55/features/nishiyama/index
Gracias. Conozco la martingala y el teorema de parada opcional, etc. Es bueno poder abarcar estos problemas muy bien dentro del marco de la martingala.
Ah, bien. No estaba seguro de su familiaridad con las martingalas, así que traté de escribirlo desde una perspectiva no técnica e incluir todos los antecedentes necesarios, ¡pero me alegro de que no fuera necesario!
Lo siento, pero todavía es un poco ambiguo para mí qué son exactamente la martingala y el tiempo de parada en la aplicación del teorema de parada opcional. ¿Te importaría elaborar un poco? (Está bien ser puramente técnico/matemático/probabilístico y dejar de lado los antecedentes de juegos de azar/apuestas, etc.) Gracias.
Claro, consulte 17.3.2 de lo siguiente como referencia: pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf
Gracias. Aunque todavía se basa en un contexto de apuestas, intentaré que sea libre de apuestas.
Puede que me equivoque, pero me parece que lo que estás buscando está en la parte superior de la página 235 (comenzando con "Describimos la situación con un poco más de precisión"). La metáfora del juego persiste para guiar la intuición, pero el variables desordenadas y tiempos de parada están ahí.
Gracias. Creo que lo seguí, pero también creo que las formulaciones en esa sección son bastante descuidadas. No estoy seguro si me estoy perdiendo algo, pero: nunca me convence por qué norte t s es un mg (porque en la definición de A t s , τ > t no es predecible, y creo que es un error tipográfico y debería haber sido τ ≥ t ), y también la parte que concluyeron mi ( τ ) = 2 + 8 del hecho de que norte t s es un mg es extremadamente confuso, en el que creo que en realidad usaron ∑ s = 1 τ norte t s en cambio (si la suma sigue siendo un mg, lo que creo que es cierto).
En conjunción con tu respuesta, creo que la forma general de resolver este tipo de problemas es la siguiente: 1). Si la computación mi ( τ patrón ) , solo debemos considerar una línea de apostadores que apuestan en este patrón, y un crupier, y el pago neto (o ingreso) del crupier ∑ s = 1 τ norte t s y aplique el teorema de parada opcional en este mg; 2). Si la computación PAG ( patrón A antes del patrón B ) , deberíamos dos líneas de apostadores apostando respectivamente en A , B con un distribuidor, y el pago total (mg): ∑ s = 1 τ ( norte t A , s − norte t B , s ) luego aplique la parada opcional.
Por cierto, utilicé su enfoque para obtener la misma respuesta que obtuve con mi "enfoque de árbol". Y resulta que su enfoque es mucho más fácil de implementar en programas de computadora y mucho más fácil de generalizar a patrones competitivos más largos de igual longitud.
Hola, siento molestarte de nuevo, pero encontré un problema técnico al aplicar el teorema de parada opcional cuando queremos obtener mi ( τ ) es decir, cuando solo hay una línea de apostadores y el pago del crupier está al día t es ∑ s = 1 t norte t s que usamos como la martingala. Sin embargo, en tal escenario parece que no se aplica ninguna de las tres condiciones para el teorema de parada opcional del tiempo discreto. Claramente, (a) y (c) fallan, (b) es cierto pero no sabemos mi ( τ ) < ∞ a priori por lo que tampoco podemos usarlo...
Puedes argumentar que mi ( τ ) está dominado por un valor geométrico (por lo tanto, tiene una expectativa finita), de la siguiente manera: cuando se espera una longitud norte secuencia, dividir el intervalo de tiempo en tamaño- norte incrementos -- es decir [ 0 , norte − 1 ] , [ norte , 2 norte − 1 ] , … . La probabilidad de que la secuencia ocurra en cualquier bloque en particular es estrictamente menor que uno, y dado que los bloques son disjuntos, estas ocurrencias son independientes. Por lo tanto, la secuencia ocurrirá eventualmente en dicho bloque, el tiempo de espera será finito porque esta es una variable geométrica, y el tiempo para que eso ocurra será limitado τ .
Manera ingeniosa de resolver problemas de tipo P (el patrón A aparece antes que el patrón B) en un proceso de lanzamiento de una moneda
RespuestasAquíPolítica de privacidad1y, 0v