Thursday, January 14, 2016

Kelly Criterion: Derivation

This is a follow-up to a previous post on the Kelly Criterion.


You may be familiar with the compound interest formula: \[a_n = a_0 (1+r)^n,\] where \(r\) is the constant annual (say) rate of return. Setting \(R = (1+r)\), we have \(a_n = a_0 R^n\).

If the returns per year are not constant (think stocks instead of bonds), then we have to modify the formula to, \[a_n = a_0 \prod_{i=1}^n R_i.\] Suppose the \(R_i\) come from a known (and "stable over time") random process. We know how to deal with sums and products of independent and identically distributed (iid) random variables.

As I demonstrated in the previous post, we don't want to maximize the arithmetic average \(\langle a_n \rangle\) because it is skewed by positive outcomes; instead, we use a geometric average.

We can do this using the property of logarithms.
    \log a_n & = \log a_0 + \sum_{i=1}^{n} \log R_i\\
    \langle \log \frac{a_n}{a_0} \rangle & = n \langle \log R \rangle,\\
    \end{align}\] where I have used the result that expected value of the sum of iid random variables, \(y = \sum_{i=1}^{n} x_i,\) is given by \(\langle y \rangle = n \langle x \rangle.\)

We wan to maximize \(\langle \log \frac{a_n}{a_0} \rangle\) by maximizing \(\langle \log R \rangle\).

Let us denote the average return \(S = \exp(\langle \log R \rangle)\), so that we can crudely write \(a_n \sim a_0 S^{n}\) (compare this with the formula  \(a_n = a_0 R^n\) for constant rate of returns).

Note that \(S\) is a function of \(f\). We want to choose \(f\) to maximize this growth rate.


Back to our wager. Let us generalize it a little bit.

Suppose there are \(m\) possible outcomes (instead of just two), each with probability \(q_i\), and payoff \(b_i\). Note that the \(q_i\)s have to add to one. How much do we wager?

We want to maximize \(S\) (or \(\log S\), since it is a monotonic function). \[\begin{align}
\log S & = \langle \log R \rangle \\
       & = q_1 \log(1 + b_1 f) + ... + q_m \log(1 + b_m f) \\
       & = \sum_{i=1}^{m} q_i \log(1 + b_i f)
      \end{align}\] Setting up:
\[\dfrac{d \log S}{df} = \sum_{i=1}^{m} \frac{q_i b_i}{1 + b_i f} = 0\] Solving the last equation for \(f\) gives the optimal value. This value corresponds to an average growth rate of \[S = \exp \left( \sum q_i (1 + b_i f^*) \right)\]
Special Case

When we have just two outcomes, \[\frac{q_1 b_1}{1 + b_1 f} + \frac{q_2 b_2}{1 + b_2 f} = 0\] Following the example in the last post, by Setting \(b_2 = -1\) and \(q_1 = q\), we get \[\frac{q b}{1 + b f} = \frac{1 - q}{1 - f},\] which simplifies to the familiar rule, presented there.

Python Code

Lets encode the equation to solve:

def funcKelly(f, q, b):
    """equation to solve for f"""
    s = 0.
    for qi, bi in zip(q,b):
        s += (qi * bi) / (1. + bi * f)
    return s

def optimalKelly(q, b):
    """given probabilities q and payouts b, 
       solve the equation to get optimal Kelly
       by solving the function funcKelly"""

    from scipy.optimize import brentq
    fstar = brentq(funcKelly, 0.0, 1.0, args=(q, b))
    return fstar

Geometric Average Growth Rate

Finally, let me plot the average growth rate S versus fraction f, by taking the average of 1000 independent simulation (of a series of 100 bets) with q = (0.5, 0.5), b = (2, -1).

The "star" on the plot shows the optimality of \(f^*\).

No comments: