The Kelly Criterion: Where does the logarithm come from?

This is the third post in a four-part series exploring the Kelly criterion:

The neat thing about the derivations in the last two posts is that they give a motivation for "optimizing the logarithm of wealth". The logarithm is not put in by decree, but is a mathematical technicality that arises from the repeated betting process! Kelly mentions this in his original paper:

At every bet he maximizes the expected value of the logarithm of his capital. The reason has nothing to do with the value function which he attached to his money, but merely with the fact that it is the logarithm which is additive in repeated bets and to which the law of large numbers applies.

This argument is very general. Let's say we model the wealth VnV_n after nn rounds of betting based on the initial wealth V0V_0 in terms of a function f(R,l)=Vn+1/Vnf(R, l) = V_{n+1} / V_n as

Vn=V0f(R,l)n(1)V_n = V_0 f(R, l)^n \tag 1

where RR is a random variable describing the possible outcomes of the game, and ll is the fraction of available money to invest in each round. Then we can derive the following formula for the best ll value:

lopt=argmaxljf(rj,l)pjn=argmaxljpjlogf(rj,l)=argmaxlE[logVn+1Vn](2)\begin{aligned} l_{opt} & = \operatorname*{argmax}_l \prod_j f(r_j, l)^{p_j n} \\ & = \operatorname*{argmax}_l \sum_j p_j \log f(r_j, l) \\ & = \operatorname*{argmax}_l E \left[ \log \frac{V_{n+1}}{V_n} \right] \tag 2 \end{aligned}

where rjr_j are the possible investment outcomes and pjp_j are the associated probabilities. The crucial change from random variable RR to outcomes and probabilities rjr_j and pjp_j is justified by the law of large numbers. Based on the exponential nature of the formula, switching to a logarithmic view feels very natural.

Consequently, neither the details of the game — represented by the random variable RR — nor the exact form of the per-round return ff matter. Any iterative scheme with reinvestment of profits should be representable in the form of equation (1), leading to the logarithm in solution (2). Beyond the origin of the logarithm, this analysis also shows the universality of the Kelly derivation.

Unfortunately, this argument is mostly skipped in online discussions. Often the logarithm is not justified at all, or it is treated as "genius from the 1950s says: use log\log". Sometimes the result is also linked to utility theory, which posits that having twice the money is not twice as useful. While utility theory may be true, reasonable people can disagree on their utility function — exactly how useful more or less money is to them. However, Kelly's result is not grounded in utility, and the log\log does not represent logarithmic utility of money. Consequently, even people who disagree on their utility function should agree that the Kelly criterion is the fastest way to gain wealth.

I hope this post shed some light on the reasoning behind the Kelly decision scheme. If you're interested in interactive plots that really helped me understand this material, you can find them in this Jupyter Notebook.

In the next post, we'll take a closer look at the relation of the Kelly criterion to expected values.

The Kelly Criterion: Multiple Investment Opportunities

This is the second post in a four-part series exploring the Kelly criterion:

After the last post introduced the Kelly criterion and its application in deciding how much to invest in a single gamble, we'll investigate whether Kelly can help us choosing between multiple investment opportunities.

We'll start with a mathematical model:

V1=V0((1+r0)(1ili)+ili(1+ri))V_1 = V_0 \left( (1+r_0)(1 - \sum_i l_i) + \sum_i l_i(1 + r_i) \right)

Simple, right? :-)

  • V0,V1V_0, V_1 are the available money before and after the first round, as before.
  • r0r_0 is the risk-free return rate. This allows us to model opportunity costs (could put the money into a bank account instead of investing, r0=0.004r_0 = 0.004), or inflation (non-invested money loses value over time r0=0.02r_0 = -0.02).
  • lil_i is the fraction of the available money invested in stock ii.
  • rir_i is a random variable describing returns for stock ii.

The first term (1+r0)(1ili)(1+r_0) (1 - \sum_i l_i) represents all the money not invested in any stock, being invested at the risk-free return rate r0r_0. The second term ili(1+ri)\sum_i l_i(1 + r_i) represents the outcomes of the investments in individual stocks ii.

We will re-formulate a bit to simplify the expression:

V1V0=(1+r0)ili(1+r0)+ili(1+ri)=(1+r0)+ili(rir0)\begin{aligned} \frac{V_1}{V_0} & = (1+r_0) - \sum_i l_i (1+r_0) + \sum_i l_i(1 + r_i) \\ & = (1+r_0) + \sum_i l_i(r_i - r_0) \end{aligned}

We can further simplify by merging the lil_i and rir_i into the vectors l\vec l and r\vec r, with 1\vec 1 being a vector where all elements are 11:

V1V0=(1+r0)+l(rr01)\frac{V_1}{V_0} = (1+r_0) + \vec l \cdot (\vec r - r_0 \vec 1)

Let's move from a single game round to nn rounds:

VnV0=((1+r0)+l(rr01))n\frac{V_n}{V_0} = \left( (1+r_0) + \vec l \cdot (\vec r - r_0 \vec 1) \right)^n

Now we are again in a position where we can follow Kelly's prescription: invoking the law of large numbers and finding the ll which maximizes the gain Vn/V0V_n/V_0.

For large nn, we can approximate:

VnV0j(1+r0+l(rjr01))pjn\frac{V_n}{V_0} \approx \prod_j \left( 1+r_0 + \vec l \cdot (\vec r_j - r_0 \vec 1) \right)^{p_j n}

In this step we switched from the random variable r\vec r to its outcomes rj\vec r_j. Each possible outcome rj\vec r_j occurs with probability pjp_j. We justify this switch with the law of large numbers: the outcome rj\vec r_j will be observed proportionally to its probability, pjnp_j n times (for large nn). Consequently, we will have pjnp_j n factors involving rj\vec r_j in the overall product, with jj iterating over all potential outcomes of r\vec r.

Note that since rj\vec r_j is vector-valued, pjp_j is a joint probability distribution.

At this point we are nearly finished. We are looking for the vector lopt\vec l_{opt} that maximizes Vn/V0{V_n}/{V_0}. In analogy to last post, we arrive at:

lopt=argmaxlVnV0=argmaxllogVnV0=argmaxljpjlog(1+r0+l(rjr01))\begin{aligned} \vec l_{opt} & = \operatorname*{argmax}_{\vec l} \frac{V_n}{V_0} = \operatorname*{argmax}_{\vec l} \log \frac{V_n}{V_0} \\ & = \operatorname*{argmax}_{\vec l} \sum_j p_j \log \left( 1+r_0 + \vec l \cdot (\vec r_j - r_0 \vec 1) \right) \end{aligned}

This equation is not analytically solvable, but may be approximated as a quadratic programming problem as described in a paper by Vasily Nekrasov.

Conclusion

It should be obvious that the Kelly criterion is applicable in a wide range of scenarios, from gambling over investment decisions to whether to buy insurance. If you're interested in interactive plots that really helped me understand this material, you can find them in this Jupyter Notebook.

In the next post we'll discuss the origins of the logarithm in the Kelly formula.

The Kelly Criterion: Introduction

This is the first post in a four-part series exploring the Kelly criterion:

The Kelly criterion is a formula used to determine the optimal size of a series of bets in order to maximize wealth. It is often described as optimizing the logarithm of wealth, and will do better than any other strategy in the long run.

Let's look at a simple gamble: when you play, you win with probability pp and lose with probability q=1pq = 1-p. If you win, you get back your initial bet plus a fraction rr of that bet. If you lose, your bet is forfeited. The Kelly formula calculating the optimal fraction of your available wealth to bet is:

lopt=prqr=pr(1p)r=p1prl_{opt} = \frac{pr - q}{r} = \frac{pr - (1-p)}{r} = p - \frac{1-p}{r}

Here is a small demo to explore the formula:

Kelly calculation demo

p0.80
r0.40

Probability of winning: 80 %
Profit on win, as percentage of placed bet: 40 %
Optimal fraction of wealth bet in this game: 30 %

The main takeaways are:

  • In each game you invest a fraction ll of the total amount of money you have. If you play the game from the demo (p=0.8,r=0.4p=0.8, r=0.4) and you have $100 available, you should invest $30 (since l=0.3l=0.3). If you win, you will have $112 (100+30×0.4100 + 30 \times 0.4) and invest $33.60 (112×0.3112 \times 0.3) in the second round. If you lost the first round you'd have $70, and invest $21 in the second round. If you can not reinvest your earnings, Kelly does not apply.
  • This formula holds when a large number of games are played. If you play only few rounds of a game this may not apply.
  • When it applies, the Kelly strategy will generate the most wealth out of your initial starting capital.

Derivation of the Kelly criterion

We will take a short dive into mathematics to understand how Kelly came up with this formula. Let's compute the wealth V1V_1 after the first round of gaming, when starting from an initial wealth V0V_0:

V1=V0(1+WlrW+(1W)lrL)V_{1} = V_{0} (1 + Wlr_W + (1-W)lr_L)

Here, ll is the fraction of money bet, rWr_W is the profit on win, rLr_L is the fraction of the bet forfeited on loss (in the above scenario, rL=1r_L=-1). WW is a random variable that's 11 with probability pp and 00 with 1p1-p. So with probability pp we'll have W=1W=1, giving V1,win=V0(1+lrW)V_{1,win} = V_0 (1+lr_W), with probability 1p1-p we'll get V1,loss=V0(1+lrL)V_{1,loss} = V_0 (1+lr_L).

We can reformulate the expression in a way that will show an important generalization:

V1=V0(1+lrW)W(1+lrL)(1W)V_1 = V_0 (1+lr_W)^W(1+lr_L)^{(1-W)}

The two expressions look very different, but they are equivalent since WW can only take on the values 00 and 11. If W=1W=1 the second term will vanish since x0=1x^0 = 1, and we will get the same result for V1,winV_{1,win}. The same consideration holds for V1,lossV_{1,loss}.

If we repeat this game nn times, we arrive at

Vn=V0(1+lrW)Wn(1+lrL)(nWn)V_n = V_0 (1+lr_W)^{W_n}(1+lr_L)^{(n-W_n)}

with WnW_n being the number of wins in those nn games. Essentially, each won round adds a factor (1+lrW)(1+lr_W) to the expression, each lost round (1+lrL)(1+lr_L).

Now comes a crucial step: how many wins do we expect after playing many games? Asked mathematically, what value will WnW_n have for large nn? Because of the law of large numbers we expect W=pnW = pn. So for p=0.8p=0.8 and n=10000n=10000 we would expect to win 8000 out of the 10000 games.

Let's plug this into our formula:

Vn=V0(1+lrW)pn(1+lrL)(1p)nV_n = V_0 (1+lr_W)^{pn}(1+lr_L)^{(1-p)n}

The law of large numbers allowed us to eliminate the random variables WW, WnW_n and instead obtain an explicit formula in terms of p,n,rW,rLp, n, r_W, r_L. Since we are interested in maximizing our profit, we are looking for loptl_opt — the ll value that maximizes Vn/V0{V_n}/{V_0}.

lopt=argmaxlvnv0=argmaxllogvnv0=argmaxlplog(1+lrW)+(1p)log(1+lrL)\begin{aligned} l_{opt} & = \operatorname*{argmax}_l \frac{v_n}{v_0} \\ & = \operatorname*{argmax}_l \log \frac{v_n}{v_0} \\ & = \operatorname*{argmax}_l p \log(1 + l r_W) + (1-p) \log(1 + l r_L) \end{aligned}

We are free to introduce the logarithm and drop the nn factor because this does not change the value of loptl_{opt}.1 Differentiating the logarithmic expression and solving for ll gives:

lopt=prL1prWl_{opt} = -\frac{p}{r_L} - \frac{1-p}{r_W}

This is identical with the formula given in the introduction after substituting rL=1r_L = -1.

Extension to games with more than two possible outcomes

We can extend the Kelly argument to games that have a greater number of possible outcomes. Such games could be:

  • A game with 6 different rewards selected by roll of a 6-sided die, where rewards may be negative (money lost)
  • An investment in a stock, here we have a continuous range of outcomes.

If we have multiple outcomes rir_i, each happening with probability pip_i, we obtain:

lopt=argmaxlipilog(1+lri)l_{opt} = \operatorname*{argmax}_l \sum_i p_i \log(1 + l r_i)

While this equation is not easily solvable analytically, it is trivial to solve numerically. This allows us to extend the Kelly approach to a new kind of game with some interesting practical applications.

If you're interested in interactive plots that really helped me understand this material, you can find them in this Jupyter Notebook.

The Kelly formalism can be generalized further still, taking into account multiple parallel investment opportunities. We'll look at this in the next post.


1 The logarithm is a strictly monotonically increasing function, so α>βlogα>logβ\alpha \gt \beta \Leftrightarrow \log \alpha \gt \log \beta. Thus it doesn't change the location of any maxima: argmaxf(x)=argmaxlogf(x)\operatorname*{argmax} f(x) = \operatorname*{argmax} \log f(x). See Mark Schmidt's Argmax and Max Calculus paper for more information about properties of argmax\operatorname*{argmax}.

Exploring GDB's Python API with Jupyter

GDB — the most common console debugger on Linux systems — has a Python API for adding new debugger commands and pretty-printers for complex data structures, or to automate debugging tasks.

While Python scripts can be loaded from files, it is nice to interactively explore the API or the debugged program. IPython would be perfect for the job, but starting it directly inside GDB doesn't work well. Fortunately, it's easy to launch an IPython kernel and connect with an external Jupyter console.

Launching the kernel from the gdb prompt:

(gdb) python
>import IPython; IPython.embed_kernel()
>end

Gives the following message:

To connect another client to this kernel, use:
    --existing kernel-12688.json

We can start Jupyter on a separate terminal and connect to this kernel:

$ jupyter console --existing kernel-12688.json
In [1]: gdb.newest_frame().name()
Out[1]: 'main'

The GDB Python API is then available from the gdb module within this Python session. To get started, I'd suggest the API documentation or this series of tutorials.

Currently, only the console client can connect to existing kernels. Support in the Notebook or in Jupyter Lab is tackled in this Github issue. Even with the limited capabilities of the console client, it's a great way to explore the API and to tackle more complicated debugging problems that require automation to solve.

PyDays 2017

PyDays 2017 was Austria's first conference dedicated to the Python programming language. It took place on May 5 and May 6 and was graciously hosted by the Linuxwochen Wien at FH Technikum in Vienna. It was great on many levels: meeting new people excited about Python and where it's headed, over 20 talks, interesting hallway conversations, etc.

I helped out with the organization of the conference, mostly taking care of catering. We (the organization team) are very happy with how everything went. The atmosphere was welcoming and open, the quality of the talks and workshops was very good, attendance was great, and people seemed to have a really good time. From an organizational perspective, the talks mostly stayed on-time, the audio/video hardware worked fine, and the PyDays booth was well-received. Giving out snacks, coffee, soda, cake during breaks worked out nicely and was received very well. The feedback, both at and after the conference, was very positive.

In addition to the co-organization of the Conference, I also held a talk about Dask, a Python library for parallel computing. It provides data structures similar to NumPy Arrays or Python Dataframes that process operations in parallel and scale to out-of-memory datasets. Dask is exciting since it provides the analytical power and familiar mental model of Dataframes, but handles hundreds of gigabytes of data and allows seamless scaling from a single laptop to a computing cluster. The talk was well-received, and there was a lot of interest at the end and in the hallway afterwards. The slides are online, if you're interested as well.

Finally, I'd like to thank my co-organizers, Claus, Kay, Helmut and Sebastian, as well as the people who helped out during the conference, for all their great work to make the PyDays a success. I'd also like to thank our sponsors: the Python Software Foundation, the Python Software Verband e.V., T-Mobile, UBIMET, and Jetbrains.

Overall it was great to see so much community interest in Python. If you're passionate about Python as well, join us on the Python Austria Slack and our meetups!