You are given an even coin, and 50 flips of this coin. You can choose to flip, or cashout. Every time you flip a heads, $10 is added to your winnings. You can cashout only when a heads is present, But you will no longer be able to play the game. If you reach the end of the 50 flips, and the last flip is a tails, then you recieve no money. What is the optimal strategy for this game?
Solution
As with all optimisation questions, we will pose a strategy and then calculate various outcomes for each of those strategies. Our success metric will be expected value, as this will tell us how much money we will make per attempt. Let's begin by employing a simple strategy, whereby the first 49 flips are completed, and then (hopefully) take our money out on the last flip. Let's calculate the expected number of heads, denoting E[H] as the average number of heads per 49 coin flips: \[ E[H] = 49 * 0.5 = 24.5 \] There are two outcomes for the next result: We land a heads, achieving 25.5 total heads and taking out \( 25.5 * 10 = $255 \) dollars, or we land a tails, and lose everything. This gains an expected value of: \[ E[X] = 255 * \frac{1}{2} + 0 * \frac{1}{2} = $127.50 \] Now, we can certainly optimise this by allowing a higher chance of landing a heads and be able to withdraw our money. Now let's consider the event where we flip the coin 48 times, and then withdraw our money if either of the next 2 coin flips land on heads: \[ E[H] = 48 * 0.5 = 24 \] Now, there are 3 events that can occur:
1. We land a heads on the 49th attempt, bringing us to 25 heads flips, and we withdraw our money. This event has a \( \frac{1}{2} \) chance of occuring.
2. We land a tails on the 49th attempt, and then land a heads on the 50th attempt, bringing us to 25 heads flips, and allowing us to withdraw our money. This event has a \( \frac{1}{4} \) chance of occuring.
3. We land a tails on both the 49th attempt and 50th attempt, meaning we lose all our saved up money. This event has a \( \frac{1}{4} \) chance of occuring.
Converting this to expected value, we get: \[ E[X] = 250 * \frac{1}{2} + 250 * \frac{1}{4} + 0 * \frac{1}{4} = 250 * \frac{3}{4} = $187.50 \] If you haven't discovered a pattern yet, we can equate this into an equation, and solve to optimise for the number of coin flips to begin considering banking. If we decide to bank on the 50th throw, we will have \( E[X] = 10 (\frac{49}{2} + 1) * \frac{1}{2} \), if we decide to bank on the 49th throw and beyond, we will have \( E[X] = 10 * (\frac{48}{2} + 1) * \frac{3}{4} \), if we decide to bank on the 48th throw and beyond, we wil have \( E[X] = 10 * (\frac{47}{2} + 1) * \frac{7}{8} \). Thus, we can model this as: \[ E[X] = 10 * (\frac{50 - n}{2} + 1) * \frac{2^n - 1}{2^n} \] where \( n \) is 50 subtracted by the number before you will bank if a heads appears. We can use this to optimally calculate each value:
For n = 3: \[ E[X] = 10 * (\frac{47}{2} + 1) * \frac{7}{8} = 245 * \frac{7}{8} = $214.38 \] For n = 4: \[ E[X] = 10 * (\frac{46}{2} + 1) * \frac{15}{16} = 240 * \frac{15}{16} = $225.00 \] For n = 5: \[ E[X] = 10 * (\frac{45}{2} + 1) * \frac{31}{32} = 235 * \frac{31}{32} = $227.65 \] For n = 6: \[ E[X] = 10 * (\frac{44}{2} + 1) * \frac{63}{64} = 230 * \frac{63}{64} = $226.41 \] Since n = 5 generates a greater profit than n = 6, it seems like we have identified a local maximum. Therefore, the optimum strategy we found would be to start banking on any heads that appears after the 45th flip, which would return an average of $227.65 per game.
To further optimise this solution, we could introduce a dynamic programming system which updates on every roll. Although this method is impractical for quantitative trading, since you typically will not have access to program in the interview, it may be beneficial for you to bring this up.