Coin Tossing Game Optimal Strategy
I was recently asked this question in an interview, but was completely stumped as to how to even begin answering it - it's been bugging me ever since, and I thought it was quite a nice question, so hopefully someone on here can help me out. Any help would be appreciated! Here goes:
You start off with £100 and you toss a coin 100 times. Before each toss you choose a stake $S$ which cannot be more than your current balance $x$ (so your maximum stake for the first toss is £100). If the coin comes up heads, you win $2S$ and your new balance is $x+2S$. If it comes up tails, you lose your stake and have $x-S$. How do you choose your stake so as to maximise your expected winnings from the game, not including the initial balance?
Cheers,
Boris
Solution 1:
It really is as simple as "the bet is in your favor-take it." $S=x$. You win $100(3^{100}-1)$ with probability $2^{-100}$ and lose $100$ with almost certainty. This presumes somebody can pay you that much. Then the expected win is $$\frac{1}{2^{100}} \cdot 100(3^{100}-1) -(1-\frac 1{2^{100}}) \cdot 100\approx 4\cdot 10^{19}.$$
To maybe make this less unbelievable, imagine a two round game. Clearly on the last throw, you want to bet all you have, increasing your expected fortune by $50\%$. On the first throw, your expected balance is $\frac {x-S}{2}+\frac {x+2S}{2}=x+\frac{S}{2}$ which (given the rules) is maximized when $S=x$. If you won on the first flip, you now have 3S, so you can now bet $S_{2}$ with the condition that $S_{2} \leq 3S$. Your expected balance after the second flip is then $\frac{3S-S_{2}}{2} + \frac{3S+2S_{2}}{2} = \frac{6S+S_{2}}{2} = 3S+\frac{S_{2}}{2}$, which is again maximized if $S_{2}=3S$, so that your expected balance will be $3S+\frac{3S}{2} = \frac{9S}{2}$, and your expected profit of the second round (assuming you won on the first flip) will now be $\frac{9S}{2}-3S=\frac{3}{2}S=\frac{S_{2}}{2}$.
Alternately, your result is the same if you interchange the two flips. Since you should be all on the last flip, you should on the first as well.
Solution 2:
In my opinion this calls for the Kelly Criterion (http://en.wikipedia.org/wiki/Kelly_criterion). In this case, the fraction of your wealth that should be bet is $\frac{0.5 \times 3-1}{3-1}$.