You roll an eight sided dice, and keep track of the cumulative sum. You can stop and take the sum at any time, but if the sum is ever greater than 8 then the game ends, and you get a payout of zero. What is the expected value of this game? What is the best strategy?
This question was from an interview preparation handbook, but didn't have a solution and I'm not quite sure how to solve it. In terms of best strategy, I was thinking along the lines of, say we have a cumulative sum of $s$, the expected payoff would simply be the probability of getting a number $n$ where $s+n > 8$ multiplied by $-s$ plus the expected payoff of the other numbers multiplied by their probabilities, and that should always be a positive number.
I'm not sure how to quantify this properly though!
A strategy should be a function $f(n,t)$ and $t$ where $n$ is the number of rolls and $t$ is the current total, and $f(n,t)$ is $0$ or $1$ if you should stop or continue. Let $T_f$ be your expected total using the strategy $f.$ Turnss out, the best strategy doesn’t depend on $n.$
If $t=8$ you obviously should stop.
If $4\leq t<8$ and you continue, you have at least a $1/2$ probability of losing on this roll, and at most a positive win of $8.$ So your expected value is no more than $4,$ so you do at least as well by stopping.
Continue in this way.
If $t=3,$ and you roll again, it will be your last roll, because your next $t$ will be at least $t\geq4.$ So your expected value will be $$\frac18 (4+5+6+7+8)=\frac{15}4>3.$$ This is an improvement.
So it pays to continue when $t=3.$
You can do the same for $t=1,2,$ or you can argue that if it pays off to continue at $t=3,$ it pays off to continue at $t=1,2.$
If $X_t$ is the value you get under this strategy when you have a $t$ total, your expected value at value is: $$E(X_t)=\begin{cases}t&t\geq 4\\ 3+\frac34&t=3\\ 4+\frac7{32}&t=2\\ 4+\frac{191}{256}&t=1\\ 5+\frac{695}{2048}&t=0 \end{cases}$$
So the expected value for the strategy is approximately $5.339.$
For a die with $n$ sides, $n$ even, stopping at $t\geq n/2$ works only for $n\leq 14.$
If $n$ is odd, stopping at $t\geq(n+1)/2$ works only for $n\leq 7.$
For general $n,$ you should stop when $$t>\sqrt{2n^2+2n+\frac14}-\left(n+\frac12\right)\approx(\sqrt2-1)\left(n+\frac12\right)$$