¿Alguna vez dejar de rodar el dado?

Question

Tiene seis lados morir. Mantener un total acumulado de las tiradas de dados. (E. g. si sacas un 3, luego 5, luego la 2, el total acumulado es de 10.) Si el total acumulado es siempre igual a un cuadrado perfecto, entonces usted pierde, y se va a casa con nada. De lo contrario, usted puede elegir para ir a casa con un pago de su importe total acumulado, o a tirar el dado de nuevo.

Mi pregunta es acerca de la estrategia óptima para este juego. En particular, esto significa que estoy en busca de una respuesta a esta pregunta: si mi total acumulado es de $n$, ¿debo elegir para rodar o no rodar con el fin de maximizar mi total acumulado? Hay algunos entero $N$ después de que la respuesta a esta pregunta es siempre rollo?

Creo que no es un entero, y suponemos que este entero es de $4 dólares. Mi razonamiento es que el cuadrado de los números son lo suficientemente escaso para el valor esperado de estar siempre en aumento tirando el dado de nuevo.

Como un ejemplo, supongamos que el total acumulado es de $35 dólares. Balanceo de un $1$ y golpear 36 significa que nos vamos a casa con nada, por lo que el valor esperado de rodar una vez es:

$$E(Rollo|35) = \frac 0 6 + \frac {37} 6 + \frac {38} 6 + \frac{39} 6 + \frac {40} {6} + \frac{41}{6} = 32.5$$

es decir,

$$E(Rollo|35) = \frac 1 6 \cdot (37 + 38 + 39 + 40 + 41) = 32.5$$

Pero el siguiente recuadro, después de 35 $a$ es $49$. Así, en el caso de que no nos rollo de $36$, obtenemos para mantener lanzar el dado sin ningún riesgo, ya que el total acumulado es de menos de $42$. Para simplificar, digamos que si nos rollo y no alcanzó los us $36$, entonces vamos a rodar una vez más. Que morir-roll tiene un valor esperado de $3.5$. Esto significa que el valor esperado de rodadura en $35$ es:

$$E(Rollo|35) = \frac 1 6 \cdot (40.5 + 41.5 + 42.5 + 43.5 + 44.5) = 35.42$$

Y desde $35.42 > 35$, la maximización de ganancias opción es tirar de nuevo. Y esta estrategia puede ser aplicada para cada total. No veo, cuando esto deje de ser razonable se mueven, aunque no he intentado verificar que sea computacionalmente. Yo intuitivamente pensar acerca de esto en términos de las distintas secuencias.

Recientemente he tenido esta pregunta en una entrevista de trabajo, y pensé que era muy interesante. (Y contra-intuitivo, ya que esta maximización de ganancias de la estrategia siempre se traduce en ir a casa con nada.)

Answer 1

Cómo utilizar su observación en general:

Acabo de comprobar las cosas por $35$ no es indicativo de que el caso general, que para grandes valores es diferente. Tome su argumento y el uso general de la plaza $n^2$.

Supongamos que usted está en $n^2-1$. Usted puede dejar con $n^2-1$, o usted puede rodar. En un rollo, que lo pierde todo con la probabilidad $\frac{1}{6}$. Con probabilidad $\frac{5}{6}$ obtendrá al menos $(n+1)^2-6 = n^2 + 2n - 5$ por rodar hasta que no es seguro. Así, por un simple límite inferior, queremos saber si $\frac{5}{6}(n^2 + 2n - 5)$ es mayor que $n^2-1$. Para grandes $n$, este no es el caso, y realmente podemos obtener una cota superior por razonamiento similar:

---

Un límite superior:

[Una versión ordenada de la original de la siguiente manera. Manteniendo el original límite superior habría requerido un par de líneas adicionales de la lógica, así que he aumentado un poco que sea breve.]

Un límite superior: Supongamos que estamos entre $n^2 a 5$ y $n^2-1$. Si nos rollo, el mejor, las cosas podrían ir para nosotros sería perder $\frac{1}{6}$ la hora, y, cuando no perdemos, nos metemos en el rango de $(n+1)^2-6$ $(n+1)^2-1$ (la más alta de la que podría obtener sin tomar otro riesgo). Sólo la comparación de valoración actual, que está operando al menos $n^2 a 5$ por, al menos, $\frac{5}{6}(n^2 + 2n)$ en el momento de llegar a la siguiente decisión. La diferencia es de $-\frac{1}{6}n^2 + \frac{5}{3}n + 5$. Para $n \geq de 13$ esto es negativo. Así que si usted está en $13^2-k$ para $1 \leq k \leq 6$, no rollo. (Más $$ n de hacer esta diferencia aún más negativo da a esta conclusión. Véase el párrafo siguiente para obtener más detalles).

Detalles adicionales para la lógica de dar a este límite superior: Deja de $W_n$ el actual esperado de las ganancias de su estrategia para la primera vez que están dentro de los $6$ de $n^2$, incluyendo también a veces usted arrestado o detenido por su cuenta a un valor inferior. Lo anterior muestra que, si su estrategia de siempre incluye en marcha cuando dentro de los $6$ de $n^2$ para $n \geq de 13$, entonces $W_{n+1}$ es de menos de $W_n$. Por lo tanto, no hay que preocuparse acerca de cualquier cosa que aumentar sin límite, y usted debe de hecho nunca ir por encima de $168$.

---

Fácil límite inferior (números pequeños):

Valores bajos: Para $n = 3$ tenemos $(5+6+7+8)/6 > 3$ así rollo a $n = 3$. Excepto para el caso $n = 3$, si hacemos rodar en $n$, vamos a dejar de obtener al menos $\frac{5}{6}(n+3)$. Así que si $\frac{5}{6}(n+3) - n > 0$, se vuelve a tirar. Esto nos dice a tirar de nuevo para $n < 18$ por lo menos. Ya que no podemos parar si no podemos busto, esto nos dice a tirar de nuevo para $n \leq 18$.

---

Un algoritmo y los resultados reportados para el caso general:

La obtención de una solución general: Iniciar con valores esperados de $n$ y una decisión de "estancia" asignados a $n$ para $163 \leq n \leq 168$. Luego trabajar hacia atrás para obtener EV y las decisiones en cada menor de $n$. A partir de esto, verás donde a hit/estancia y lo que el conjunto de accesible valores con la estrategia óptima es.

Una rápida secuencia de comandos escribí salidas de los siguientes: 30, 31, 43, 44, 45, 58, 59, 60, 61, 62, y el 75+. Usted nunca va a superar los 80. El general EV de que el juego es de aproximadamente 7.2. (Estándar de descargo de responsabilidad que usted debe programar usted mismo y de verificación.)

Answer 2

Si usted mantener lanzar el dado para siempre, se llegará a un cuadrado perfecto con probabilidad 1. Intuitivamente, cada vez que estés cerca de una plaza (dentro de la distancia de 6), tiene una probabilidad de 1/6 a golpear la plaza. Esto ocurre infinidad de veces, y por lo que está obligado a golpear un cuadrado con el tiempo.

Un poco más formalmente, supongamos que se tira el dado infinitamente a menudo lo que sucede. Su trayectoria (la secuencia de sumas parciales) tiene la propiedad de que la diferencia entre puntos adyacentes es de entre $1$ y $6$. En particular, para cada número $N$, habrá un punto de $x$ en la trayectoria tal que $N-6 \leq x < $ N. Si $x$ es el primer punto, entonces usted tiene una oportunidad de $1/6$ llegará a $N$ como su siguiente punto. Además, si $N_2 > N_1+6$, a continuación, estos eventos son independientes. Por lo que su probabilidad de golpear a $N_1$ o $N_2$ en el primer tiro una vez "en rango" es $1-(5/6)^2$. El mismo argumento funciona para cualquier número finito de puntos separados, y dado un número infinito de puntos, no importa cuán distante, llegamos a la conclusión de que golpeó a uno de ellos casi seguramente.

Answer 3

Si usted denotar la ganancia esperada de todos los futuros lanzamientos cuando ya se han acumulado $X$ y lanzar un $Y$ por $G(X,Y)$, entonces este es:

• $G(X,Y) = $indefinido, si $X$ es un cuadrado. (No es relevante, pero acabo de mencionar).
• $G(X,Y) = -X$, si $X$ no es un cuadrado, pero $X+$ Y es un cuadrado.
• $G(X,Y) = Y+MAX\left(0,\frac{1}{6}\sum_{i=1}^6 G(X+Y,i)\right)$ de otra manera.

Los dos primeros son fáciles de ver, en la última, la suma calcula la ganancia esperada de todos los futuros lanzamientos excluyendo este lanzamiento, y el de máxima con un 0 se toma debido a que sólo seguir jugando si el futuro que se espera obtener es positivo.

He hecho una tabla de excel de este, con $1\le Y \le 6$ y $1\le X \le 188$. He encontrado que al aumentar el límite superior de $X$, los valores esperados para una baja de $X$ no cambio; con el límite superior de $188$ confío en que todos los valores hasta $160$ (pero no tengo ninguna prueba).

En esta tabla, el beneficio esperado es negativo por $X=30, 31, 43, 44, 45, 58, 59, 60, 61, 62, 75, 76, 77, 78, 79, 80, \ldots$. Me detengo aquí, porque estos son los seis números consecutivos, y para llegar a lo más alto de los números que usted va a llegar a uno de ellos. Así que, según mi excel de los cálculos, la mejor estrategia es jugar hasta llegar a uno de los números en la lista.

---

Actualización: yo no había visto la actualización de aes respuesta todavía, pero ahora veo que de forma independiente se llegó a la misma serie de números.

Answer 4

Ampliación de @aes s 'solución de la simulación, mis cálculos sugieren que, de hecho, siempre estar cuando dentro de 6 de un cuadrado perfecto, para una gran plaza.

En primer lugar, vamos a lanzar este como un problema de programación dinámica:

$V\left(n\right)=\begin{casos} 0 & \hspace{1em}\existe k\in\mathbb{N} s.t. k^{2}=n\\ \max\left\{ n,\frac{1}{6}\sum\limits_{m=1}^{6}V\left(n+m\right)\right\} & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n \end{casos}$

Es decir, su valor condicional en la que cuenta actualmente la suma total de $n$ es dada por la elección de estancia (toma $n$) o un promedio de más de valores futuros, a menos de $n$ es un cuadrado perfecto.

Para hacer este computable, considere la posibilidad de un número finito de versión del problema, donde se nos de la fuerza $V(n)=n$ para todo $n$ pasado cierto umbral de $N$; llamar a esta aproximación $\tilde{V}\left(n;N\right)$.

$\tilde{V}\left(n;N\right)=\begin{casos} 0 & \hspace{1em}\existe k\in\mathbb{N} s.t k^{2}=n\\ \max\left\{ n,\frac{1}{6}\sum\limits_{m=1}^{6}\tilde{V}\left(n+m\right)\right\} & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n\cap n<N\\ n & \hspace{1em}\nexists k\in\mathbb{N} s.t. k^{2}=n\cap n\geq N \end{casos}$

Me aproximó con el siguiente código en R (lento, lo sé):

value_functions<-c()

NNN<-10000
squares<-cumsum(seq(1,2*ceiling(sqrt(NNN+6))-1,by=2))

for (NN in ceiling(.8*NNN):NNN){
  values<-0:(NNN+6)
  values[squares+1]<-0
  for (nn in (NN-1):0){
    values[nn+1]<-ifelse(nn %in% squares,0,
                         max(nn,sum(values[(nn+2):(nn+7)])/6))
  }
  value_functions<-rbind(value_functions,values[0:NNN])
}

Aquí un complot para $N=9990,\ldots,10000$, $n=1,\ldots,200$ (que no podemos decirles a las parcelas por separado de $N$ aparte sugiere convergencia):

Puede ser difícil de ver, pero básicamente lo que está pasando es:

1. en un cuadrado perfecto, el valor es 0
2. justo después de que, estamos seguros, por algún tiempo, y vamos a rodar seguro. porque tenemos la certeza de que vamos a rodar muchas veces, el valor no aumenta (que el dinero está garantizado).
3. a las 6 antes de que el siguiente cuadrado perfecto, o el valor se desploma--ahora hay un riesgo de fracaso si decidimos continuar.
4. justo antes de esto, nuestro valor aumenta-hemos eliminado algunos de los riesgos de incumplimiento por llegar, por ejemplo, de 7 a menos de un cuadrado, el cual garantiza que vamos a ser capaces de rodar de nuevo libre de riesgo.

Edificio en @aes 's encontrar, aquí se la cuenta a la que nos abandonan, según mi simulación:

  [1]   30   31   43   44   45   58   59   60   61   62   75   76   77   78   79   80   94   95   96   97   98   99  115  116  117  118  119  120  138  139  140  141  142  143  163  164  165  166
 [39]  167  168  190  191  192  193  194  195  219  220  221  222  223  224  250  251  252  253  254  255  283  284  285  286  287  288  318  319  320  321  322  323  355  356  357  358  359  360
 [77]  394  395  396  397  398  399  435  436  437  438  439  440  478  479  480  481  482  483  523  524  525  526  527  528  570  571  572  573  574  575  619  620  621  622  623  624  670  671
[115]  672  673  674  675  723  724  725  726  727  728  778  779  780  781  782  783  835  836  837  838  839  840  894  895  896  897  898  899  955  956  957  958  959  960 1018 1019 1020 1021
[153] 1022 1023 1083 1084 1085 1086 1087 1088 1150 1151 1152 1153 1154 1155 1219 1220 1221 1222 1223 1224 1290 1291 1292 1293 1294 1295 1363 1364 1365 1366 1367 1368 1438 1439 1440 1441 1442 1443
[191] 1515 1516 1517 1518 1519 1520 1594 1595 1596 1597 1598 1599 1675 1676 1677 1678 1679 1680 1758 1759 1760 1761 1762 1763 1843 1844 1845 1846 1847 1848 1930 1931 1932 1933 1934 1935 2019 2020
[229] 2021 2022 2023 2024 2110 2111 2112 2113 2114 2115 2203 2204 2205 2206 2207 2208 2298 2299 2300 2301 2302 2303 2395 2396 2397 2398 2399 2400 2494 2495 2496 2497 2498 2499 2595 2596 2597 2598
[267] 2599 2600 2698 2699 2700 2701 2702 2703 2803 2804 2805 2806 2807 2808 2910 2911 2912 2913 2914 2915 3019 3020 3021 3022 3023 3024 3130 3131 3132 3133 3134 3135 3243 3244 3245 3246 3247 3248
[305] 3358 3359 3360 3361 3362 3363 3475 3476 3477 3478 3479 3480 3594 3595 3596 3597 3598 3599 3715 3716 3717 3718 3719 3720 3838 3839 3840 3841 3842 3843 3963 3964 3965 3966 3967 3968 4090 4091
[343] 4092 4093 4094 4095 4219 4220 4221 4222 4223 4224 4350 4351 4352 4353 4354 4355 4483 4484 4485 4486 4487 4488 4618 4619 4620 4621 4622 4623 4755 4756 4757 4758 4759 4760 4894 4895 4896 4897
[381] 4898 4899 5035 5036 5037 5038 5039 5040 5178 5179 5180 5181 5182 5183 5323 5324 5325 5326 5327 5328 5470 5471 5472 5473 5474 5475 5619 5620 5621 5622 5623 5624 5770 5771 5772 5773 5774 5775
[419] 5923 5924 5925 5926 5927 5928 6078 6079 6080 6081 6082 6083 6235 6236 6237 6238 6239 6240 6394 6395 6396 6397 6398 6399 6555 6556 6557 6558 6559 6560 6718 6719 6720 6721 6722 6723 6883 6884
[457] 6885 6886 6887 6888 7050 7051 7052 7053 7054 7055 7219 7220 7221 7222 7223 7224 7390 7391 7392 7393 7394 7395 7563 7564 7565 7566 7567 7568 7738 7739 7740 7741 7742 7743 7915 7916 7917 7918
[495] 7919 7920 8094 8095 8096 8097 8098 8099 8275 8276 8277 8278 8279 8280 8458 8459 8460 8461 8462 8463 8643 8644 8645 8646 8647 8648 8830 8831 8832 8833 8834 8835 9019 9020 9021 9022 9023 9024
[533] 9210 9211 9212 9213 9214 9215 9403 9404 9405 9406 9407 9408 9598 9599 9600 9601 9602 9603 9795 9796 9797 9798 9799 9800 9994 9995 9996 9997 9998 9999

---

Todavía no estoy totalmente satisfecho de que tenemos un totalmente riguroso solución todavía.

Básicamente, todo lo que hemos hecho hasta ahora ASUME un número finito de soluciones. Mi simulaciones son cruxed en que siempre podemos encontrar un punto de parada; lo mismo para @aes. Su límite superior se supone que estamos operando en $n^2-1$ para $(n+1)^2-1$, pero, en el lenguaje del problema como se ha indicado anteriormente, está la realidad de negociación de $n^2-1$ para $V\left(\left(n+1\right)^2-1\right)$. Si este es en sí mismo infinito, todo el problema se desata.

Es decir, todavía no estoy convencido de que hemos encontrado un límite superior--una vez que se prueba un límite superior, las simulaciones por mí, @aes y @Pakk toda la línea.

Answer 5

El juego puede ser reducido a la decisión de cerca de cada cuadrado. Se debe decidir a intentar superar el de la plaza, hay (una vez pasado 9) una probabilidad fija de éxito, vamos a llamar a $p$ (puede ser calculado exactamente, pero eso no es importante aquí).

Considerar en primer lugar el juego sin la pérdida, así que si llegamos a la plaza, nos acaba de ir a casa a llevar el dinero hasta ahora obtenidos.

En ese caso, por supuesto, que nunca deja de rodar. Pero podemos demostrar, que el valor esperado es, sin embargo, finito: Por cada vez que salimos de una plaza $n^2$ podemos garantizar la seguridad de la diferencia con el siguiente cuadrado $(n+1)^2$ como un premio. Esta liquidación asciende a $(n+1)^2-n^2=2n+1$.

En consecuencia, el valor esperado sería de aproximadamente $\sum_{n=1}^{\infty}(2n+1)p^n$. Este convergente suma. Si queremos saber la expectativa bajo la condición de que ya superó los $m$ cuadrados, es de $W_m=\sum_{n=1}^{\infty}(2(n+m)+1)p^n$, que es lo que el futuro es "vale la pena".

Si ahora volver al otro juego, en el que las continuas es no libre, pero incurres en una siempre creciente costo (el de la probabilidad ponderada del coste de cada plaza es de $C_m=m^2(1-p)$ como $m^2$ es la cantidad que tendría que renunciar, si llegamos a la plaza $m^2$ y $(1-p)$ es la oportunidad para golpear), que es el "costo" tenemos que pagar para el futuro.

Ahora sólo hay que comparar la "pena del futuro" hemos calculado que con el "coste del futuro".

El valor del futuro $W_m$ incrementa linealmente en $m$ (significado de la toma de la decisión), mientras que la probabilidad ponderada coste para continuar el juego $C_m$ aumenta cuadráticamente en $m$ (significado de la toma de la decisión).

Así que la respuesta es: Sí, que dejaría de lanzar el dado en algún momento como el costo esperado de permanecer en el juego superará a la ganancia esperada en algún momento.