Kelly Can't Fail
Beautiful, thanks for sharing it!
I think the portfolio argument is an unnecessary detour though. There's a two-line proof by induction.
1. The payoff in the base case of (0,1) or (1,0) is 2.
2. If we are at (r,b), r >=b , have $X, and stake (r-b)/(r+b) on red, the payoff if we draw red and win is X * (1+(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r-1) = X * 2^(r+b) * r / ((r+b) * (r+b-1 choose r-1)) = X * 2^(r+b) / (r+b choose r).
Similarly, if we draw black and lose, the payoff is X * (1-(r-b)/(r+b)) * 2^(r+b-1) / (r+b-1 choose r) = X * 2^(r+b) * b / ((r+b) * (r+b-1 choose r)) = X * 2^(r+b) / (r+b choose r). QED
Interesting side note on Kelly:
In probability theory, Proebsting's paradox is an argument that appears to show that the Kelly criterion can lead to ruin. Although it can be resolved mathematically, it raises some interesting issues about the practical application of Kelly, especially in investing. It was named and first discussed by Edward O. Thorp in 2008.[1] The paradox was named for Todd Proebsting, its creator.
A very similar card game played by deciding when to stop flipping cards from a deck where red is $1 and black is −$1 as described in Timothy Falcon’s quantitative-finance interview book (problem #14). Gwern describes it and also writes code to prove out an optimal stopping strategy: https://gwern.net/problem-14
Kelly criterion is one of my favorite game theory concepts that is used heavily in bankroll management of professional gamblers, particularly poker players. It is a good way to help someone understand how you can manage your finances and stakes in a way that allows you to climb steadily forward without risking too much or any ruin, but is frequently misapplied in that space. The problem is kelly deals with binary results, and often situations in which this is applied where the results are not binary (a criteria for applying this) you can see skewed results that look almost right but not quite so, depending on how you view the math
When I was a teen I discovered that I could always guess more than half the cards right using card counting to determine what color is more common in the deck. I programmed my
https://en.wikipedia.org/wiki/TRS-80_Model_100
to simulate it and it never failed. Recently I thought about it again and wrote a Python script that tried it 30 million times and... it never failed.
I've been thinking about what to do with it and came up with the options of (i) a prop bet and (ii) a magic trick, neither of which seemed that promising.
As a prop bet I can offer $1000 to somebody's $10 which is not the route to great prop bet profits, also I worry that if I make a mistake or get cheated somehow I could be out a lot of money. (Now that I think of it maybe it is better if I re-organize it as a parlay bet)
As a magic trick it is just too slow paced. I developed a patter to the effect that "Parapsychologists were never able to reliably demonstrate precognition with their fancy Zener cards, but I just developed a protocol where you can prove it every time!" but came to the conclusion that it was not entertaining enough. It takes a while to go through a deck which doesn't seem like a miracle, you will have to do it 7 times in a row to exclude the null hypothesis at p=0.01. Maybe somebody with more showmanship could do it but I gave up.
It would have been a better demo if reduced to more manageable numbers e.g. a deck of 2 black and 2 red cards.
Turn 1 r = b so no bet
Turn 2 bet 1/3 on whichever card wasn't revealed in turn 1.
Turn 3 either you were wrong on turn 2 and you now have 2/3 of your stake but you know the colour of the next two cards so you can double your stake each time to end up with 4/3 after turn 3 or you were right and you have 4/3 of your stake but have one of each red or black left so you don't bet this turn.
Turn 4 you know the colour of the final card so you double your money to 8/3 of your original stake.
And then the exercise to the reader is to prove optimality (which is fairly straightforward but I don't believe there is a short proof)
Very cool to see no variance in the outcome. But that also makes it feel like there should be a strategy with better expected return due to the unique problem structure. Do we know if the Kelly strategy is optimal here?
> The problem and solution appear to come from Thomas Cover.
I don’t recall this specific example, but I learned about the Kelly criterion in a class that Thomas Cover taught. He was one of my favorite teachers, and any discussion with him was guaranteed to be interesting and worthwhile. RIP.
As a guy named Kelly, I appreciate the vote of confidence!
I guess it's kind of intuitive that if you are playing an exhaustive game (all 52 cards) that the optimal solution would not only be optimal but deterministically so. But I wonder if that idea just feels good and isn't true. Is it false? Anyone have a counter-example?
I created a simple tool to play with the optimal bet size on v0. Interesting.
Checks out with multiple RNG seeds.
It shouldn't be a problem because the RNG is advanced each run. Might save someone a check though.
I need to do some Math, but I wonder if there's a better strategy than Kelly betting. An assumption made for Kelly betting is the bets are independent of each other. That's not the case in the problem given.
After making a bet, you gain information about the contents of the rest of the deck of cards. I could see it being possible to do better by pricing in that information into your bet.
Can anyone comment on the universal portfolio article linked in the conclusion? Asking for a friend.
Very cool writeup, would’ve benefited from some LaTeX formatting.
This article uses stake to mean bankroll, but usually it denotes bet size.
In practice, there are a number of factors which make using Kelly more difficult than in toy examples.
What is your bankroll? Cash on hand? Total net worth? Liquid net work? Future earned income?
Depending on the size of your bankroll, a number of factors come in to play. For example, if your bankroll is $100 and you lose it all it's typically not a big deal. If you have a $1 million bankroll, then you are likely more adverse to risking it.
What is the expected value? Is it known? Is it stationary? Is the game honest?
Depending on the statistical profile of your expected value, you are going to have to make significant adjustments to how you approach bet sizing. In domains where you can only estimate your EV, and which are rife with cheats (e.g. poker), you need to size your wagers under significant uncertainty.
What bet sizes are available?
In practice, you won't have a continuous range of bet sizes you can make. You will typically have discrete bet sizes within a fixed range, say $5-$500 in increments of $5 or $25. If your bankroll falls to low you will be shut out of the game. If your bankroll gets too high, you will no longer be able to maximize your returns.
At the end of the day, professional gamblers are often wagering at half-kelly, or even at quarter-kelly, due in large part to all these complexities and others.
Corollaries, by considering different deck shufflings, such as perfectly interleaved as perfectly separated:
9.08 ~
52/52 × 52/51 × 50/50 ÷ 50/49 × ... 2/2 × 2/1
= 52/51 × 50/49 × ... × 2/1
= 2^52 × 26!² / 52!
= (52/52 × 50/51 × ... × 2/27) × (52/26 × 50/25 × ... × 2/1)
This also points to a non-"many worlds"/portfolio version of the prod of zero-variance.
Every bet is e/d, where e is current edge and d is current deck size. So every outcome multiplies the stack by (d + e × (-1)^i)/d, where is ±1, depending on win or lose.
Note that the product of all the values of d is constant, so we can ignore the denominator.
Since we know (from the OP proof) that the product of these numbers is constant for all shuffles of the deck, we can split a shuffled deck anywhere such that both parts are balanced red=blue, and the total (multiplicative) return over each part of the deck is constant across all shuffling of that part of the deck. (There are at least two ways to prove this part!)
This is gives a further hint toward another fascinating fact: over any span of the deck between points where the deck is balanced, the numerators of the bet results double-cover all the even numbers between the starting and ending deck size.
To see why:
* A loss after a loss has a numerator (deck minus edge) of 2 less than the previous bet, as the deck size decreased by 1 and the edge has inccreased by 1.
* A win after a win also has a numerator (deck plus edge) of 2 less than the previous bet, as the deck size decreased by 1 and the edge has decreased by 1.
* A win after a loss, causes a big swing in the numerator, exactly back to the largest not yet double-covered numerator that started the streak that just ended. Then the new win streak continues making the second cover of even numerators, until... a loss after a win jumps the numerator back to continuing the sequence of decreasing even numberators, which will get their second cover later when the later wins come.
Since the deck is balanced, the number of wins always equals the number of losses, as long as we consider the 0 wager on a balanced subdeck to be a loss, since it increases the edge like non-degenerate losses do.
(When the deck is balanced, edge is 0, so the return of no-bet is same as a win is same as a loss)
You can visualize the numerator changes like so: a crane is driving from 52 to 0. Its arm is pointing either forward or backward, and there is a counterweight of the same length pointing in the opposite direction. At each step, the crane arm is either pointing toward 0 and stretches another step toward 0, or points backward to 52 and shrinks (toward 0 milestone and toward 0 arm length), or it swings to the other direction. Whenever the crane stretches toward 0, the counterweight stretches backward, its end not moving relative to the ground.
Because the deck is balanced at start and empty deck is balanced, the crane starts and ends with a 0-stretch arm. The front side is either the frame arm stepping 2 steps forward at a time relative to the ground, or holding still while the backside crane arm shrinks closer, and the crane arm occasionally flips back and forth pointing forward or ackward. And vice versa for the counterweight.
Over the course of the drive, the crane arm end reaches every even milestone once pointing forward and once again pointing backward.
why use a static seed on the random generator and could that be making this appear more interesting than it might otherwise?
Intuition for the bet size:
When the deck has d cards left, it is sensible to make d bets of 1/d your stack, where each bet is that one specific card is next. If there are r reds and b=r+e blues, r of these bets simply cancel out r other bets, leaving e (times 1/d) remaining to be a nontrivial bet.
Interesting as a mathematical puzzle - but note that it's difficult to find cooperative, solvent counter-parties for "I can't lose" betting games.
I was like "oooh fun a card game" then was like "oh shit I'm too dumb for this math"
It's really disappointing that the code examples aren't given in PyGyat.
Note that you need to be able to infinitely divide your stake for this to work out for you all the time.
For example, if the deck has 26 red cards on top, you'd end up dwindling your initial $1.00 stake to 0.000000134 before riding it back up to 9.08