# 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

• There was a Project Euler problem where your objective was to maximize the chance you finish with at least (as I recall) $10^9$. The thought process is different. Nov 19, 2012 at 15:41
• "not including the intial balance" is irrelevant; that's just an additive constant that doesn't affect the maximization. Jan 13, 2020 at 7:19

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.

• Thanks Ross - I really appreciate your help. If you're willing, I extended the question slightly here: math.stackexchange.com/questions/246565/… Nov 28, 2012 at 16:11
• Can you explain how you get 3^100 − 1, and why do you subtract a lose of 1, i.e. why is this not £100? May 22, 2013 at 23:02
• @timboj: yes, it should be winning $100(3^{100}-1)$ You end with $100\cdot 3^{100}$ and started with $100$, so that is the profit. May 23, 2013 at 3:31
• @RossMillikan I'm not sure why you say that the expectation is $1.5(x+s/2)$ and not just $(x+s/2)$. Mar 20, 2018 at 18:14
• @AntoniParellada: it gets factored in automatically. Here it is $1-2^{-100}$, almost certain. You have to win all $100$ flips or you are broke. If you are not broke, you have lots of money, enough to make the expected value huge. The only reason not to bet all you have is that you have something else you want to maximize than expected value. Economists call it utility and it is supposed to reflect that fact that money has declining utility, but you need to specify it exactly to have a problem that can be solved. Sep 18, 2020 at 20:53

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}$.

• To maximize the expected winnings you should bet your whole bankroll (as @Ross suggests in his answer). The problem with doing this, is that at some point (with probability 1) you will lose everything you have. This is the idea of Kelly's bet, it maximizes the growth of your wealth, and keeps you safe from losing it all. Note that the expectation of betting it all will be larger than betting Kelly, but with Kelly you will not lose everything. Mar 23, 2018 at 8:08

Long comment on the risk :

While this's not an answer , it's still highly related to the question and I want to show how crazy the risk is growing using the idea of sharp ratio .

Assume the bet is a constant fraction of current wealth $$f$$ .

The expected return is (which's maximized at $$f=1$$) $$E[X] = \sum_{k=0}^{100}\frac{1}{2^{100}}\binom{100}{k} (1+2f)^k(1-f)^{100-k}100$$ $$= \frac{100}{2^{100}} (2+f)^{100}$$ and $$E[X^2] = \sum_{k=0}^{100}\frac{1}{2^{100}}\binom{100}{k} (1+2f)^{2k}(1-f)^{2(100-k)}100^2$$ $$= \frac{100^2}{2^{100}} (5f^2 + 2f + 2)^{100}$$ The sharp ratio is $$\frac{E[X] - 100}{\sqrt{E[X^2] -E[X]^2}}$$ $$= \frac{(\frac{1}{4}f^2 + f + 1)^{50} - 1}{\sqrt{(\frac{5}{ 2}f^2 + f + 1)^{100} - (\frac{1}{4}f^2 + f + 1)^{100}}}$$ A plot shows that the sharp ratio is maximized very near zero and quickly converges to $$0$$

We could also check that variance of return $$E[X^2] -E[X]^2$$ grows pretty crazily . So a risk averse person may not bet any money at all .

I'm not sure that you wrote out the explanation of the question correctly (please correct me if I'm wrong), but if you bet S, then right after betting and before the coin is tossed your wealth is x-S.. now if the game is such that you either lose everything or gain 2S, then your wealth after one coin toss is either x-S or x-S+2S=x+S with prob. 1/2 each. In this case, no matter how much you bet your expected wealth will be x and since we are risk averse you probably don't want to bet anything.

• You didn't read the question carefully. You are getting 2:1 odds, so if you win your balance is $x+2S$, not $x+S$ Jan 21, 2015 at 19:38
• I did, I was just asking him if it is possible that he made a mistake because on one hand he says you win 2S on the other your new balance is x+2S (which means you win 3S).. Jan 21, 2015 at 22:20
• No. Your stake is not forfeited unless you lose. Until then it's still yours, so it's not counted as part of your winnings just because you retain it after you win. If you win $\ 2S\$, your both retain your stake of $\ S\$ and also win $\ 2S\$. Sep 13, 2019 at 12:14