introduce
you may have heard Kelly bet allocation strategy. It is a system for correctly utilizing information or bias in gambling situations. It is also known as the maximum aggressive or high variance strategy because betting more than the Kelly pick can cause considerable damage.
I recently came across a strange card game in which the Kelly strategy is risk-free zero variance. Peter Winkler, in his excellent book, calls this game “Next Card Betting” math puzzle. The problem and solution seem to come from Thomas Cover. I find this betting game and its analysis amazing and wanted to share it with you here.
game
The gameplay is as follows. The standard 52-card deck consists of 26 red cards and 26 black cards, which are shuffled and players start with a $1 bet. Each card is exposed one at a time and is not replaced in the deck. Players can place any part of their current bet on whether the next card will be black or red, with odds one to one.
The player obviously has a favorable strategy, which involves counting the number of black and red cards seen. Counting the cards seen allows them to know how many cards of each color are left in the unseen part of the deck. For example, they can safely double their bet by not betting on any card other than the last card. This allows them to safely place their entire bet on the now inferred color of the last unseen card.
Kelly Strategy
The Kelly strategy is to choose a bet that maximizes the expected logarithm of the bet. We can derive it as follows.
let r is the number of red cards remaining in the deck, b Black cards remaining. Assumptions without loss of generality r > b. Then we want to maximize P[draw red] * log(1 + bet_fraction) + P[draw black] * log(1 - bet_fraction) as a function bet_fraction. This expression is maximized when the derivative is zero. The probability of drawing red next is r/(r + b). So we need to solve (r/(r + b)) / (1 + bet_fraction) - (b/(r + b)) / (1 - bet_fraction) = 0. some algebra tells us bet_fraction = (r - b) / (r + b).
So the entire Kelly betting strategy is:
- if
r = bthen don’t bet - if
r > bbet|r - b| / (r + b)Your percentage of shares in “Red” - if
b > rbet|r - b| / (r + b)A small percentage of your stake in “Black”.
exist[1]:
# import tools
import numpy as np
exist[2]:
# set up our pseudo-random number generator to produce shuffled decks
rng = np.random.default_rng(2024)
exist[3]:
# define our deck shuffling tool
def k_array_with_t_true(k: int, t: int):
"""Create a length-k boolean array with t-True values"""
is_true = np.array([False] * k, dtype=bool)
is_true[rng.choice(k, size=t, replace=False)] = True
return is_true
exist[4]:
# implement our betting strategy
def run_bets(is_red) -> float:
"""Run the Kelly betting strategy"""
stake = 1.0
n_red_remaining = int(np.sum(is_red))
n_black_remaining = len(is_red) - n_red_remaining
for i in range(len(is_red)):
# form bet
bet_red = 0
bet_black = 0
fraction = np.abs(n_red_remaining - n_black_remaining) / (n_red_remaining + n_black_remaining)
if n_red_remaining > n_black_remaining:
bet_red = stake * fraction
elif n_black_remaining > n_red_remaining:
bet_black = stake * fraction
# derive outcome
stake = stake - (bet_red + bet_black)
if is_red[i]:
stake = stake + 2 * bet_red
n_red_remaining = n_red_remaining - 1
else:
stake = stake + 2 * bet_black
n_black_remaining = n_black_remaining - 1
return stake
exist[5]:
# play the game 10000 times
payoffs = [
run_bets(k_array_with_t_true(52, 26)) for _ in range(10000)
]
assert np.max(payoffs) - 1e-8 < np.min(payoffs)
(np.min(payoffs), np.max(payoffs))
go out[5]:
(9.081329549427776, 9.081329549427803)
For each run, our return is 9.08 times our starting bet. Notably, there was no change or difference in the results. pay attention to this 9.08 The return is much greater than 2 The return of the simple “wait until the end” strategy.
This result is highly unusual for a Kelly strategy. The Kelly strategy guarantees against “bankruptcy” (losing all capital) and maximizes the expected growth rate of the logarithm of equity. But they often offer few other guarantees, may actually lose money, and the variation is often high. What would Kelly do in this situation? cannot fail?
an explanation
There is significant evidence that this strategy has zero variance.
have (52 choose 26) = 495,918,532,948,104 Possible arrangements of red and black cards. It is a standard result (not proven here) that in a correctly shuffled deck, each of these permutations is effectively equally likely.
We define a new “portfolio” strategy as follows.
- each
(52 choose 26)Possible red/black arrangements are designated as sub-strategies in our portfolio. - We allocate a
1/(52 choose 26)A small portion of the initial stake for each sub-strategy. We allow each sub-strategy to retain its own funds and do not reallocate funds between sub-strategies. - Each sub-strategy assumes that its assigned red/black arrangement is what would happen in the actual deck. The sub-strategy places its entire bet on each card, betting that the exposed card will match its own defined arrangement.
All but one of the portfolio sub-strategies will lose all their money because they end up betting all their holdings on the wrong guess. End the experience by correctly guessing a single strategy for the entire deck 52 Double it and lose nothing. Therefore, the strategy multiplies its starting bet by 2^(52). Therefore, our portfolio strategy itself always experiences total returns $1/(52 choose 26) * 2^(52) ~ $9.08 in the initial $1 bet. Final portfolio returns are independent of the order of the cards.
The argument ends with the claim that the new portfolio strategy is actually the same as the earlier Kelly strategy.
Think about what happens to the portfolio when we get a red card. in our portfolio strategies r / (r + b) Some non-bankrupt sub-strategies expect the next card to be “red”, and b / (r + b) Some non-bankrupt sub-strategies predict that the next card will be “black”. The next draw will bankrupt one of the families and double the other (depending on the color of the draw). However, some studies suggest that the combined equity of a portfolio strategy evolves as follows:
- total
stakegostake * 2 * b / (r + b)About painting “red” - total
stakegostake * 2 * r / (r + b)About painting “black”.
This is an algebra problem that confirms that the return on this portfolio is exactly The return pattern of our early Kelly putting strategy |r - b| / (r + b) The most common colors remaining. The Kelly strategy has exactly the same benefits as the portfolio strategy, and our results are that the two strategies are identical.
The Kelly strategy is zero variance because it is the same as a portfolio strategy that itself has zero variance.
One thought I would like to take away is as follows. Since we bet on the majority color, each time we lose the bet, the deck becomes more unbalanced and more favorable to us. If we place a small enough bet, the advantage of the wrong bet will offset the loss of capital. In this case, the Kelly strategy is pricing information or uncertainty. This is similar to the “exploration phase and exploitation phase” considerations in issues such as A/B testing.
The proof given comes from Winkler math puzzle. I strongly I recommend picking up this book and reading his articles on this and many other issues. The proof itself is very similar to the style of the cover. This is a cover invented later Universal Portfolio investment strategy.
category: math Quantitative Finance teaching