Probabilidad de rompecabezas

Question

Me parece que este braintease en internet y no sabes cómo resolverlo. Para la segunda pregunta, Mi primer pensamiento es, a deducir de la situación cuando hay sólo 2 ranuras, luego 3, 4, .., n,.. ranuras. Pero me parece que no es tan fácil. Alguien puede darme una pista sobre esto? Muchas gracias!

1. Usted puede lanzar una moneda 100 veces o parada antes, que se les paga el porcentaje de jefes de su lanza, la estimación del límite superior de la valor del juego.

2. Hay una máquina de juego de azar con n-ranuras. Usted poner las bolas de uno por uno en la máquina, cada pelota tiene la misma probabilidad para obtener dentro de cada ranura. Puede detener el juego en cualquier momento. En la final será recompensada como este: por cada 1-bola de ranura, que son recompensados \$1; para cada k-bola de ranura (k>=2), se te penalizará \$k; para cada 0-bola de ranura usted es recompensado nada. ¿Cuál es su estrategia? Lo que se espera que el valor del juego?

Answer 1

Deje $E(h,n)$ ser el esperado ganancias (en virtud de la parada óptima estrategia) después de darle la vuelta a la moneda de $n$ veces y la obtención de $h$ cabezas.

Si le da la vuelta de nuevo, sus ganancias esperadas se $\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1)$.

Si usted no voltear de nuevo, sus ganancias esperadas se $\dfrac{h}{n}$.

Por lo tanto, se tapa de nuevo iff $\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1) > \dfrac{h}{n}$, y sus ganancias esperadas satisfacer $E(h,n) = \max\left\{\dfrac{h}{n},\dfrac{1}{2}E(h,n+1)+\dfrac{1}{2}E(h+1,n+1)\right\}$.

Trivally, si usted mueve de un tirón $100$ veces y obtener $h$ jefes, sus ganancias se $E(h,100) = \dfrac{h}{100}$.

El uso de un ordenador, podemos utilizar el recursividad para obtener $E(0,0) \approx 0.783894497678384$.

Como resulta, parando después de $h > t$ está bastante cerca de la estrategia óptima. Después de golpear a el por encima de la recursividad, la actual estrategia óptima puede ser formulada como "Después de la $n$-th flip, parada si usted ha conseguido, al menos, $h(n)$ cabezas", donde $h(n)$ está dada por la siguiente tabla:

$\begin{matrix} n&\ 1&\ \ 2&\ \ 3&\ \ 4&\ \ 5&\ \ 6&\ \ 7&\ \ 8&\ \ 9&\ 10\\ h(n)&\ 1&\ \ 2&\ \ 2&\ \ 3&\ \ 4&\ \ 4&\ \ 5&\ \ 5&\ \ 6&\ 6\end{de la matriz}$

$\begin{matrix} n&11&12&13&14&15&16&17&18&19&20\\ h(n)&7&8&8&9&9&10&10&11&11&12\end{de la matriz}$

$\begin{matrix} n&21&22&23&24&25&26&27&28&29&30\\ h(n)&12&13&13&14&14&15&15&16&16&17\end{de la matriz}$

$\begin{matrix} n&31&32&33&34&35&36&37&38&39&40\\ h(n)&17&18&18&19&19&20&20&21&21&22\end{de la matriz}$

$\begin{matrix} n&41&42&43&44&45&46&47&48&49&50\\ h(n)&22&23&23&24&24&25&25&26&26&27\end{de la matriz}$

$\begin{matrix} n&51&52&53&54&55&56&57&58&59&60\\ h(n)&27&28&28&29&29&30&30&31&31&32\end{de la matriz}$

$\begin{matrix} n&61&62&63&64&65&66&67&68&69&70\\ h(n)&32&33&33&34&34&35&35&36&36&37\end{de la matriz}$

$\begin{matrix} n&71&72&73&74&75&76&77&78&79&80\\ h(n)&37&38&38&39&39&40&40&41&41&42\end{de la matriz}$

$\begin{matrix} n&81&82&83&84&85&86&87&88&89&90\\ h(n)&42&43&43&43&44&44&45&45&46&46\end{de la matriz}$

$\begin{matrix} n&91&92&93&94&95&96&97&98&99&100\\ h(n)&47&47&48&48&48&49&49&50&50&0\end{de la matriz}$

---

Para el juego de pinball, tus ganancias en cada pelota son independientes el uno del otro. Así, usted debería jugar el juego todo el día, o no, dependiendo de si sus ganancias esperadas es positivo o no. Este es un sencillo cálculo, por lo que voy a dejar de hacerlo.

Answer 2

Para un trivial estimación del tirón de la moneda del juego, usted no puede ganar más de $1$ (todos los jefes), por lo que es un límite superior.

Menos trivial, tenemos que definir nuestra estrategia. Supongamos que usted ha volteado $h$ jefes y $t$ colas. Deje $V(h,t)$ ser el valor del juego en este punto. Claramente $V(h,t) \ge \frac h{h+t}$ porque nos puede parar ahora y conseguir que. Si lanzamos de nuevo, la alternativa es $\frac 12(V(h+1,t)+V(h,t+1))$ también contamos $V(1,0)=1$ porque no se puede hacer mejor y parada, mientras que $V(0,1)=\frac 12(V(1,1)+V(0,2))$ porque no se puede hacer peor y debe voltear de nuevo.

Me sugieren que se debe detener en cualquier momento $h \gt t$ Si usted decide voltear una vez y dejar de cualquier manera, usted empezar con $\frac h{h+t}$ y el comercio que para $\frac {2h+1}{2(h+t+1)}$ que es menos. La repetición tiene usted en el mismo barco-algunos handwaving aquí.

Una estrategia es la siguiente: Usted mueve de un tirón la primera vez. Cabezas obtendrá $1$. Las colas que se mantenga voltear hasta que la ley de los grandes números se activa y tiene (aproximadamente) la mitad de los jefes y obtenga $\frac 12$. El valor del juego es $\frac 34$ Usted puede hacer un poco mejor por tirar cuando usted está exactamente a la mitad de las cabezas-si usted gana usted está delante, si usted pierde, usted puede mantener mover de un tirón y (con una probabilidad de $1$) volver a por lo menos, incluso. El valor debe ser un poco más de $3/4$

Para el pinball caso, la lógica es la misma. Evaluar si la siguiente bola mejora su rentabilidad y jugar o no. Creo que usted puede demostrar que usted no necesita preocuparse acerca de los efectos a largo plazo-sólo pregunte si esta bola mejora mi rentabilidad, pero no he probado nada de esto.