Coin Tossing Game Optimal Strategy

Question

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

Answer 1

It really is as simple as "the bet is in your favor-take it." $S=x$. You win $3^{100}-1$ with probability $2^{-100}$ and lose $1$ with almost certainty. This presumes somebody can pay you that much. The expected win is then $\frac {3^{100}-1}{2^{100}}-1(1-\frac 1{2^{100}})\approx 4\cdot 10^{17}$

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, then your expectation is $1.5(\frac {x-S}2+\frac {x+2S}2)=1.5(x+\frac S2)$ which (given the rules) is maximized when $S=x$. 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.