10-Sided Die Strategy
Jane Street
You're given a fair 10-sided die. You roll it once. Then, you're given a choice: either take the amount you rolled, or roll again and take the sum of both rolls if the sum is not above 10. If the sum is above 10, you get nothing. What's your optimal strategy?
Answer
When you're asked to give your optimal strategy, you'll need to devise a decision rule. So you roll once, and then you're faced with a choice: you either roll again or you don't. So how do you decide when to roll again? You should roll again if you expect to win more by rolling again than by keeping your first roll, i.e. if expected value of re-rolling is higher than your first roll. Let's look at an example:
Imagine you first rolled a 2, then you will lose everything if your second roll is 9 or 10, and otherwise you're fine. So how much do you expect to win by re-rolling? Well, 2 out of 10 possibilities give you 0, and in 8 out of 10 possibilities you get your second roll plus the first roll. Second roll has an equal chance of being any of the numbers which don't make you lose (1-8), so we have: $E(\text{re-roll}|2) = \frac{2}{8}\cdot 0 + \frac{8}{10}\cdot (2 + \frac{1+2+3+4+5+6+7+8}{8})=5.2$. So if we keep our first roll - we get 2, and if we re-roll - we expect to get 5.2. So we should re-roll.
Now imagine our first roll was an 8. Then we lose if second roll is anything above 2, so re-rolling gives us on average: $E(\text{re-roll}|8) = \frac{8}{10}\cdot 0 + \frac{2}{10}\cdot (8 + \frac{1+2}{2})=1.9$. So in this case, we expect a higher score by keeping our first roll (2) than by re-rolling (1.9).
Since we re-roll on a 2, and keep our first on a 8 - the tipping point must be somewhere in between. In an interview scenario, you can simply evaluate a few more cases to see where the tipping point is. Or you can notice the pattern: if we rolled x first, there are always x out of 10 possible second rolls that get us above 10 (i.e. we lose). So there's $\frac{x}{10}$ chance we lose on our second roll, vs $\frac{10-x}{x}$ chance we're fine. In case we're fine, we get x plus the value of the second roll, which is on average $\frac{1+2+...+10-x}{10-x} = \frac{(10-x)\cdot(10-x+1)}{2\cdot (10-x)}=\frac{11-x}{2}$. We used a well-known result that the sum of first N numbers is $\frac{N\cdot (N+1)}{2}$- make sure to know it. Putting all of this together, the expected payoff of re-rolling given we first rolled x is: $$E(\text{re-roll}|x) = \frac{x}{10}\cdot 0 + \frac{(10-x)}{10}\left(x + \frac{11-x}{2}\right)=\frac{(10-x)(x+11)}{20}$$Last remaining question is: when is this expected payoff greater than our first roll, i.e. when is $\frac{(10-x)(x+11)}{20}>x$? Solving this quadratic equation, we see it's when x<4.34. Therefore, our optimal strategy is: if your first roll is above 4 - keep it, else - re-roll.
Note that in a real interview, they probably wouldn't ask you to derive the entire solution: they're more likely interested in seeing if you can spot the pattern and set up the equation, or try out a few cases manually to see where the boundary is.