Kelly Gambling

Introduction

In Kelly gambling (Kelly 1956), we are given the opportunity to bet on \(n\) possible outcomes, which yield a random non-negative return of \(r \in {\mathbf R}_+^n\). The return \(r\) takes on exactly \(K\) values \(r_1,\ldots,r_K\) with known probabilities \(\pi_1,\ldots,\pi_K\). This gamble is repeated over \(T\) periods. In a given period \(t\), let \(b_i \geq 0\) denote the fraction of our wealth bet on outcome \(i\). Assuming the \(n\)th outcome is equivalent to not wagering (it returns one with certainty), the fractions must satisfy \(\sum_{i=1}^n b_i = 1\). Thus, at the end of the period, our cumulative wealth is \(w_t = (r^Tb)w_{t-1}\). Our goal is to maximize the average growth rate with respect to \(b \in {\mathbf R}^n\):

\[ \begin{array}{ll} \underset{b}{\mbox{maximize}} & \sum_{j=1}^K \pi_j\log(r_j^Tb) \\ \mbox{subject to} & b \geq 0, \quad \sum_{i=1}^n b_i = 1. \end{array} \]

Example

We solve the Kelly gambling problem for \(K = 100\) and \(n = 20\). The probabilities \(\pi_j \sim \mbox{Uniform}(0,1)\), and the potential returns \(r_j \sim \mbox{Uniform}(0.5,1.5)\) except for \(r_n = {\mathbf 1}\), which represents the payoff from not wagering. With an initial wealth of \(w_0 = 1\), we simulate the growth trajectory of our Kelly optimal bets over \(P = 100\) periods, assuming returns are i.i.d. over time. In the following code, rets is the \(K \times n\) matrix of possible returns with row \(r_i\), while ps is the vector of return probabilities \((\pi_1,\ldots,\pi_K)\).

suppressMessages(suppressWarnings(library(CVXR)))
set.seed(1)
n <- 20      # Total bets
K <- 100     # Number of possible returns
PERIODS <- 100
TRIALS <- 5

## Generate return probabilities
ps <- runif(K)
ps <- ps/sum(ps)

## Generate matrix of possible returns
rets <- runif(K*(n-1), 0.5, 1.5)
shuff <- sample(1:length(rets), size = length(rets), replace = FALSE)
rets[shuff[1:30]] <- 0    # Set 30 returns to be relatively low
rets[shuff[31:60]] <- 5     # Set 30 returns to be relatively high
rets <- matrix(rets, nrow = K, ncol = n-1)
rets <- cbind(rets, rep(1, K))   # Last column represents not betting

## Solve for Kelly optimal bets
b <- Variable(n)
obj <- Maximize(t(ps) %*% log(rets %*% b))
constraints <- list(sum(b) == 1, b >= 0)
prob <- Problem(obj, constraints)
result <- solve(prob)
bets <- result$getValue(b)

## Naive betting scheme: bet in proportion to expected return
bets_cmp <- matrix(0, nrow = n)
bets_cmp[n] <- 0.15                  # Hold 15% of wealth
rets_avg <- ps %*% rets
## tidx <- order(rets_avg[-n], decreasing = TRUE)[1:9]
tidx <- 1:(n-1)
fracs <- rets_avg[tidx]/sum(rets_avg[tidx])
bets_cmp[tidx] <- fracs*(1-bets_cmp[n])

## Calculate wealth over time
wealth <- matrix(0, nrow = PERIODS, ncol = TRIALS)
wealth_cmp <- matrix(0, nrow = PERIODS, ncol = TRIALS)
for(i in seq_len(TRIALS)) {
    sidx <- sample(K, size = PERIODS, replace = TRUE, prob = ps)
    winnings <- rets[sidx,] %*% bets
    wealth[,i] <- cumprod(winnings)
    
    winnings_cmp <- rets[sidx,] %*% bets_cmp
    wealth_cmp[,i] <- cumprod(winnings_cmp)
}

Growth curves for five independent trials are plotted in the figures below. Red lines represent the wealth each period from the Kelly bets, while cyan lines are the result of the naive bets. Clearly, Kelly optimal bets perform better, producing greater net wealth by the final period.

library(ggplot2)
library(tidyr)
df <- data.frame(seq_len(PERIODS), wealth)
names(df) <- c("x", paste0("kelly", seq_len(TRIALS)))
plot.data1 <- gather(df, key = "trial", value = "wealth",
                     paste0("kelly", seq_len(TRIALS)),
                     factor_key = TRUE)
plot.data1$Strategy <- "Kelly Optimal Bets"
df <- data.frame(seq_len(PERIODS), wealth_cmp)
names(df) <- c("x", paste0("naive", seq_len(TRIALS)))
plot.data2 <- gather(df, key = "trial", value = "wealth",
                     paste0("naive", seq_len(TRIALS)),
                     factor_key = TRUE)
plot.data2$Strategy <- "Naive Bets"
plot.data <- rbind(plot.data1, plot.data2)
ggplot(data = plot.data) +
    geom_line(mapping = aes(x = x, y = wealth, group = trial, color = Strategy)) +
    scale_y_log10() +
    labs(x = "Time", y = "Wealth") +
    theme(legend.position = "top")

Extensions

As observed in some trajectories above, wealth tends to drop by a significant amount before increasing eventually. One way to reduce this drawdown risk is to add a convex constraint as described in Busseti, Ryu, and Boyd (2016, 5.3)

\[ \log\left(\sum_{j=1}^K \exp(\log\pi_j - \lambda \log(r_j^Tb))\right) \leq 0 \]

where \(\lambda \geq 0\) is the risk-aversion parameter. With CVXR, this can be accomplished in a single line using the log_sum_exp atom. Other extensions like wealth goals, betting restrictions, and VaR/CVaR bounds are also readily incorporated.

Session Info

sessionInfo()
## R version 3.5.0 (2018-04-23)
## Platform: x86_64-apple-darwin15.6.0 (64-bit)
## Running under: macOS High Sierra 10.13.4
## 
## Matrix products: default
## BLAS: /Library/Frameworks/R.framework/Versions/3.5/Resources/lib/libRblas.0.dylib
## LAPACK: /Library/Frameworks/R.framework/Versions/3.5/Resources/lib/libRlapack.dylib
## 
## locale:
## [1] C
## 
## attached base packages:
## [1] stats     graphics  grDevices datasets  utils     methods   base     
## 
## other attached packages:
## [1] tidyr_0.8.1   ggplot2_2.2.1 CVXR_0.99    
## 
## loaded via a namespace (and not attached):
##  [1] gmp_0.5-13.1      Rcpp_0.12.17      pillar_1.2.2     
##  [4] compiler_3.5.0    plyr_1.8.4        R.methodsS3_1.7.1
##  [7] R.utils_2.6.0     tools_3.5.0       digest_0.6.15    
## [10] bit_1.1-13        evaluate_0.10.1   tibble_1.4.2     
## [13] gtable_0.2.0      lattice_0.20-35   rlang_0.2.0      
## [16] Matrix_1.2-14     yaml_2.1.19       blogdown_0.6.3   
## [19] xfun_0.1          Rmpfr_0.7-0       ECOSolveR_0.4    
## [22] stringr_1.3.1     knitr_1.20        tidyselect_0.2.4 
## [25] rprojroot_1.3-2   bit64_0.9-7       grid_3.5.0       
## [28] glue_1.2.0        R6_2.2.2          rmarkdown_1.9.14 
## [31] bookdown_0.7      purrr_0.2.4       magrittr_1.5     
## [34] backports_1.1.2   scales_0.5.0      htmltools_0.3.6  
## [37] scs_1.1-1         colorspace_1.3-2  labeling_0.3     
## [40] stringi_1.2.2     lazyeval_0.2.1    munsell_0.4.3    
## [43] R.oo_1.22.0

Source

R Markdown

References

Busseti, E., E. K. Ryu, and S. Boyd. 2016. “Risk–Constrained Kelly Gambling.” Journal of Investing 25 (3): 118–34.

Kelly, J. L. 1956. “A New Interpretation of Information Rate.” Bell System Technical Journal 35 (4): 917–26.