Análisis de "Pequeños dados Dungeon" (I)

Question

Considere el siguiente de un solo jugador del juego: en un principio, no hay una olla de $\$0$. On each turn, the player may opt to end the game and collect the contents of the pot, or roll a single die. In the latter case, if the roll is $1$, the game is over and the player collects nothing. Otherwise, the amount of the die roll (from $\$2–\$6$) is added to the pot, and the player gets another move. The player continues rolling until they either get a $1$, y cobro nada, o la opción de llevarse el bote. Nos gustaría encontrar la estrategia óptima para este juego, y el beneficio esperado bajo la estrategia óptima.

Un simple (pero no es del todo correcto), el análisis va de esta manera: Cualquier estrategia racional debe tomar la forma de "Stop si y sólo si el bote tiene un valor de al menos $\$S$." If the pot contains $\$P$, a continuación, la ganancia esperada de la próxima tirada de dados es $\frac16(-P+2+3+4+5+6 )$ dólares. Esto es positivo siempre que $P\ge 20$, por lo que el jugador debe rodar hasta que el bote llega a $\$20$ o más y, a continuación, dejar y recoger.

De hecho, esta es una estrategia óptima, pero el análisis no es exactamente correcto, porque se supone, erróneamente, que la ganancia esperada por el éxito de la tirada de dados es exactamente $\$4$. But actually the expectation is a little bit more than this, because a successful die roll not only adds $\$4$ a la olla, que permite la posterior morir rollos que se pueden agregar más. De hecho, las estrategias de $S=20$ $S=21$ rendimiento idéntico espera que las rentabilidades de $\$8.141794893727$.

Un análisis más profundo de la siguiente manera: Vamos a $X_S(P)$ ser el esperado de la cantidad ganada por la siguiente parada-a-$S$ estrategia al $\$P$ is already in the pot. Then $X_S$ satisface la siguiente inusual de recurrencia:

$$X_S(P) = \begin{cases} P & \text{if %#%#%} \\ \frac16\sum_{i=2}^6 X_S(P+i) & \text{otherwise} \end{casos} $$

Estamos interesados en el comportamiento de $P\ge S$, la cual se puede calcular exactamente el uso de esta recurrencia. Esto es tedioso, así que he tenido el ordenador. $X_S(0)$ está maximizada, como ya se ha mencionado, para$X_S(0)$$S=20$.

Mis preguntas son:

1. Hay un método más sencillo para calcular el $S=21$ sin la ayuda de la computadora?
2. Hay un argumento que muestra que $X_S(0)$?

Answer 1

Deje $X(P)$ denotar el valor esperado del juego en su totalidad, con \$$P$ en el bote. Por lo tanto $$X(P)=\max(P,\frac{1}{6}\left(0+X(P+2)+X(P+3)+X(P+4)+X(P+5)+X(P+6)\right)$$

Debido a $X(P)\ge P$, $X(P+2)\ge P+2$ (etc) y la clavija y ha $$X(P)\ge \frac{5P+20}{6}$$

Ahora para$P< 20$, $P< \frac{5P+20}{6}$ así que no será efectivo hasta por lo menos $P=20$. Por otro lado, para todos los $k\in\mathbb{N}$,$X(P+k)\le X(P)+k$. Prueba: Jugar dos partidos en paralelo, uno con un extra \$k in the pot. If you bust, the extra money doesn't help, and if you cash out you've got an extra \$k.

Ahora, supongamos $X(P)>P$ pero $X(P-1)=P-1$. Tenemos $$6(P-1)\ge X(P+1)+X(P+2)+X(P+3)+X(P+4)+X(P+5)$$ $$X(P+2)+X(P+3)+X(P+4)+X(P+5)+X(P+6)>6P$$ $$6P-6-X(P+1)>6P-X(P+6)$$ $$X(P+1)+5\ge X(P+6)>X(P+1)+6$$

Esta contradicción demuestra que una vez $X(P)=P$ $X(P+k)=P+k$ todos los $k\in \mathbb{N}$. Además, para algunos $P$ suficientemente grande debemos tener $X(P)=P$ ya que de lo contrario el derecho a la estrategia sería jugar para siempre, el cual arroja un valor esperado de \$0 almost surely. Set $P^\estrella de$ to be the maximal value such that $X(P^\estrella)>P^\estrella de$; from the above we have $P^\estrellas\ge 19$.

Tenemos $P^\star<20$ desde $$6P^\star<X(P^\star+2)+X(P^\star+3)+X(P^\star+4)+X(P^\star+5)+X(P^\star+6)=5P^\star+20$$

Por lo tanto $P^\star=19$, y la mejor estrategia es mantener rodando mientras tenemos 19 o menos. Para encontrar el valor esperado del juego original, es decir,$X(0)$, tenemos que trabajar hacia atrás.

$X(20)=20, X(21)=21$, etc.

$X(19)=\frac{1}{6}(21+22+23+24+25)=\frac{115}{6}$

$X(18)=\frac{1}{6}(20+21+22+23+24)=\frac{55}{3}$

$X(17)=\frac{1}{6}(\frac{115}{6}+20+21+22+23)=\frac{631}{36}$

Esto es demasiado para calcular a mano, pero estoy seguro de que alguien puede escribir un par de líneas de código para entenderlo.