La paradoja del lanzamiento de una moneda
Así que recientemente comencé a leer este fantástico libro de la revista Quanta titulado «La conspiración de los números primos» que cubre algunos de los problemas más grandes de las matemáticas modernas y una vez más fui un nerd atacado por un problema de matemáticas.
El libro explica que si Alicia lanza una moneda al aire buscando las dos primeras caras consecutivas, la encontrará después de, en promedio, seis lanzamientos. Si Bob está volteando buscando la primera instancia de cara y luego cruz, la encontrará en promedio después de cuatro volteos.
¿¡Que demonios!?
Las posibilidades de que aparezca HH son las mismas que las de que aparezca HT. ¡Son probabilidades independientes! ¿Cómo podrían resultar en resultados esperados tan diferentes?
Bueno, la prueba no es tan obvia, para empezar veamos una prueba del caso HH .
Entonces tenemos esta relación de recurrencia dada por esta cadena de Markov donde
Entonces, ¿qué significa esto? Elegí que el orden de los términos fuera bastante sugerente. Mira, una cuarta parte de las veces obtenemos HH en los primeros dos lanzamientos, la mitad de las veces obtenemos cruz y tenemos que reiniciar (produciendo 1+x lanzamientos) y una cuarta parte de las veces obtenemos HT y tenemos que reiniciar (produciendo 2 +x voltea).
Si resuelves esta recurrencia encontrarás x=6. Pero resulta que la recurrencia de HT es un poco diferente. En realidad se ve así:
Encontré esto aquí y tiene una explicación bastante buena, pero pensé en agregar mis dos centavos. Probablemente sea más fácil explicar esto de adentro hacia afuera, así que definamos nuestro término y que representa la cantidad de vueltas que tendremos que hacer para obtener nuestra T.
En otras palabras, si solo queremos saber cuántos lanzamientos necesitamos en promedio para obtener 1 cruz, es esto, que es 2.
Encontré que era una idea muy motivadora recordar que para obtener la secuencia HT necesitamos dos piezas, necesitamos una H y una T. Así que no importa qué cada secuencia que termine en HT tendrá la forma {algún número de Ts, al menos cero}{algún número de Hs, al menos uno}{exactamente una T}.
Entonces, en nuestro primer lanzamiento, la mitad del tiempo obtenemos una T y tenemos que reiniciar, por lo tanto, el término 1/2 (1 + x). Una vez que hemos encontrado la primera H la mitad de las veces, obtenemos otra H inútil y tenemos que voltearla de nuevo, por lo tanto, el término 1/2(1+y).
Si resuelves esto, de hecho obtienes 4.
Así que tengo una contribución más para agregar aquí, y esa es una prueba experimental. Si no me cree, puede intentarlo usted mismo, incluso incluí una verificación de cordura para mostrar que, en promedio, tomamos 2 lanzamientos para obtener cara (o cruz):
import scala.util.Random
val random = new Random()
def flipCoin(): Char = { if (random.nextBoolean()) ‘H’ else ‘T’ }
def flipUntilSequence(seq: String, history: String): Int = {
if(history.endsWith(seq))
history.length
else
flipUntilSequence(seq, history + flipCoin())
}
val hh_es= for (i <- Range (1, 1000000)) yield flipUntilSequence(«HH», «» )
val ht_es = for (i <- Range (1, 1000000)) yield flipUntilSequence(«HT», «»)
val h_es = for (i <- Range (1, 1000000)) yield flipUntilSequence(«H», «» )
println (s»Número promedio de lanzamientos para obtener cara: ${h_es.sum.toDouble / h_es.length}»)
println (s»Número promedio de lanzamientos para obtener HH $ {hh_es.sum.toDouble / hh_es.length}»)
println (s»Número promedio de lanzamientos para obtener HT $ {ht_es.sum.toDouble / ht_es.longitud}»)
Y, de hecho, el resultado de mi ejecución más reciente es:
Promedio de lanzamientos para obtener cara: 2.0016590016590015Promedio de lanzamientos para obtener HH 6.001767001767002
Promedio de lanzamientos para obtener HT 3.9996059996059996
Entonces, ¿hay una explicación simple en inglés de por qué esto funciona? Bueno, encontré muchas de las publicaciones en este hilo de Stack Overflow realmente útiles, pero particularmente esto en e. En pocas palabras, en el caso de HT podemos permanecer indefinidamente en el estado H_ y cada vez que acertamos una T hemos terminado, en el caso de HH cada vez que lanzamos una T tenemos que empezar de nuevo y esperar hasta el próximo lanzamiento de una H. El orden realmente importa aquí.
