Graph all the things
analyzing all the things you forgot to wonder about
2018-09-09
interests: game theory, interactive visualizations
A coworker posed this problem:
Suppose you're at a casino with $100, and need $200 to get home. The casino only supports one style of betting: you can put any amount of money on the table, and with 30% chance they double it, otherwise taking it away. What should your strategy be to maximize your chance of getting home?
Starting from $100, you'd think that you should just take the obvious 30% chance to double your money. And you'd be right. But why? I wasn't able to come up with any simple proof other than solving the general case, which I found surprisingly interesting.
To study this, let's rephrase the problem so that you have money,
, and want to reach 1 money.
Each bet has chance
of doubling your money.
Denote by
the amount of money your strategy bets when you have
money, and suppose that following this strategy gives you a
chance of winning when you have
money.
Here's an interactive graph of your probability of winning, playing by the optimal strategy.
Click on the graph to zoom in!
I first solved numerically, starting from an obvious lower bound on
One can prove inductively that .
I was expecting something boring - that you should always just bet as much as you can until you hit , then bet as much as you need to reach 1 money - but I was wrong.
Instead, it converged to these interesting fractal
and
:
I'll prove that the following local optimality condition is necessary and sufficient for the optimal strategy to this problem:
A strategy with and
is a globally optimal strategy (no strategy with
has
for any
) if and only if there exist no
and
such betting
with
money and otherwise following the strategy gives a higher chance of winning than betting
.
To prove it is necessary, suppose that there were an and
such that betting
with
gave a higher chance of winning than betting
.
Then clearly the strategy
To prove that it is sufficient, suppose for the sake of contradiction there were another strategy with corresponding
such that
for some
.
Let
denote the composite strategy that follows
where
and
otherwise.
This composite strategy satisfies
at every
, and
.
Now consider the set of all
such that
, and suppose for the sake of contradiction they all satisfy
.
Decreasing our chance of winning at such an
could only decrease it elsewhere too, so if we choose any subset of these points
to play by
instead of
, we must still get a strategy no better than
.
But this violates our assumption that
, so we must have that there exists some
and bet
that gives a chance of winning
.
This contradicts local optimality, implying that any locally optimal solution must also be a globally optimal one.
To prove that is consistent with
, choose
such that the last
digits
of
are
's, and
is a 0.
Then betting
will give us an
chance of having
money if we win and a
chance of having
money if we lose.
Our probability
is then consistent with our bet
if
.
Plugging in this
and
, and letting
and
, we get
To prove that the strategy is locally optimal, I'll consider any strategy played on amounts of money that terminate in binary, and show that a bet can only be worse than , given
.
Consider any bet
at
, and let
and
(where the
st digit is the first one that differs;
and
).
I'll skip the details, but one can prove that in any of the following cases, the bet is no better than
, which results in the first
digits of the outcomes agreeing:
Additionally, the outcomes and
are at least as good as
and
on average.
Applying all these rules implies that no bet is better than
, where the amount of money
has
binary digits after the decimal point.
Using the previous result that a locally optimal strategy is globally optimal, this strategy is globally optimal.