Graph all the things

analyzing all the things you forgot to wonder about



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!


Numerical Solution

I first solved numerically, starting from an obvious lower bound on

and iteratively updating a lower bound by choosing the optimal based on . In particular, at iteration , update

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 :

A locally optimal strategy is globally optimal

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

outperforms , since it will give higher chance of winning at , and potentially at any other satisfying , etc. This proves that our condition is necessary for any optimal 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.

Exact Solution

I'll show that on the subset of points with a terminating sequence of binary digits , an optimal solution is
All I have to do is show that this is consistent with and that is locally optimal, implying global optimality.

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

This shows that our betting strategy is consistent with .

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:

  • If .
  • If .
  • If and .

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.