Threshold Strategies and Backward Induction for a Repeated Die Game

# TAKE AND ROLL calculate return


# TAKE AND ROLL calculate return












You are given a fair 20−sided die and 100 actions in a game. The die starts with upface 1. The two options you can perform are to roll and to take. Performing a roll re-rolls the current upface of the die. Performing a take allows you to cash out the current upface of the die. Note that the game does not end when you perform a take and that you do not have to roll between takes. Therefore, for example, you can just perform 100 takes on the initial 1 upface and walk away with $100 guaranteed. Your strategy is to cash out the upface when you roll at least some threshold n for the first time. You fix this n at the beginning of the game. Assuming rational strategy in selecting n, what is your expected payout on this game?

My approach is giving me a max expected profit of 1813 but it is wrong..

I assumed that n = 1 to allow me to cash out right from my first roll..

So now lets assume that, if I get a number >= k on a roll I will stop rolling and collect for the remaining moves. After hit and trial I got the value k = 18 for which the expected max return is the max - Now calculating the max - To get a no. greater than equal to 18 I require an expected 7 throws (on 7th throw I can expect to see >=18) So I have 94 moves with value {18,19,20} so my expected earning over 94 moves is - 94*19 = 1786 Now for the initial 6 moves I can't hold onto a number a keep collecting so the optimum is the order - Roll , collect , Roll , collect , Roll , collect. and on every collect I can expect to earn (av of numbers from 1 to 17) = 9 So on 3 collects I will earn 27 hence ,My total earning is 1813..

If you try with keeping k = 19 you will have 91 available moves with expected value being 19.5 so total earning is 91*(19.5) = 1774.5 now for the remaining 9 moves it is best to do C,R,C,R,C,R,C,R,C hence total amount collected is 1 + av(of numbers from 1 to 18 which equals 9.5) - 1 + 4*9.5 = 39 hence your earning is 1813.5 but since you have to atleast roll a number greater than equal to 1 to cash out you subtract the 1 hence here you total earning is 1812.5<1813...

What is wrong in my approach can you figure out

## Answer by Kermittfrog (score 2)

https://quant.stackexchange.com/a/80087

At closer inspection, this question resembles the problem of pricing an American option, i.e. finding the optimal exercise time/state. As such, it should be solvable using backwards induction.

To this end, I will first try to answer the original question of a threshold-based strategy, followed by providing the optimal (and only slightly better) approach.

### Threshold ansatz

Given a twenty-sided die with equally likely face value $1\leq F \leq 20$ and some threshold level $1\leq T\leq 20$, we know that the expected face given $T$ is $\mathrm{E}(F|F\geq T)=\frac{20+T}{2}$. Also, the probability of throwing a face of $T$ (or more) at exactly the $i$th throw is:

$$ \begin{align} P(F_i\geq T|F_1<T,\ldots,F_{i-1}<T)&=\left(1-\frac{20-T+1}{20}\right)^{i-1}-\left(1-\frac{20-T+1}{20}\right)^{i}\\ &=\left(\frac{T-1}{20}\right)^i\frac{21-T}{T-1} \end{align} $$

The expected strategy payoff given threshold $T$ is thus:

$$ \begin{align} EV(T)&=\sum_{i=1}^{100}(100-i)\frac{20+T}{2}P(F_i\geq T|F_1<T,\ldots,F_{i-1}<T)\\ &=\frac{21-T}{T-1}\frac{20+T}{2}\sum_{i=1}^{100}(100-i)\left(\frac{T-1}{20}\right)^i \end{align} $$

This expectation is easily calculated across $T$. We find:

| $T$ | Exepcted strategy value $EV(T)$ |
| ... | ... |
| 16 | 1728 |
| 17 | 1757.5 |
| 18 | 1773.33 |
| 19 | 1755 |
| 20 | 1602.368 |

i.e., $T=18$ indeed maximizes the expected payoff given a threshold strategy.

### Optimal stategy

Starting from the ultimate state of the system, we will iterate backwards and - for each state - decide, whether it would be beneficial to throw the die or simply keep the current face until the ultimate round.

To this end let $EV(n)$ denote expected value of the strategy when collecting the corresponding points backwards.

In the ultimate round, $n=100$, we will simply collect whatever face $F_n$ is facing upwards. In the second to last round, for each possible state of the current face, $1\leq F_{n-1} \leq 20$, we will decide whether we should keep the current face - and collect it twice, i.e. during rounds $n-1$ and $n$ - or roll the die, thereby gaining $E(V_n)$ on average, in the ultimate round. For each state in round $n-1$, the optimal decision yields the value $$ V_{n-1}(F_{n-1})=\max(2F_{n-1},E(V_{n}))) $$

In the third-to-last-round, $n-2$, we compare collecting $F_{n-2}$ three times to re-rolling the die and expecting a payoff $E(V_{n-1})$. The optimal decision again yields value: $$ V_{n-2}(F_{n-2})=\max(3F_{n-2},E(V_{n-1}))) $$

We repeat this method backwards until round $2$. In round one, we will always roll the die. The expected value of this strategy is then 1773.3399338.. which is slightly higher than the optimal value from above.

Especially for a smaller number of rounds, the strategy is (slightly) better: