# Weird Probability Question on a D20

I've been playing around with some problems related to discrete distributions, and I was wondering if I could get some help on a certain problem. I have a buddy that will roll a D20 at most $n$ times, and I can decide to stop after any particular roll or continue going until I finish the $n$th flip. I earn the dollar amount of the upper-facing value of the last roll. I've been playing around with trying to solve for what is the optimal strategy for this game, and I have a feeling that, since the expected payoff of any roll is $10.5,$ I believe that I should be rolling until I hit a value above $10,$ which is when I will stop. However, I am having a hard time figuring out the expected payoff of this strategy. Is there a particular way to go about this proof?

Your threshold for stopping should start quite high and decrease as you have fewer rolls remaining. Your sense of rerolling anything $10$ or below is correct if you only have one roll remaining. To see what you should do if you have two rolls remaining, you need the expected value of two rolls. You have $\frac 12$ chance of getting $11-20$ on the first roll, which you will keep, so your expected value is $\frac 12 \cdot 15.5 + \frac 12 \cdot 10.5=13$, so on the third to last roll you should only keep $14$ or above. Then you can figure the expected value of three rolls because you know the strategy. That tells you what to keep on the fourth to last roll and so on. You keep the third to last roll with probability $\frac 7{20}$ and it averages $17$ if you keep it, so the expected value of a three roll game is $\frac 7{20}\cdot 17+\frac {13}{20}\cdot 13=14.4$. Now you know that you should keep $15$ or above on the fourth to last roll and can compute the expected value.
This is an example of the Secretary Problem. You should reject every result up to $\frac{n}{e}$ (about 36.8%) of them then select the first roll which is greater than the best roll seen so far (or the last one if this doesn't happen).