¿Por qué es esta que tira la moneda probabilidad problema sin resolver?

Question

Usted juega un juego de lanzar una moneda buena. Usted puede parar después de cualquier juicio, momento en el que le pagan en dólares el porcentaje de cabezas volteadas. Así que si en el primer juicio que girar la cabeza, usted debe parar y ganar \$100 debido a que usted tiene el 100% de los jefes. Si usted lanza una cola y una cabeza, se podría detener y ganar \$50, o continuar, con la esperanza de que la relación va a exceder de 1/2. Esta segunda estrategia es superior.

Un papel por Medina y Zeilberger (arXiv:0907.0032v2 [matemáticas.PR]) dice que es una sin resolver problema determinar si es mejor continuar o detener después de haber volteado 5 cabezas en 8 ensayos: aceptar \$62.50 o de la esperanza de más. Es fácil simular este problema, y es claro desde limitada, incluso los datos experimentales de que es mejor seguir (tal vez más de un 70% de probabilidad de que usted va a mejorar \$62.50):

Mi pregunta es básicamente: ¿por Qué esto es difícil de probar? Presumiblemente, no es tan difícil para escribir una expresión para la expectativa de superar 5/8 en términos de la distribución binomial acumulativa.

---

(5 de diciembre de 2013). Un artículo sobre este tema acaba de ser publicado:

Olle Häggström, Johan Wästlund. "Riguroso análisis por computadora del Chow-Robbins juego." (pre-diario arXiv enlace). La American Mathematical Monthly, Vol. 120, Nº 10, Diciembre De 2013. (Jstor enlace). Desde el Resumen:

"En particular, nos confirman que con 5 cabezas y 3 colas, detenerse es óptima".

Answer 1

Acepto Qiaochu la respuesta de "¿has probado a hacer en realidad?" Me hizo probar ahora, y ahora puedo apreciar el desafío. :-) El papel que he citado se refiere a otro por Chow y Robbins desde 1965 que tiene una hermosa formulación, mucho más clara que la acumulables binomios con el que he luchado. Permítanme explicarlo, porque es realmente genial.

Para la estrategia natural que he mencionado en los comentarios (y repetido por Raynos), deje que $f(n,h,t)$ ser el beneficio esperado si usted comienza con $h$ jefes y $t$ colas, y deja que el juego continúe no más de $n$ más ensayos. Entonces no es fácil recursiva formulación de $f$: $$f(n,h,t) = \max \left( \frac{1}{2} f(n,h+1,t) + \frac{1}{2} f(n,h,t+1) , h/(h+t) \right) $$ porque usted tiene una oportunidad igual de aumentar a $h+1$ jefes o $t+1$ colas en la próxima flip si continúa, y se obtiene la relación actual, si usted se detenga. Ahora, cuando $h+t=n$, usted necesita para hacer un "límite" de la asunción. Suponiendo que la ley de un gran número de grandes $n$ lleva a que el valor razonable de $\max ( 1/2, h/n )$ en este caso. Ahora todo lo que necesita hacer es llenar la tabla para todos los $h$ y $t$ valores $n=h+t$. La respuesta real es el límite cuando $n \rightarrow \infty$, pero el uso de grandes $n$ se aproxima a este límite.

Después de la Medina y Zeilberger documento fue publicado, de hecho apenas hace unas tres semanas, un muy cuidadoso cálculo usando la formulación recursiva fue hecho por Julian Wiseman y reportados en esta página web. La conclusión es que me notable: "Elegir seguir reduce el beneficio esperado [de 0.625] para 0.62361957757." Esto todavía no es una prueba, pero la "respuesta" que se conoce en la actualidad. Así que mi "es claro desde limitada, incluso los datos experimentales que" estaba completamente equivocado! Estoy encantado de aprender de mi error.

Answer 2

Esto parece estar relacionado con Gittins Índices. Gittins los Índices son una manera de resolver este tipo de parada óptima problemas para algunas clases de problemas, y, básicamente, una forma de equilibrio de cuánto se espera de ganar dado su conocimiento actual y cuánto más se podría obtener al poner en riesgo la obtención de más información sobre el proceso (o la probabilidad de salir cara, etc).

Bruno

Answer 3

Probablemente estoy haciendo algo mal, pero...

Si usted juega para un número n de vueltas más y obtener k jefes, su porcentaje será (5+k)/(n+8). La probabilidad de que esto ocurra es Binomial[n,k]/2^n. Sumando sobre todos los k para un n dado, tenemos:

ex2[n_] = Sum[(5+k)*Binomial[n,k]/2^n, {k,0,n}]/(n+8)  

Las matemáticas le da a este como: 1/2 + 1/(8+n)

Así, si jugamos para un número n de vueltas más, nuestro valor esperado es 1/2 + 1/(8+n).

Sustrae el 5/8 ya tenemos y la simplificación de los rendimientos -1/8 + 1/(8+n), que es obviamente negativa para cualquier número natural n.

Por favor crítica.