100-sided dice roll problem

Question

When should I stop rolling if it costs $1 for each roll and I earn only the value of the final roll shown on a 100-sided dice roll? My intent is to maximise profit and I have unlimited rolls

Answer 1

This question is ambiguous. Does it mean

• You can play this game only once and you wish to maximize the expected difference between what you collect at the end and the cost of the rolls needed to get there? Or,

• You can play this game an unlimited number of times and you wish to maximize your expected profit per roll in the long run?

The two interpretation lead to very different strategies, each of which would be exceptionally poor if applied in the other circumstance!

First interpretation.

Let $T\subset \{1,2,\ldots, 100\}$ be the set of values for which you intend to collect a reward and let $p=|T|/100$ be its size as a proportion of all outcomes. The expected number of rolls needed to observe an element of $T$ is (as is well known and intuitively obvious) equal to $1/p = 100/|T|.$ Moreover, the expected reward is the mean of $T$ (because, conditional on $T,$ the rolls are uniformly distributed among the values of $T$). Consequently,

1. For any given value of $p$ you want to make the mean of $T$ as large as possible. Thus, $T = \{t, t+1, \ldots, 100\}$ must consist of the $100p$ highest possible values on the die. Its mean is $(100+t)/2$ and $p = (101-t)/100.$

2. Thus, your expected net profit is $(100+t)/2 - 100/(101-t).$ As a function of a real variable this rises smoothly to a maximum at $t = 101 - \sqrt{200} \approx 86.9$ and then falls rapidly, implying that as a function of an integral value it must be maximized either at $86$ or $87.$ It's almost a toss-up, but $t=87$ wins out by a tiny amount.

Here is a plot of this function.

And a closer look near the region of interest (notice the scale on the vertical axis):

Second interpretation.

You might as well ask what is the best way to pick up cash lying in the street: take it all!

Imagine all future rolls laid out before you in order, like this randomly generated sequence:

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

You will pay $\$1$ for each of these rolls no matter what. You will receive, however, only those rewards where you choose to stop.

I'm going to make your choice supremely easy: since you have committed to bet on each roll, I will let you peek at them all to decide which rewards to collect! Surely you cannot do better without peeking, so this provides an upper bound on what you might be able to achieve.

For instance, if--according to some--you select any reward where the roll exceeds 49, your list of net returns (rewards minus the bets) begins

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

If instead--if you were relying on the results of the first interpretation of the question for guidance--you select only rewards where the roll exceeds 86, your list of net returns begins

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

The more restrictive your stopping rule, the more times you will replace a positive number with a -1. In the long run, it just gets worse and worse for you as you hold back waiting for any set of special stopping numbers.

This argument covers not only a threshold stopping rule, but even an arbitrary sequence of stopping rules of any complexity. Any rule that causes you not to collect a reward immediately reduces your total return.

Wait, you might object: why can't I just decide not to bet on the next roll? Go right ahead. I will make the same offer as before, but you are not allowed to peek at the roll before deciding not to bet. Because that's the case, the list of the rolls that you do bet on will have exactly the same probabilistic characteristics as the list I began this answer with: it's a sequence of independent uniform outcomes.

I said that peeking gives an upper bound on the possibilities. However, since the greatest total rewards can be obtained without peeking,

the optimal strategy is to collect a reward on every turn regardless of the roll's outcome. Your expected value for each roll is $-1$ (for the cost of rolling) plus $101/2$ (the expected value on a d100 die), a net of $49.5.$

---

If you are believer in any other strategy, understand that by waiting until a high-ish value is observed, you will tend to pay for several rolls before seeing that number. For instance, if you wait to see a value exceeding 50, it is easy to establish (and intuitively obvious) that you will pay for two rolls on average for that to happen. You will collect an expected value of $(51+52+\cdots+100)/50 = 75.5$ but you will have paid $\$2$ for that privilege. The average rate of return on your investment is only $(75.5-2)/2 = 36.75,$ noticeably less than the ROI of $49.5/1 = 49.5$ achieved with the optimal strategy.

Still unconvinced? For the 20 rolls shown at the outset, I will pay $20$ and collect $1233,$ leaving me up by $1213.$ You will pay the same $20$ and will collect only $1131,$ leaving you with $102$ less than me.

Answer 2

Let $t \in [0,99]$ be our rejection threshold value. In other words, if the value we rolled is $> t$, then we stop.

Then $p = 1 - \frac{t}{100}$ is the probability that we stop. This then means that on average it will take us $\frac{1}{p}$ rolls to finish. Note that when we stop, we received a value uniformly distributed over $[t+1,100]$, which is on average $\frac{t+1+100}{2}$. Thus, our expected profit is

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

Iterating over the values of $t$ gives us the maximum expected value at $t=86$ of $86.3571429 (which is consistent with Lynn's simulation which resulted in the same rule of >= 87).

Ths analysis below is wrong, since the expected payout is incorrect. See my new answer for a fully probabilistic treatment

Now then let's consider the case where the player has access to a supplementary source of randomness in order to make decisions. Now we define $t = i + r$ where $i$ is a whole number $r \in [0,1)$ is the remainder. And establish the following rule for the roll value $v$:

• When $v \leq i$, continue
• When $v > i + 1$, stop
• When $v = i + 1$, stop with probability $1-r$

Then the probability of stopping is $p = 1 - \frac{i+1}{100} + \frac{1-r}{100} = 1 - \frac{t}{100}$. Given that we have stopped, the expected payout is the same as before. So the expression for the expected profit remains the same. Only now we can optimize over non-integer $t$. Solving this gives $t= 100 - 10\sqrt 2 \approx 85.858$ resulting in a profit of $\frac{201}{2} - 10\sqrt 2 \approx 86.358$

Answer 3

I coded this in Python and obtained the following results from 1,000,000 runs for each test:

Test 1: Stopping when throw >= 50:

Average winnings: \$73.07
Minimum winnings: \$35
Maximum throws: 20

Test 2: Stopping when throw >= 87:

Average winnings: \$86.36
Minimum winnings: \$-4
Maximum throws: 92

I tested a few stopping values, and stopping after rolling 87 or higher seemed to give the best results:

Here's my python code:

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

The past is past and doesn't matter for your strategy, so after roll $i$ you have the option of $\$X_i$ if $X_i$ is showing, or paying \$1 to get the random $\$X_{i+1}$, for a total of $\$X_{i+1}-1$. The expected value of the next roll, and every future roll, is \$50-1=\$49.

Thus, if you are currently getting \$50 or higher you should stop, if you are currently getting less than \$49 you should keep going. If you are currently getting exactly \$49 you are indifferent in expectation and you need some other criterion -- perhaps you should toss a coin to decide.

Answer 5

First, of all, the only thing that matters as far as deciding when to stop is the last roll. Others have mentioned this without proving it, so here's an argument for it: your winnings depend only on your last roll. You previous rolls don't affect it at all. Furthermore, your marginal cost is not affected by the rolls. You total cost depends on how many previous rolls you had, but optimality is based on marginal cost, not total cost. Since neither cost nor benefit are affected by previous rolls, we can ignore them.

Therefore, whether you should roll again is based solely on what the current roll is. So there are n different strategies: stop as soon as you see a $1$, stop as soon as you see a $2$, etc. If $f(n)$ is the expected winnings for following the nth strategy, then the problem is to find the $n$ that maximizes $f(n)$. So what is $f(n)$? Well, we have a $\frac1{100}$ chance of getting $100$. And if $n<100$, then we have a $\frac1{100}$ chance of getting $99$. And so on. In other words, the expected value after the next roll is $\frac{100+99+98+...n}{100}$. With some knowledge of arithmetic sequences, we can put that in closed form as $\frac 1 {100}*\left(5050-\frac{n(n+1)}2\right)= \frac{10100-n(n+1)}{200} $. There's also a $\frac{n-1}{100}$ chance of not stopping at the next roll, in which case we're right back where we started, except we're down a dollar. So $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}$$

This has the maximum value of 84.6176 at n = 85. This isn't the same as previous answers, so I wuite possibly made a mistake with my arithmetic somewhere.

Answer 6

Maybe I don't understand your question, in which case I apologise. The expected payoff after $n$ rolls is the value of the last roll. This is, $$ \mathbb{E}[R_n]=\sum_{i=1}^{100} p_i i = 50.5 $$ where $R_n$ is the revenue from the last roll; $R_n$ takes values $i=1,\ldots,100$ with each value having probability $p_i=1/100$. Therefore the expected payoff is not a function of $n$. The cost of $n$ rolls is $n$ dollars. So my expected payoff is $50.5-n$. The maximum expected payoff is for $n=1$.

Answer 7

As a stats learner some of the answers here went far above my head, but with my intuition I came to a similar conclusion so I thought I could be worth sharing my mental process in case it might help someone or to get it commented on by someone more expert.

With every new dice roll you are paying 1\$ so you want to increase the expect utility by at least 1\$.

Now let's say you already rolled a 99, you are going to make 99\$ and a new dice roll is "good" only if you get 100. The chances are $1/100$, so the expected utility is $0.01\$$. Rolling a dice again is not worth it.

What if you already got a 98? You can make 1\$ more by rolling a 99 or 2\$ more by rolling a 100. The two options are mutually exclusive and equally likely so we can just sum up their expected utility $0.01\$ + 0.02\$ = 0.03\$$. Not worth it again.

So we just need to find the value $n$ for which the sum of expect utilities is more than 1\$, which would mean, finding the $m = 100 - n$ for which $\dfrac{m*(m+1)}{2 * 100} > 1$ which is "the sum of the increases of the expected utilities for all the values greater than ours is greater than 1\$".

That gives us $n = 86$ with an increase in the expected utility of $1.05\$$.

Answer 8

Here is a function to compute the expected best profit of the game recursively, in Python. This value is 86.35, and it is also the case that for all values of last_roll greater than or equal to 87, the most profitable option is to stop playing right away (best_profit(last_roll, rolls) == last_roll - rolls). I do not know how to prove that mathematically, however. For values strictly less than 87 there exist both situations where continuing is more profitable, and situations where stopping is more profitable.

#!/usr/bin/env python3

from functools import cache

@cache
def best_profit(last_roll, rolls):
    # If the maximal possible profit in the next roll is less than or equal to zero, there is no profit in playing at all, stop immediately.
    if 100 - (rolls + 1) <= 0:
        return last_roll - rolls
    # If the profit of stopping is greater than or equal to the maximal possible profit of continuing, stop.
    if last_roll - rolls >= 100 - (rolls + 1):
        return last_roll - rolls

    return max(last_roll - rolls, 0.01 * sum(best_profit(next_roll, rolls + 1) for next_roll in range(1, 100+1)))

print(best_profit(0, 0))

Answer 9

Here we generalize on the other approaches but realize the same solution. The difference is that here we do not presume a stopping rule of the form suggested, but rather prove it is optimal.

We note that however many prior turns have been should not impact our current decision. It follows immediately that we should take the first roll (since we will not lose money even if we decide to stop after 1 roll). We thus take a fully probabilistic approach, whereby we stop after having seen a value $i$ with probability $p_i$, or $p=(p_1, p_2, \dots, p_{100})$. Then, defining $V(p) = \sum_i p_i i$, we have that our expected winnings, as a function of $p$ is:

$$ W(p) = -1 + \left(1 - \sum_i \frac{p_i}{100}\right)W(p) + \frac{V}{100} $$

where the middle term captures the expected winnings when we do not stop.

Rearranging gives: $$ W(p) = \frac{V - 100}{\sum_i p_i} $$

Then, $$ \frac{dW}{dp_j} = \frac{j \sum_i p_i - V + 100}{\left(\sum_i p_i\right)^2} $$

Note that this is strictly monotonically increasing in the index $j$. Thus, there can be at most a single value $j_0$ for which the above value is 0. For all $j > j_0$, the gradient is positive, and thus to maximize $W(\cdot)$, $p_j = 1$. Similarly, for all $j < j_0$, the gradient is negative, and thus $p_j = 0$. If there is such a value $j_0$, we let $k = j_0$. Otherwise, we let $k$ be the smallest index for which the gradient is positive. Then,

$$ k \sum_i p_i - V = -(1 + 2 + \dots + (100 - k)) $$ We note that $\sum_{i=1}^{13} i = 91$ and $\sum_{i=1}^{14} i = 105$. Thus, there is no $j_0$ value. Therefore, $100 - k = 13$ or $k = 87$. This then gives the rule: stop if the value seen is $\geq 87$.