Problema de tirada de dados de 100 caras

Question

¿Cuándo debo dejar de tirar si cuesta 1 $ cada tirada y sólo gano el valor de la tirada final que aparece en una tirada de dados de 100 caras? Mi intención es maximizar el beneficio y tengo tiradas ilimitadas

Answer 1

Esta pregunta es ambigua. ¿Significa

• Usted puede jugar a este juego sólo una vez y desea maximizar la esperado diferencia entre lo que se recauda al final y el coste de los rollos necesarios para llegar hasta allí? O bien,

• Puede jugar a este juego un número ilimitado de veces y desea maximizar su beneficio esperado por tirada a largo plazo?

Ambas interpretaciones conducen a estrategias muy diferentes cada una de las cuales sería excepcionalmente pobre si se aplicara en la otra circunstancia.

Primera interpretación.

Sea $T\subset \{1,2,\ldots, 100\}$ sea el conjunto de valores por los que se pretende cobrar una recompensa y sea $p=|T|/100$ sea su tamaño como proporción de todos los resultados. El número esperado de tiradas necesarias para observar un elemento de $T$ es (como es bien sabido e intuitivamente obvio) igual a $1/p = 100/|T|.$ Además, la recompensa esperada es la media de $T$ (porque, condicionado a $T,$ los rodillos se distribuyen uniformemente entre los valores de $T$ ). En consecuencia,

1. Para cualquier valor de $p$ quieres hacer la media de $T$ lo más grande posible. Así, $T = \{t, t+1, \ldots, 100\}$ debe consistir en $100p$ valores más altos posibles en el dado. Su media es $(100+t)/2$ y $p = (101-t)/100.$

2. Por lo tanto, su beneficio neto esperado es $(100+t)/2 - 100/(101-t).$ Como función de una variable real, aumenta suavemente hasta un máximo en $t = 101 - \sqrt{200} \approx 86.9$ y luego cae rápidamente, lo que implica que en función de un integral valor debe maximizarse ya sea en $86$ o $87.$ Es casi un cara o cruz, pero $t=87$ gana por muy poco.

Aquí tienes un gráfico de esta función.

Y un vistazo más de cerca a la región de interés (fíjese en la escala del eje vertical):

Segunda interpretación.

También podrías preguntar cuál es la mejor manera de recoger dinero en efectivo tirado en la calle: ¡Tómalo todo!

Imagina todas las tiradas futuras ante ti en orden, como esta secuencia generada aleatoriamente:

86  91 100   8 100  66  87   9  71  44  24  94  57   2  68  62  59  93  97  15 ...

Pagará $\$ 1$ para cada uno de estos rollos no importa qué. Usted recibirá, sin embargo, sólo aquellas recompensas en las que decidas detenerte.

Voy a hacer que tu elección sea sumamente fácil: ya que te has comprometido a apostar en cada tirada, ¡te dejaré echar un vistazo a todas para que decidas qué recompensas recoger! Seguramente no podrá hacerlo mejor sin echar un vistazo, así que esto le proporciona un límite superior de lo que podría conseguir.

Por ejemplo, si -según algunos- selecciona cualquier recompensa cuya tirada sea superior a 49, su lista de ganancias netas (recompensas menos las apuestas) comienza así

 85 90 99 -1 99 65 86 -1 70 -1 -1 93 56 -1 67 61 58 92 96 -1 ...

Si, por el contrario, se basara en los resultados de la primera interpretación de la pregunta para orientarse, sólo seleccionaría las recompensas en las que la tirada fuera superior a 86, su lista de rendimientos netos comenzaría así

 -1 90 99 -1 99 -1 86 -1 -1 -1 -1 93 -1 -1 -1 -1 -1 92 96 -1

Cuanto más restrictiva sea su regla de parada, más veces sustituirá un número positivo por un -1. A la larga, sólo empeora y empeora para ti mientras te contienes esperando que cualquier conjunto de números de parada especiales.

Este argumento abarca no sólo una regla de parada de umbral, sino incluso una secuencia arbitraria de reglas de parada de cualquier complejidad. Cualquier regla que hace que no cobre una recompensa reduce inmediatamente su rendimiento total.

Espere, puede objetar: ¿por qué no puedo simplemente decidir no apostar en la siguiente tirada? Adelante. Haré la misma oferta que antes, pero no se le permite echar un vistazo a la tirada antes de decidir no apostar. Porque ese es el caso, la lista de los rollos que usted do tendrá exactamente las mismas características probabilísticas que la lista con la que empecé esta respuesta: es una secuencia de resultados uniformes independientes.

Dije que espiar da un límite superior a las posibilidades. Sin embargo, ya que las mayores recompensas totales se pueden obtener sin mirar,

la estrategia óptima es cobrar una recompensa en cada turno, independientemente del resultado de la tirada. El valor esperado de cada tirada es $-1$ (por el coste de laminación) más $101/2$ (el valor esperado en un dado d100), un neto de $49.5.$

---

Si usted es creyente en cualquier otra estrategia, comprenda que al esperar a que se observe un valor alto, tenderá a pagar varias tiradas antes de ver ese número. Por ejemplo, si espera a ver un valor superior a 50, es fácil establecer (e intuitivamente obvio) que pagará dos tiradas de media para que eso ocurra. Cobrará un valor esperado de $(51+52+\cdots+100)/50 = 75.5$ pero habrás pagado $\$ 2$ por ese privilegio. La tasa media de rendimiento de su inversión es de sólo $(75.5-2)/2 = 36.75,$ notablemente inferior al ROI de $49.5/1 = 49.5$ con la estrategia óptima.

¿Aún no está convencido? Por los 20 rollos mostrados al principio, pagaré $20$ y recoger $1233,$ dejándome por $1213.$ Pagará lo mismo $20$ y sólo recogerá $1131,$ dejándote con $102$ menos que yo.

Answer 2

Sea $t \in [0,99]$ sea nuestro valor umbral de rechazo. En otras palabras, si el valor que rodamos es $> t$ entonces nos detenemos.

Entonces $p = 1 - \frac{t}{100}$ es la probabilidad de que nos detengamos. Esto significa que, por término medio, tardaremos $\frac{1}{p}$ rollos para terminar. Obsérvese que al parar recibimos un valor uniformemente distribuido sobre $[t+1,100]$ que es, por término medio $\frac{t+1+100}{2}$ . Por lo tanto, nuestro beneficio esperado es

$$ \frac{t+1+100}{2} - \frac{1}{p} = \frac{101 + t}{2} - \frac{100}{100 -t} $$

Iterando sobre los valores de $t$ nos da el valor máximo esperado en $t=86$ de 86,3571429 $ (lo que coincide con la simulación de Lynn que dio como resultado la misma regla de >= 87).

Consideremos ahora el caso en el que el jugador tiene acceso a una fuente suplementaria de aleatoriedad para tomar decisiones. Ahora definimos $t = i + r$ donde $i$ es un número entero $r \in [0,1)$ es el resto. Y establece la siguiente regla para el valor de la tirada $v$ :

• En $v \leq i$ Continuar
• En $v > i + 1$ Para
• En $v = i + 1$ se detiene con probabilidad $1-r$

Entonces la probabilidad de parada es $p = 1 - \frac{i+1}{100} + \frac{1-r}{100} = 1 - \frac{t}{100}$ . Dado que hemos parado, el pago esperado es el mismo que antes. Por tanto, la expresión del beneficio esperado sigue siendo la misma. Sólo que ahora podemos optimizar sobre números no enteros $t$ . Resolviendo esto se obtiene $t= 100 - 10\sqrt 2 \approx 85.858$ lo que supone un beneficio de $\frac{201}{2} - 10\sqrt 2 \approx 86.358$

Answer 3

He codificado esto en Python y he obtenido los siguientes resultados a partir de 1.000.000 de ejecuciones para cada prueba:

Prueba 1: Parada cuando lanzamiento >= 50:

Ganancias medias: \$73.07
Ganancias mínimas: \$35
Lanzamientos máximos: 20

Prueba 2: Parada cuando lanzamiento >= 87:

Ganancias medias: \$86.36
Ganancias mínimas: \$-4
Lanzamientos máximos: 92

Probé algunos valores de parada, y la parada después de rodar 87 o superior parecía dar los mejores resultados:

Aquí está mi código python:

import random
import numpy as np

def roll_dice():
    return random.randint(1, 100)

def stop(num, throw, limit=50):
    return throw >= limit

def winnings(num, throw):
    return throw - num

win_list = []
max_throws = 0
stop_at = 50
for run in range(1000000):
    for i in range(1, 101):
        throw = roll_dice()
        if stop(i, throw, stop_at):
            break
    win_list.append(winnings(i, throw))
    max_throws = max(max_throws, i)
print(f'Stopping when throw >= {stop_at}')
print(f'Average winnings: ${np.mean(win_list):.2f}')
print(f'Minimum winnings: ${np.min(win_list)}')
print(f'Maximum throws: {max_throws}')

Answer 4

El pasado es pasado y no importa para tu estrategia, así que después de rodar $i$ tiene la opción de $\$ X_i$ si $X_i$ está mostrando, o pagando \$1 para obtener el azar $\$ X_{i+1}$ para un total de $\$ X_{i+1}-1$ . El valor esperado de la siguiente tirada, y cada futuro rollo, es \$50-1=\$ 49.

Por lo tanto, si actualmente está recibiendo \$50 or higher you should stop, if you are currently getting less than \$ 49 deberías seguir adelante. Si usted está recibiendo actualmente exactamente \ $ 49 que son indiferentes en la expectativa y que necesita algún otro criterio - tal vez usted debe lanzar una moneda para decidir.

Answer 5

En primer lugar, lo único que importa a la hora de decidir cuándo parar es la última tirada. Otros lo han mencionado sin demostrarlo, así que aquí tienes un argumento a favor: tus ganancias dependen únicamente de tu última tirada. Tus tiradas anteriores no afectan en absoluto. Además, tu coste marginal no se ve afectado por las tiradas. Usted total El coste depende del número de tiradas anteriores, pero la optimalidad se basa en el coste marginal, no en el coste total. Como ni el coste ni el beneficio se ven afectados por las tiradas anteriores, podemos ignorarlas.

Por lo tanto, si debe volver a tirar se basa únicamente en cuál es la tirada actual. Así que hay n estrategias diferentes: parar en cuanto veas un $1$ Deténgase en cuanto vea un $2$ etc. Si $f(n)$ son las ganancias esperadas por seguir la enésima estrategia, entonces el problema es encontrar la $n$ que maximiza $f(n)$ . Entonces, ¿qué es $f(n)$ ? Bueno, tenemos un $\frac1{100}$ posibilidad de obtener $100$ . Y si $n<100$ entonces tenemos a $\frac1{100}$ posibilidad de obtener $99$ . Y así sucesivamente. En otras palabras, el valor esperado después de la siguiente tirada es $\frac{100+99+98+...n}{100}$ . Con algunos conocimientos de secuencias aritméticas, podemos ponerlo en forma cerrada como $\frac 1 {100}*\left(5050-\frac{n(n+1)}2\right)= \frac{10100-n(n+1)}{200} $ . También hay un $\frac{n-1}{100}$ posibilidad de no parar en la siguiente tirada, en cuyo caso estamos justo donde empezamos, excepto que hemos perdido un dólar. Así que $f(n) = \frac{10100-n(n+1)}{200}+ \frac{(f(n)-1)(n-1)}{100}$ .

$$f(n) = \frac{10100-n(n+1)+ 2(f(n)-1)(n-1)}{200}$$ $$200f(n) = 10100-n(n+1)+ 2(f(n)-1)(n-1)$$ $$200f(n) = 10100-n(n+1)+ 2(f(n)(n-1))-n+1$$ $$(200-2n+2)f(n) = 10100-n(n+1)-n+1$$ $$(202-2n)f(n) = 10100-n^2-2n+1$$ $$f(n) = \frac{10101-n^2-2n}{202-2n}$$

Esto tiene el valor máximo de 84,6176 en n = 85. Esto no es lo mismo que las respuestas anteriores, por lo que wuite posiblemente cometido un error con mi aritmética en alguna parte.