0

I'm doing some prep work for a job interview and one of their difficult sample questions is as follows:

You flip a coin 100 times, but instead of having a fixed stake, you can freely choose the stake for each flip. You start with £100. After each flip, if it comes up heads you win twice your stake (and your stake is returned), if it comes up tails you lose your stake. So if you start with $x$ and select a stake of $S$, then after the flip you will either have $x+2S$ or $x-S$. You can never make your stake larger than your current balance.

If your profit is $P$ how should you select your stake, $S$, to maximise:

a) $E[P]$
b) $E[\log (P+100)]$

Edit: to clarify $0<S<100$ is required so you are betting an amount but you are also protecting yourself from losing all of your money (of course successive losses would whittle your total money to zero eventually)

user403033
  • 157
  • For a, see my answer here The bet is in your favor. Take it. All of it. – Ross Millikan Jan 23 '17 at 21:18
  • That's not correct because a single tail causes you to go bust. I'm after a mathematical based argument – user403033 Jan 24 '17 at 09:29
  • If you want the expectation, it is correct. Yes, you are very likely to go bust, but if you don't you have lots of money. The expectation is very high. If you aren't allowed to bet it all, you should bet as much as you can. What happens if you get down to $1$. Can you bet then? – Ross Millikan Jan 24 '17 at 14:47
  • you can still bet when you get down to 1, but you would have to bet everything by that point. You want S to be a percentage of your total so that you can maximise your gain whilst protecting against bankruptcy. i.e. S should be a reasonable value so that if you ran a simulation you would end in the money. – user403033 Jan 24 '17 at 16:54
  • That depends on your utility function. You are blindly assuming that betting everything is the wrong choice because you can go broke, but if you want the highest expectation value you should. In my other answer, I show the computation for the expectation value betting everything on every flip. Show me a better strategy. – Ross Millikan Jan 24 '17 at 17:03
  • https://en.wikipedia.org/wiki/Kelly_criterion

    That's basically what I was aiming to get without any prior knowledge of the Kelly Criterion. This protects from losing everything, whilst maximising the payout.

     – user403033 Jan 24 '17 at 17:08

2 Answers2

4

As I see it, the second question concerns maximising the logarithm of "100 plus the profit":

$$S^*=\underset{S\in(0,100),\, S\leq B}{\mathrm{argmax\:\;}}{\mathbb{E}(\log{(P+100)})} = \\\underset{S\in(0,100),\, S\leq B}{\mathrm{argmax\:\;}}{(\frac{1}{2}\log{(-S+100)+\frac{1}{2}\log{(2S+100)}})} $$ $$\begin{equation} = \begin{cases} 25 & \text{if } B > 25 \\ B & \text{otherwise} \end{cases} \end{equation}$$

where B is the current balance (or "bankroll"). So this means that we would not be betting $25\%$ of the current balance on each round as per the previous answer, but either betting $25 or going all in. However, if we were maximising the logarithm of "the current balance plus the profit" we would get the result that we should bet 25% of the current balance on each round:

$$S^{**}=\underset{S\in(0,100),\, S\leq B}{\mathrm{argmax\:\;}}{\mathbb{E}(\log{(P+B)})} = \\\underset{S\in(0,100),\, S\leq B}{\mathrm{argmax\:\;}}{(\frac{1}{2}\log{(-S+B)+\frac{1}{2}\log{(2S+B)}})} $$ $$\begin{equation} = \begin{cases} \frac{1}{4}B & \text{if } B < 400 \:\,(\iff \frac{1}{4}B <100\:)\\ 100 & \text{otherwise} \end{cases} \end{equation}$$ $$\begin{equation} \end{equation}$$

Martin Geller
  • 1,059
3

For the second, you are trying to maximize the expectation of the log of how much you have. For one flip, you start with $1$ and bet $x$. Your expectation is then $\frac 12(\log (1-x)+\log (1+2x))$ We take the derivative, set to zero, solve for $x$. That gives $\frac {-1}{1-x}+ \frac 2{1+2x}=0$ or $x=\frac 14$ so you should bet one quarter of your bankroll at each step. A win and a loss multiply your bankroll by $\frac 98$, so fifty wins and fifty losses will have you at about $36110$ at the end.

If you are required to bet at least $1$ every time there is no strategy in b that has positive expectation. You could lose every time, winding up with $0$ and the log is negative infinity. When you do questions like this it is essential to get the rules specified precisely.

Ross Millikan
  • 374,822
  • Should it not be $\log (100-S) + \log (100+2S)$? – user403033 Jan 24 '17 at 18:14
  • I was scaling to $1$ as your current bankroll. This ignores the granularity of betting, which was not specified, as well as an upper limit to what you can bet. – Ross Millikan Jan 24 '17 at 19:27
  • I don't see how the argument for 1 flip generalises to how one should bet in every of the 100 flips? In the expected log-term you have all S_i being the strategy decided at time t_i-1. Hence you are dealing with a multivariable optimisation problem (of a log-polynomial). I'm not convinced that you can repeat the same strategy in every step... – noob-mathematician May 26 '20 at 17:22
  • @noob-mathematician: there is no history here, so the amount you should bet just depends on how much you have. In this analysis I ignored the +100 in the log term. I don't remember why. The same approach works, but will not give a fixed fraction of the bankroll to bet. – Ross Millikan May 26 '20 at 19:21
  • "there is no history here, so the amount you should bet just depends on how much you have" - Thats not true: what you bet on the 5-th toss depends on your state right after the 4-th toss. Now your state at the 4-th toss depends on the position of the previous states and so on. That said, when you look at the gains at the 100-th toss (which is a-priori random), the latter depend on your predictable strategy at every single toss in the past. – noob-mathematician May 27 '20 at 09:00
  • No history means that you optimal action just depends on your bankroll at the moment, not how you got there. Yes, the past flips drive what your bankroll is now, but you can imagine you are just starting the game at this point. – Ross Millikan May 27 '20 at 13:57
  • @RossMillikan I am confused as well. So you showed that if the strategy is optimal for each time step, it should be optimal overall for the entire game. I tried to follow your thoughts: Let the random variable $P_i$ denote the $i-$th payoff where $P_i(x_i) = 1-x_i$ with probability 0.5 and $P_i(x_i) = (1 + 2x_i)$ with probability 0.5. Now let us consider two cointosses. We want to maximize $E[\log(P_1(x1)P_2(x2))] = E[\log(P_1(x_1))] + E[\log(P_2(x_2))]$. Thus maximizing the sum is equivalent to maximize each summand individually. – quallenjäger Sep 04 '20 at 22:55
  • @quallenjäger: you can't maximize each summand individually because they are correlated. One goes up when the other goes down. You are correct that maximizing the sum is what you want and we claim all the $x_i$ are the same. – Ross Millikan Sep 04 '20 at 23:55
  • @RossMillikan Why is that? The payoff $P_2$ solely depend on the second toss. Why do I have to care about what happened in the first toss. – quallenjäger Sep 05 '20 at 00:02