0

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

My goal is to find an optimal strategy $(s_1, s_2, s_3, ..., s_{100})$ to maximize an expected profit. It turns out that the optimal strategy is $S=x$.

I understand that the expected balance after a single coin flip is:

$$\frac{x-s}{2} + \frac{x+2s}{2} = \frac{2x+s}{2}$$

which is maximized when $s = x$. To me, this makes me think that $S = x$ is a locally optimal choice, but is this sufficient to conclude that I should always take $S = x$ for every flip or was it just coincidence (that locally optimal choice leads to globally optimal solution)? I think the good analogy is a greedy algorithm (e.g the greedy algorithm makes a locally optimal choice to find a global optimum - this doesn't work most of the time).

Ted
  • 365
  • It's not that it's locally optimal, but rather that every strategy has the same expected value of return. I personally would simply just take the $100, since the expected value is $100 anyways. – Rushabh Mehta Jan 13 '20 at 05:52
  • @DonThousand The expected value of betting all once is $\frac12\cdot 0+\frac12\cdot 300>100$ – Hagen von Eitzen Jan 13 '20 at 06:33
  • @HagenvonEitzen Oh it's $3$ times, not $2$. Then yes, the strategy is a unique global maximum. – Rushabh Mehta Jan 13 '20 at 07:04
  • If your bet each time is your whole bankroll then the probability of you not going bankrupt is $2^{-100}$ so that strategy is extremely high risk, even if the expected return is about $4 \times 10^{17}$ times your starting position. The Kelly criterion bet of $\frac{x}{4}$ would provide a balance between risk and return, I think with an expected return of about $130392$ times your starting position, a median return of about $361$ times your starting position and a probability of making a profit of about $0.9557$ – Henry Jan 13 '20 at 09:12

0 Answers0