8 ms·

Kelly Can't Fail

393 points by jmount 2y ago

deleted 2y ago
[deleted]
dado3212 2y ago
Very cool writeup, would’ve benefited from some LaTeX formatting.
- TheRealNGenius 2y ago
  [dead]
- jmount 2y ago
  Thank you, and sorry. The Wordpress/Markdown path seems to be getting worse over time.
  - smcin 2y ago
    How is the Wordpress/Markdown path getting worse over time?
    - jmount 2y ago
      Mathjax used to be available more places. Jupyter used to respect spacing around h2 labels. Things like that.
Vecr 2y ago
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.
- jmount 2y ago
  I love that. Gaming the seed is always a possibility in demos.
hawkjo 2y ago
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?
- jmount 2y ago
  The book claims it is optimal for a set of strategies they called "sensible." I didn't think the argument flowed as well as the zero variance part of the proof, so I didn't work it in. I think the source also hinted at a game-theory proof as they called the sub-strategies in the portfolio "pure strategies."
- rahimnathwani 2y ago
  Do we know if the Kelly strategy is optimal here? What do you mean by optimal? Do you mean you're willing to risk going bankrupt, if it means a higher expected value?
  - scotty79 2y ago
    Surely there's some space between risking to go bankrupt and risking of getting less than 9.08 return guaranteed by Kelly strategy. If you are willing to take some risk in exchange for possibility of higher payout just bet a bit more then Kelly recommends. That's your "optimal" strategy for the amount of risk you are willing to take. I imagine it's expected return is the same as Kelly and calculating it's variance is left as the exercise for the reader.
    - rahimnathwani 2y ago
      I imagine it's expected return is the same as Kelly Given two options with the same expected return, most people would prefer the lower variance. Accepting higher variance with no increase in expected return has a name: gambling.
- barbegal 2y ago
  It is optimal for expected returns yes.
raydiak 2y ago
As a guy named Kelly, I appreciate the vote of confidence!
- pvg 2y ago
  I think you're underselling it a bit, it's a decree of confidence rather than a mere vote.
barbegal 2y ago
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)
- stevage 2y ago
  Agreed, I could follow the general argument but not enough to be convinced about why the result is exactly the same regardless of the order of cards.
- libraryofbabel 2y ago
  Yes. Although four cards has only one nontrivial branch, on turn 3. So, start out with the four cards example, and then show tree diagrams for the 5 and 6 cards cases (still manageable numbers) to build intuition for induction to the general case.
- deleted 2y ago
  [deleted]
siavosh 2y ago
Can anyone comment on the universal portfolio article linked in the conclusion? Asking for a friend.
- robbomacrae 2y ago
  It's a theory on how to optimally rebalance your investment portfolio every day. Original paper by Thomas Cover: https://isl.stanford.edu/~cover/papers/paper93.pdf https://isl.stanford.edu/~cover/papers/paper93.pdf A good breakdown with links to code examples by Andy Jones: https://andrewcharlesjones.github.io/journal/universal-portfolios.html https://andrewcharlesjones.github.io/journal/universal-portf...
malisper 2y ago
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.
- amluto 2y ago
  But the information gained in this game is independent of your bet. The multi-armed bandit problem is a famous example of the opposite situation.
- necovek 2y ago
  That seems to be exactly what this strategy is doing: at every step, you account for the probability of the red or black card coming up, and bet accordingly (both the sum and the colour).
tooblies 2y ago
It's really disappointing that the code examples aren't given in PyGyat.
pcthrowaway 2y ago
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
- jmount 2y ago
  Very good point. I did some experiments and the system is very sensitive to any sort of quantization or rounding of bets. You get the expected value about the right place, but the variance goes up quickly. So in addition to your important case, things are a bit dicey in general.
- boothby 2y ago
  If you start out with a $1e12 stake, you're able to avoid catastrophic rounding errors even in the worst case. There's probably a life lesson here.
  - fragmede 2y ago
    Is the lesson: choose to be born to wealthy parents?
    - darkerside 2y ago
      Or is it to choose appropriate betting amounts based on your capacity for risk
      - Onavo 2y ago
        IEEE-754 isn't precise enough for my capacity :( I too need rich parents.
      - laidoffamazon 2y ago
        I guess it then does follow that having rich parents does expand your capacity for risk!
ed-209 2y ago
why use a static seed on the random generator and could that be making this appear more interesting than it might otherwise?
- jfengel 2y ago
  The idea is sound. The static seed is presumably so the results are repeatable, but it works for true randomness. (Assuming you were permitted to do it this way, which you wouldn't be.)
fancy_pantser 2y ago
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 https://gwern.net/problem-14
- jmount 2y ago
  That is a nice game and writeup.
- snthpy 2y ago
  Nice! Only quibble i have is that black should be +$1 and red -$1 to follow standard finance conventions, i.e. be in the "black" or "red".
JohnMakin 2y ago
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
- amluto 2y ago
  > particularly poker players The Kelly criterion seems excellent for many forms of gambling, but poker seems like it could be an exception: in poker, you’re playing against other players, so the utility of a given distribution of chips seems like it ought to be more complicated than just the number of chips you have. (I’m not a poker player.)
  - deleted 2y ago
    [deleted]
  - tempestn 2y ago
    It's used for bankroll management (basically deciding what stakes to play) rather than for sizing bets within a particular game.
  - fernandopj 2y ago
    Chris "Jesus" Ferguson "proved" an application of this theory back in ~2009 [1]. He was a the time promoting Full Tilt and commited to turn $1 dollar bankroll to $10000 by applying a basic strategy of never using more than a low % of his bankroll into one tournament or cash game session. So, if one's skill would turn your session probability to +EV, by limiting your losses and using the fact that in poker the strongest hands or better tourney positions would give you a huge ROI, it would be just a matter of time and discipline to get to a good bankroll. Just remember that for the better part of this challenge he was averaging US$ 0.14/hour, and it took more than 9 months. [1] https://www.thehendonmob.com/poker_tips/starting_from_zero_by_chris_ferguson https://www.thehendonmob.com/poker_tips/starting_from_zero_b...
amluto 2y ago
> 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.
- kqr 2y ago
  He's contributed a lot of interesting papers in this area too -- some of them make up a significant chunk of the book on the Kelly criterion!
moonlion_eth 2y ago
I was like "oooh fun a card game" then was like "oh shit I'm too dumb for this math"
- IAmGraydon 2y ago
  You aren't dumb. You just don't have enough exposure to the prerequisites.
  - necovek 2y ago
    It could also be both: though it's not necessarily that they are "dumb", but that the language of mathematics is something they can't get their head around, even if they can understand the concepts when described in spoken language. Eg. it's probably pretty easy to convince them that with 15 cards in a deck, out of which 5 are red and 10 are black, chances are bigger (and in particular 10/15 or ~67%) that they'll pull out a black card, and that you should bet more on this happening. If you happen to miss, you should only bet even more on black since the chances grow further — to be able to maintain this strategy, you only need to never bet too much so you have enough "funds" to bet all the way through (eg. in the worst case where the least likely thing happens: in my example, that would be 5 red cards coming up first). Putting all this reasoning into formulae is what math is, and I do believe some struggle with abstracting these more than others (which is why the divide does exist and why many people believe those good at math are "smart", which is very much not so — seen plenty of "stupid" mathematicians, even professors). Does not make them "dumb", but might make them "modern math dumb". A signal that someone can be good at math today is that they are unfazed with more-than-3-dimensional spaces (you need to stop tying things to physical world).
lupire 2y ago
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) and these equalities can also be directly verified algebraically 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.
lupire 2y ago
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.
andrewprock 2y ago
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.
- zahlman 2y ago
  > In practice, you won't have a continuous range of bet sizes you can make. You may also be required to pay for the privilege of placing a bet (spread and commissions in trading; the rake at a casino table).
ilya_m 2y ago
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
- lupire 2y ago
  Why isn't your inductive proof an unnecessary detour?
lordnacho 2y ago
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. https://en.wikipedia.org/wiki/Proebsting%27s_paradox https://en.wikipedia.org/wiki/Proebsting%27s_paradox
- dominicrose 2y ago
  Quoting the same page: One easy way to dismiss the paradox is to note that Kelly assumes that probabilities do not change. That's good to know. Kelly is good if you know the probabilities AND they don't change. If you don't know or if they can change, I expect the right approach has to be more complex than the Kelly one.
  - cubefox 2y ago
    In particular, then the right approach has to be more risk averse than Kelly would recommend. In reality, most probabilities can only be estimated, while the objective probabilities (e.g. the actual long run success rate) may well be different and lead to ruin. That's also what makes the title "Kelly can't fail" more wrong than right in my opinion.
    - LegionMammal978 2y ago
      For the issue in Proebsting's paradox, one simple approach I've found successful is to gradually accumulate your full bet as the betting lines progress to their ultimate positions. This works even in illiquid markets where your bets affect the lines, since it gives the other participants less room to suddenly react to what you're doing. (Though you always have the slight worry of a huge last-second bet that you can't react to, eBay-auction style.) As for the actual probability being different from the expected probability, that's not too difficult to account for. Just set up a distribution (more or less generous depending on your risk tolerance) for where you believe the actual probability may lie, and work out the integrals as necessary, recalling that you want to maximize expected log-value. It's not the trivial Kelly formula, but it's exactly the same principle in the end.
PaulHoule 2y ago
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 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.
- jdhwosnhw 2y ago
  That reminds me of my favorite algorithm, which can find the majority element in a list with any number of distinct entries while using O(N) time and O(1) space (provided a majority element exists). I sometimes pose deriving this algorithm as a puzzle for people, no one has ever solved it (nor could I). https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
  - barapa 2y ago
    That is really cool
  - lupire 2y ago
    What's great about that is that the assumption (or O(n) check) that the majority exists is incredibly powerful, enabling the algorithm, which is nearly the dumbest possible algorithm, to work. The one flaw in the magic is that "2nd pass to verify" is a significant cost, transforming the algorithm from online streaming O(1) space to O(n) collection-storage space.
im3w1l 2y ago
This article uses stake to mean bankroll, but usually it denotes bet size.
bell-cot 2y ago
Interesting as a mathematical puzzle - but note that it's difficult to find cooperative, solvent counter-parties for "I can't lose" betting games.
bilater 2y ago
I created a simple tool to play with the optimal bet size on v0. Interesting. https://v0.dev/chat/1u6efMupysC?b=b_sxkDz7R6crr&p=0 https://v0.dev/chat/1u6efMupysC?b=b_sxkDz7R6crr&p=0
gcanyon 2y ago
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?

Kelly Can't Fail

393 points by jmount 2y ago

deleted 2y ago

[deleted]

dado3212 2y ago

Very cool writeup, would’ve benefited from some LaTeX formatting.

TheRealNGenius 2y ago
[dead]
jmount 2y ago
Thank you, and sorry. The Wordpress/Markdown path seems to be getting worse over time.
- smcin 2y ago
  How is the Wordpress/Markdown path getting worse over time?
  - jmount 2y ago
    Mathjax used to be available more places. Jupyter used to respect spacing around h2 labels. Things like that.

Vecr 2y ago

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.

jmount 2y ago
I love that. Gaming the seed is always a possibility in demos.

hawkjo 2y ago

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?

jmount 2y ago
The book claims it is optimal for a set of strategies they called "sensible." I didn't think the argument flowed as well as the zero variance part of the proof, so I didn't work it in. I think the source also hinted at a game-theory proof as they called the sub-strategies in the portfolio "pure strategies."
rahimnathwani 2y ago
Do we know if the Kelly strategy is optimal here? What do you mean by optimal? Do you mean you're willing to risk going bankrupt, if it means a higher expected value?
- scotty79 2y ago
  Surely there's some space between risking to go bankrupt and risking of getting less than 9.08 return guaranteed by Kelly strategy. If you are willing to take some risk in exchange for possibility of higher payout just bet a bit more then Kelly recommends. That's your "optimal" strategy for the amount of risk you are willing to take. I imagine it's expected return is the same as Kelly and calculating it's variance is left as the exercise for the reader.
  - rahimnathwani 2y ago
    I imagine it's expected return is the same as Kelly Given two options with the same expected return, most people would prefer the lower variance. Accepting higher variance with no increase in expected return has a name: gambling.
barbegal 2y ago
It is optimal for expected returns yes.

raydiak 2y ago

As a guy named Kelly, I appreciate the vote of confidence!

pvg 2y ago
I think you're underselling it a bit, it's a decree of confidence rather than a mere vote.

barbegal 2y ago

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)

stevage 2y ago
Agreed, I could follow the general argument but not enough to be convinced about why the result is exactly the same regardless of the order of cards.
libraryofbabel 2y ago
Yes. Although four cards has only one nontrivial branch, on turn 3. So, start out with the four cards example, and then show tree diagrams for the 5 and 6 cards cases (still manageable numbers) to build intuition for induction to the general case.
deleted 2y ago
[deleted]

siavosh 2y ago

Can anyone comment on the universal portfolio article linked in the conclusion? Asking for a friend.

robbomacrae 2y ago
It's a theory on how to optimally rebalance your investment portfolio every day. Original paper by Thomas Cover: https://isl.stanford.edu/~cover/papers/paper93.pdf https://isl.stanford.edu/~cover/papers/paper93.pdf A good breakdown with links to code examples by Andy Jones: https://andrewcharlesjones.github.io/journal/universal-portfolios.html https://andrewcharlesjones.github.io/journal/universal-portf...

malisper 2y ago

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.

amluto 2y ago
But the information gained in this game is independent of your bet. The multi-armed bandit problem is a famous example of the opposite situation.
necovek 2y ago
That seems to be exactly what this strategy is doing: at every step, you account for the probability of the red or black card coming up, and bet accordingly (both the sum and the colour).

tooblies 2y ago

It's really disappointing that the code examples aren't given in PyGyat.

pcthrowaway 2y ago

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

jmount 2y ago
Very good point. I did some experiments and the system is very sensitive to any sort of quantization or rounding of bets. You get the expected value about the right place, but the variance goes up quickly. So in addition to your important case, things are a bit dicey in general.
boothby 2y ago
If you start out with a $1e12 stake, you're able to avoid catastrophic rounding errors even in the worst case. There's probably a life lesson here.
- fragmede 2y ago
  Is the lesson: choose to be born to wealthy parents?
  - darkerside 2y ago
    Or is it to choose appropriate betting amounts based on your capacity for risk
    - Onavo 2y ago
      IEEE-754 isn't precise enough for my capacity :( I too need rich parents.
    - laidoffamazon 2y ago
      I guess it then does follow that having rich parents does expand your capacity for risk!

ed-209 2y ago

why use a static seed on the random generator and could that be making this appear more interesting than it might otherwise?

jfengel 2y ago
The idea is sound. The static seed is presumably so the results are repeatable, but it works for true randomness. (Assuming you were permitted to do it this way, which you wouldn't be.)

fancy_pantser 2y ago

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 https://gwern.net/problem-14

jmount 2y ago
That is a nice game and writeup.
snthpy 2y ago
Nice! Only quibble i have is that black should be +$1 and red -$1 to follow standard finance conventions, i.e. be in the "black" or "red".

JohnMakin 2y ago

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

amluto 2y ago
> particularly poker players The Kelly criterion seems excellent for many forms of gambling, but poker seems like it could be an exception: in poker, you’re playing against other players, so the utility of a given distribution of chips seems like it ought to be more complicated than just the number of chips you have. (I’m not a poker player.)
- deleted 2y ago
  [deleted]
- tempestn 2y ago
  It's used for bankroll management (basically deciding what stakes to play) rather than for sizing bets within a particular game.
- fernandopj 2y ago
  Chris "Jesus" Ferguson "proved" an application of this theory back in ~2009 [1]. He was a the time promoting Full Tilt and commited to turn $1 dollar bankroll to $10000 by applying a basic strategy of never using more than a low % of his bankroll into one tournament or cash game session. So, if one's skill would turn your session probability to +EV, by limiting your losses and using the fact that in poker the strongest hands or better tourney positions would give you a huge ROI, it would be just a matter of time and discipline to get to a good bankroll. Just remember that for the better part of this challenge he was averaging US$ 0.14/hour, and it took more than 9 months. [1] https://www.thehendonmob.com/poker_tips/starting_from_zero_by_chris_ferguson https://www.thehendonmob.com/poker_tips/starting_from_zero_b...

amluto 2y ago

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

kqr 2y ago
He's contributed a lot of interesting papers in this area too -- some of them make up a significant chunk of the book on the Kelly criterion!

moonlion_eth 2y ago

I was like "oooh fun a card game" then was like "oh shit I'm too dumb for this math"

IAmGraydon 2y ago
You aren't dumb. You just don't have enough exposure to the prerequisites.
- necovek 2y ago
  It could also be both: though it's not necessarily that they are "dumb", but that the language of mathematics is something they can't get their head around, even if they can understand the concepts when described in spoken language. Eg. it's probably pretty easy to convince them that with 15 cards in a deck, out of which 5 are red and 10 are black, chances are bigger (and in particular 10/15 or ~67%) that they'll pull out a black card, and that you should bet more on this happening. If you happen to miss, you should only bet even more on black since the chances grow further — to be able to maintain this strategy, you only need to never bet too much so you have enough "funds" to bet all the way through (eg. in the worst case where the least likely thing happens: in my example, that would be 5 red cards coming up first). Putting all this reasoning into formulae is what math is, and I do believe some struggle with abstracting these more than others (which is why the divide does exist and why many people believe those good at math are "smart", which is very much not so — seen plenty of "stupid" mathematicians, even professors). Does not make them "dumb", but might make them "modern math dumb". A signal that someone can be good at math today is that they are unfazed with more-than-3-dimensional spaces (you need to stop tying things to physical world).

lupire 2y ago

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) and these equalities can also be directly verified algebraically 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.

lupire 2y ago

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.

andrewprock 2y ago

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.

zahlman 2y ago
> In practice, you won't have a continuous range of bet sizes you can make. You may also be required to pay for the privilege of placing a bet (spread and commissions in trading; the rake at a casino table).

ilya_m 2y ago

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

lupire 2y ago
Why isn't your inductive proof an unnecessary detour?

lordnacho 2y ago

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. https://en.wikipedia.org/wiki/Proebsting%27s_paradox https://en.wikipedia.org/wiki/Proebsting%27s_paradox

dominicrose 2y ago
Quoting the same page: One easy way to dismiss the paradox is to note that Kelly assumes that probabilities do not change. That's good to know. Kelly is good if you know the probabilities AND they don't change. If you don't know or if they can change, I expect the right approach has to be more complex than the Kelly one.
- cubefox 2y ago
  In particular, then the right approach has to be more risk averse than Kelly would recommend. In reality, most probabilities can only be estimated, while the objective probabilities (e.g. the actual long run success rate) may well be different and lead to ruin. That's also what makes the title "Kelly can't fail" more wrong than right in my opinion.
  - LegionMammal978 2y ago
    For the issue in Proebsting's paradox, one simple approach I've found successful is to gradually accumulate your full bet as the betting lines progress to their ultimate positions. This works even in illiquid markets where your bets affect the lines, since it gives the other participants less room to suddenly react to what you're doing. (Though you always have the slight worry of a huge last-second bet that you can't react to, eBay-auction style.) As for the actual probability being different from the expected probability, that's not too difficult to account for. Just set up a distribution (more or less generous depending on your risk tolerance) for where you believe the actual probability may lie, and work out the integrals as necessary, recalling that you want to maximize expected log-value. It's not the trivial Kelly formula, but it's exactly the same principle in the end.

PaulHoule 2y ago

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

jdhwosnhw 2y ago
That reminds me of my favorite algorithm, which can find the majority element in a list with any number of distinct entries while using O(N) time and O(1) space (provided a majority element exists). I sometimes pose deriving this algorithm as a puzzle for people, no one has ever solved it (nor could I). https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm https://en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority...
- barapa 2y ago
  That is really cool
- lupire 2y ago
  What's great about that is that the assumption (or O(n) check) that the majority exists is incredibly powerful, enabling the algorithm, which is nearly the dumbest possible algorithm, to work. The one flaw in the magic is that "2nd pass to verify" is a significant cost, transforming the algorithm from online streaming O(1) space to O(n) collection-storage space.

im3w1l 2y ago

This article uses stake to mean bankroll, but usually it denotes bet size.

bell-cot 2y ago

Interesting as a mathematical puzzle - but note that it's difficult to find cooperative, solvent counter-parties for "I can't lose" betting games.

bilater 2y ago

I created a simple tool to play with the optimal bet size on v0. Interesting. https://v0.dev/chat/1u6efMupysC?b=b_sxkDz7R6crr&p=0 https://v0.dev/chat/1u6efMupysC?b=b_sxkDz7R6crr&p=0

gcanyon 2y ago

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?