100-sided dice roll problem 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
 A: 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}')

A: 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.
A: 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$
A: 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.
A: 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$.
A: 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))

A: 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\$$.
A: 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$.
