21
$\begingroup$

A number $p$ is drawn uniformly at random from $[0, 1]$. You are then given a biased coin that turns up heads with probability $p$, but the number $p$ is not known to you.

You start with a total wealth of $1$ dollar. On each round, you may bet any amount $x$ from $0$ to your total wealth. The coin is flipped, and if it comes up heads you win $x$ dollars, otherwise you lose $x$ dollars.

Given that there are $N \geq 2$ rounds in the game, what is the optimal strategy for the game? Here an optimal strategy will mean one that maximises the expected winnings, noting that the expectation is also taken over the initial uniform draw.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Just to confirm, you really do want to maximize expected winnings, and are not looking for an analogue of the Kelly criterion? $\endgroup$
    – Timothy Chow
    Commented Feb 19 at 16:08
  • $\begingroup$ @TimothyChow Indeed, I think it will be easier to analyse if we just ask to maximize the expected winnings. $\endgroup$
    – Nate River
    Commented Feb 19 at 16:11
  • 1
    $\begingroup$ @Command Master Any real amount. $\endgroup$
    – Nate River
    Commented Feb 19 at 16:56
  • 2
    $\begingroup$ @TimothyChow The Kelly criterion version is actually relatively simple to analyze. Let $\epsilon_i$ be $+1$ if the $i$th flip is heads and $-1$ if the $i$th flip is tails, and let $b_i$ be the fraction of our money we bet on the $i$th flip. Then the amount of money we have at the end is $\prod_{i=1}^N (1+ \epsilon_i b_i)$ so the logarithm is $\sum_{i=1} \log (1+\epsilon_i b_i)$. Since that splits as a sum over flips, its expectation splits as a sum over flips, and we can analyze each flip independently. $\endgroup$
    – Will Sawin
    Commented Feb 24 at 14:48
  • 2
    $\begingroup$ The usual Kelly argument shows that if the current flip has probability $q$ of being heads, we should bet $0$ if $q\leq 1/2$ and bet a proportion $2q-1$ if $q\geq 1/2$. Here $q$ is $\frac{H+1}{H+T+2}$ where $H$ is the number of heads so far and $T$ is the number of tails, so the fraction we bet is $\frac{ H-T}{H+T+2}$. $\endgroup$
    – Will Sawin
    Commented Feb 24 at 14:50

2 Answers 2

Reset to default
10
$\begingroup$

The strategy suggested in Geoffry Irving's answer of betting the maximum amount each time is correct, but the argument given is incomplete. The expected final amount, conditional on the outcomes of the first $n$ coin flips, is a linear function of the amount we have after the $n$th coin flip, but this linear function is not independent of the result of the $n$th coin flip, so it's not clear that it's correct to bet if the $n$th coin flip has a probability $>1/2$ of coming up heads and incorrect if the $n$th coin flip has a probability $<1/2$ of coming up heads.

In fact, this logic suggests we should be indifferent to whether we bet or not on the first coin flip, but this is not correct: Say $N=2$, the strategy of betting the maximum amount each time gives an expected return of $\\\$4/3$ while the strategy of not betting on the first coin flip, and then betting the maximum amount if the first coin flip comes up heads, gives an expected return of only $\\\$7/6$.

Betting the maximum amount each time is the unique optimal strategy for the following reason: There are $2^N$ possible sequences of heads and tails. If the coin were fair, each of those outcomes would occur with probability $2^{-N}$ and betting would be a martingale so the sum over all sequences of the money left in each sequence would be $2^N$. Thus, the maximum expectation achieved is $2^N$ times the probability of the most probable outcome, and this is achieved if and only if the strategy leaves us with $\\\$0$ on every outcome except the most probable.

A sequences of $k$ heads and $N-k$ tails has a probability $\frac{1}{ (N+1) \binom{N}{k}}$ which is maximized if and only if $k=0$ or $k=N$. The strategy of always bet everything gives $\\\$0$ except if $k=N$, so it indeed achieves the maximum, and no other strategy achieves the maximum since we must lose on every sequence with exactly one tail, and thus must bet the maximum after every number of heads.

An interesting question is, if you start playing the game after seeing the coin produce a certain number of heads and a certain number of tails, when you should bet. It may be optimal in some cases to bet with a probability of heads slightly less than $1/2$. Certainly this is true if we allow a non-integer number of heads so far (more sensibly, if we draw $p$ from a beta distribution instead of a uniform distribution): If one varies the parameters slightly from the starting value, the optimal strategy stays the same.

Improve this answer
$\endgroup$
9
  • $\begingroup$ @ChristianRemling Well, if the expectation is positive but just barely greater than zero, it may be better to wait, as the expectation grows or shrinks, and only do it when it's just barely greater than zero. $\endgroup$
    – Will Sawin
    Commented Feb 20 at 3:18
  • $\begingroup$ How could betting the maximum amount each time be correct. Doesn't that mean your first loss must wipe you out? $\endgroup$
    – Robbie Goodwin
    Commented Feb 21 at 22:50
  • $\begingroup$ @RobbieGoodwin If a pot of money is your only source of food then it's very rarely wise to bet it all, as getting wiped out is catastrophic but if the goal is to maximize the expected value, it's often correct, as long as the reward earned by betting is greater than the loss of getting wiped out, which in this case it is. $\endgroup$
    – Will Sawin
    Commented Feb 22 at 1:13
  • $\begingroup$ @WillSawin Thanks and how will your firsts loss not wipe you out? $\endgroup$
    – Robbie Goodwin
    Commented Feb 22 at 21:26
  • 2
    $\begingroup$ @RobbieGoodwin Your concern with getting wiped out is why I suggested that the Kelly criterion might be a more natural notion of optimality to consider. $\endgroup$
    – Timothy Chow
    Commented Feb 24 at 12:44
8
$\begingroup$

It is optimal to always bet the full amount iff heads has come up most of the time, and zero otherwise (breaking ties arbitrarily).

To see this, first note that any strategy can be scaled linearly, so our expected final amount is a linear function of the amount we have at any step. And then, if the bet this round has nonnegative EV, we may as well bet everything. Finally, the bet has nonnegative EV if heads is the most common, and nonpositive EV if tails is most common.

Edit: Following Christian’s comments below, the above strategy can be simplified to “always bet everything”. The above proof works in more generality, if one starts at any intermediate state with any amount. But as written in the question, with the above strategy once there is any tails we can assume to have lost everything.

The Kelly version might be more interesting to analyze.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ It's simple but very neat actually: the reason this strategy works is that going broke stops you from losing more than $\$ 1$ when up against an unfavorable coin while you do milk the favorable ones to the max. $\endgroup$
    – Christian Remling
    Commented Feb 19 at 18:13
  • $\begingroup$ "any strategy can be scaled linearly" -- what does this mean? It can't be a comment about your betting size, because a priori you can hypothesize a strategy that bets any nonlinear function. $\endgroup$
    – Chris Gerig
    Commented Feb 19 at 19:39
  • 1
    $\begingroup$ For example if $N=2$ then always bet the max scores $4/3$ whereas betting only if heads have the lead scores $7/6$, which is worse. $\endgroup$
    – Will Sawin
    Commented Feb 19 at 21:25
  • 1
    $\begingroup$ @ChristianRemling The issue is that if you bet nothing you have \$1 in the worlds where the first coin comes up heads and \$1 in the worlds where the first coin comes up tails. But you would much rather have \$1 in the worlds where the first coin comes up heads, where it has an expected value of \$4/3, than in the worlds where the first coin comes up tails, where it has an expected value of \$1. $\endgroup$
    – Will Sawin
    Commented Feb 19 at 21:27
  • 3
    $\begingroup$ For the record, I agree with Will that this proof is not correct. And the reason is roughly that one should consider betting even when this round's EV is negative, if the EV of the next round conditioned on a heads this round is positive. For example, if $p$ were uniformly either $0$ or $0.9$, this answer would say to wait to bet until you see a head, but betting immediately is much better, because in the world where $p=0.9$, you usually have a 2x or 4x head start on an approaching-infinitely-large EV, which is worth giving up an additive $1$ in the world where $p=0$. $\endgroup$
    – usul
    Commented Feb 20 at 4:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .