Iterative Simultaneous Kelly Solution |

Iterative Simultaneous Kelly Solution

I like to use LaTeX, so this is mostly an excuse for me to practice my LaTeX skills. Whether one is familiar or unfamiliar with the Kelly Criterion, the concepts outlined below help to give insight to how one can make possible improvements when certain conditions are met. Generally, improvements from a sequential to simultaneous adjustment of the Kelly stakes are slight. However, as will be shown, slightness can turn considerable when extrapolated over longer time frames. Feel free to just jump here.

Why a Log-Utility

The Kelly Criterion generalizes a model that maximizes the growth of one’s bankroll using a logarithmic utility. Why does this work? Well, its due to the inherent properties of logarithms. For instance, log2 (8) tells you how many times to divide eight by two to get one. Keep dividing by two in perpetuity and the number never reaches zero. Thus, using the Kelly Criterion, one has infinite bankroll, assuming there is no minimum placed on wager sizes. With infinite bankroll, there is no maximum placed on how big the bankroll can grow to.

Using a log-utility, bankroll is now the sum of the probabilities of the log-returns for any wager. Concretely, the return is simply the payout times the percentage of bankroll wagered. For one wager, with p as the win probability, w as the payout, and x as the wager size, the rate of growth is:

$G(x) = p \log (1+wx) + (1-p) \log (1-x)$

The payout, w, on a win is the decimal odds – 1. Since a losing bet results in w = -1, the return on a losing bet is 1-x. And when x = 1, the logarithm is undefined, and ruin is guaranteed. (Financial conditions when x > 1 have yet to be of concern.)

The optimal wager size, or stakes, for any given bet is now the partial derivative of the function G with respect to x.

$\frac { \partial G}{ \partial x} = \frac { pw }{1 + wx} + \frac { 1-p } { 1-x }$

Conveniently, the function G is a concave function, and at some point on the interval $0 \le x \le 1$ , function G converges to a maximum, the tangent slope of the curve equals zero. Setting the partial derivative to zero gives:

$x = \frac { pw - 1 + p }{ w } = \frac { dp - 1 } { w }$

(d = decimal odds)

This can also be expressed in terms of probabilities, since the win probability divided by the implied probability, 1/d, is roughly equal to the return on a winning wager:

$1 + wx \approx \frac { p }{ p_{imp}}$

And the optimal stakes can also be found with the formula:

$x = \frac { p - p_{imp} } { 1 - p_{imp} }$

Simultaneity

For sequential stakes, the previous holds true. However, making wagers simultaneously results in a set of stakes that does not maximize log-utility. Since the bankroll isn’t re-adjusted every time a wager wins or loses, an adjustment has to be made. For example, with two independent simultaneous events (wagers placed at the same time), the function G equals:

$G(x _{1}, x_{2}) = p _{1}p _{2}log(1+w _{1}x _{1} + w _{2}x _{2}) + q _{1}p _{2}log(1 - x _{1} + w _{2}x _{2}) + p _{1}q _{2}log(1+w _{1}x _{1} - x _{2}) + q _{1}q _{2}log(1 - x _{1} - x _{2})$ $q _{1}, q _{2} = 1 - p _{1}, 1 - p _{2}$

The size of possible joint outcomes is mⁿ, m being the single game outcomes (typically binary), and n the number of simultaneous events. In this case, there are four possible joint outcomes. When n becomes larger than two, the space of joint outcomes becomes too large to write down completely, so in more compact notation, the function G can be reduced to:

$G(x _{1}, x _{2}, \dots, x _{n}) = \sum _{i}^{m^n} \textbf{P} _{i} log(1+\sum _{j}^n w _{ij} x_{j})$

Where P is an mⁿ x 1 vector, and $\prod _{j}^n p _{j} = P _{i}$

In Vectorized form:

$G = \textbf{P}^\intercal \log(1 + \textbf{WX})$

W is an mⁿ x n matrix, $w \in \textbf{W} _{i}, x \in \textbf{X}$

Iterative Solution

As mentioned before, there are implied constraints placed on x. The sum of all stakes can not exceed one, and negative stakes are yet unknown to commerce. With that in mind, if one is fortunate enough to have a rather size-able edge across multiple simultaneous bets, the stakes can be re-calculated with elementary math:

$x _{i} := \frac {x _{i}}{\sum _{i}^{n} x_{i}}$

Whether this is a necessary step or not will be obvious given a set of events. Regardless, the assumption here is the function G is not maximized using single game stakes, because after a result is final, the initial bankroll changes. Any number r <> ar if a <> 1. (When the stakes are zero, the number of simultaneous events simply becomes n – 1, and does not effect the current bankroll).

Through a derivative-free, iterative solution, the goal is to move up a curve until the point reaches an apex, so arbitrary steps are suitable enough to reach the desired goal. The result will be the optimal kelly fraction across all stakes, which has the benefit of maintaining proportionality. Conveniently, the time-complexity of such an algorithm has a lower bound of 1 and an upper bound of N, number of iterations, which should terminate, at the most, when the kelly fraction = 0.

Assuming the matrices P, W, and X have been populated (pseudocode):

alpha = 1
N = 100
G_temp = -1
for i = 1 to N
    X := X * alpha  ##alpha = fraction
    G = P_transpose * log(1+W*X)
    if G < G_temp
        break
    else
    G_temp = G
    alpha = alpha - .01  ##Sufficient step size, alpha terminates at zero
    end
end

This should guarantee a solution. Two things to mention, the statement “Assuming the matrices P, W, and X have been populated” is of major importance, and should not be reduced to assumptions. However one chooses to populate an array, matrix, etc…, this adds considerably to the time-complexity of the algorithm. The size is enormous, and assigns $\Theta (c*m^n)$ the new lower bound.

I’ve created an example with random probabilities and payouts, to visualize the algorithm.

$\begin{tabular}{|l|l|l|} \hline \textbf{implied p}&\textbf{p}&\textbf{stake}\\\hline 0.5776&0.6250&0.1122\\ 0.5560&0.5988&0.0965\\ 0.5994&0.6427&0.1080\\ 0.5273&0.5682&0.0866\\ 0.5235&0.5719&0.1015\\ 0.4070&0.4375&0.0514\\ 0.4964&0.5431&0.0927\\ 0.4738&0.5323&0.1112\\ 0.4175&0.4691&0.0886\\ 0.4150&0.4676&0.0899\\\hline \end{tabular}$

In Octave, the entire process took 0.03 seconds. That was worth a .07% increase in bankroll. The more events there are the more one will benefit.

As mentioned before, the improvements may be slight. But setting G as the rate of growth in the equation, Y = e^rt, can translate into drastic increases in bankroll. A brief example of the time it takes to triple bankroll given r:

$3 = e^{rt}$

$r = .030, \ t = \frac {\ln(3)}{.030} \approx 36.62$

$r = .025, \ t = \frac {\ln(3)}{.025} \approx 43.94$

A 0.5% increase in bankroll in this case means if one makes a series of wagers simultaneously, each meeting similar conditions, approximately seven such wagers are unnecessary to reach three times initial bankroll. If n = 10, that’s 70 different bets. Performed weekly and that’s over two months worth of extra money ever year. Over ten years and a bettor can secure over 18 months of additional bankroll had one considered simultaneous outcomes.

Direct Calculation

The iterative solution has the advantage of maintaining proportionality. This can be restated as using some scalar, s, to optimize stakes, X:

$s \begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \Rightarrow \textbf{max}(G)$

Now the function, G, becomes:

$G(s) = \textbf{P}^\intercal \log (1 + \textbf{W} \times s \textbf{X})$

And the derivative of G:

$\frac { dG}{ ds} = \textbf{P}^\intercal (\textbf{WX} \div (1+\textbf{W} \times s \textbf{X}))$

Here, division is element-by-element division. In most programming languages, this is syntactically equivalent to “(W*X)./(1+W*X).”

I’ve reduced G to a one variable equation, so there should be a direct solution without having to iterate by setting the derivative of G to zero and solving for s, the kelly fraction. (N = mⁿ )

$s = \frac { \sum _i^{N} P_i \sum _j^{n} w_{ij} x_j}{ \sum _i^{N} P_i ( \sum _j^{n} w_{ij} x_j)^2 } = \frac { \textbf{P}^\intercal (WX)}{ \textbf{P}^\intercal (WX \circ WX) }$

(Hadamard Product)

Mutual Exclusivity

Much work has been done on simultaneous events whose outcomes are dependent on each other (i.e. horse racing, futures). A general algorithm for kelly stakes across mutual exclusive events is outlined at wikipedia.

Further Reading
SBRForum Kelly Calculator
Algorithms for optimal allocation of bets on many simultaneous events
Optimal Betting Strategies for Simultaneous Games

Download article as PDF

This entry was posted on July 1, 2012, 6:48 pm and is filed under Betting, Kelly. You can follow any responses to this entry through RSS 2.0. You can leave a response, or trackback from your own site.