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!
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.