Optimal Kelly criterion for process with N discrete outcomes

Question

I am trying to come up with a generalisation of the Kelly formula for optimal fractional betting but and have hit a roadblock. The Kelly criterion is usually explained via a game that ends in 1 of 2 states (e.g. a coin flip) and gives the optimal fraction of your wealth $f$ that should be bet each round to maximise growth. I'm trying to extend this to get $f$ for a game with N possible end states.

Here's what I have so far. Each round of the game ends in 1 of N possible states. The probability of getting any $n$ result is $p_n$ ($\sum_{n=1}^N p_n = 1$) and the payout is $b_n$ such that you wealth $X$ would change by $X_1 = X_0(1 + b_n f)$ on an outcome of $n$. The expected return after each round is given by:

$$ {X_1 \over X_0} = \prod_{n=1}^N(1+b_n f)^{p_n} $$

Taking the natural log of both sides (as per the original Kelly idea):

$$ ln\left({X_1 \over X_0}\right) = \sum_{n=1}^N p_n \ln(1+b_n f) $$

Differentiating and setting to zero gives:

$$ \sum_{n=1}^N{ {p_n b_n} \over {1+b_n f}} = 0 $$

This is where I am stuck. I would like to get $f$ in terms of some function of the $b_n$ and $p_n$ terms? So far I've been unsuccessful. Any idea mathematical tools/approach I can use?

I should add there there is no functional relationship between any of the $p_n$ and $b_n$ values that could be used to simplify here (except the relationship $\sum_{n=1}^N p_n = 1$). Also note that $b_n$ can be positive or negative.

Thanks!

Answer 1

Three notes:

(1) The function $\sum \tfrac{p_n b_n}{1+f b_n}$ is smooth and monotonically decreasing in $f$, so numerical root finding methods like bisection or Newton's method should work well. I would bet on this over any closed formula.

(2) Solving this problem directly involves finding the roots of a degree $n-1$ polynomial (the numerator of $\sum \tfrac{p_n b_n}{1+f b_n}$) so, if $n \geq 6$, there probably isn't a closed formula in radicals. Indeed, I did some experimentation and looked at the case $p_1=p_2=\cdots=p_6=1/6$ and $(b_1, b_2, \cdots, b_6) = (-1,1,2,3,4,5)$. Then the numerator of $\sum \tfrac{p_n b_n}{1+f b_n}$ is the quintic $p(f):=-7 - 70 x - 210 x^2 - 98 x^3 + 385 x^4 + 360 x^5$. I claim that this quintic has Galois group $S_5$, so we can't solve it in radicals.

To check this, I factored $p(f)$ modulo the first $100$ primes. I found that $p(f)$ is irreducible modulo $23$ and factors as three distinct linears and a quadratic modulo $89$, so, by a standard criterion, the Galois group is $S_5$. So we can't expect a closed formula in radicals. (But it is still easy to numerically solve the equation: The unique root in $[0,1]$ is $0.76653$.)

(3) To me, it seems odd to allow many outcomes, but still just a single parameter $f$. Wouldn't a more common case be that you have many potential bets, and you want to know how much wealth to allocate to each? So you want to maximize $\sum p_j \log(1+b_j f_j)$, subject to $\sum f_j \leq 1$?

The good news is that this is also doable numerically! The function $\sum p_j \log(1+b_j f_j)$ is convex down, so hill climbing should work well.

Answer 2

That looks like a reasonable approximation, with risk of f being a complex number. Going to the fourth term is exceedingly complicated but resolves the issues of cutting off at the third, as one real solution is guaranteed in a cubic equation.

Really though, there is an exact solution since you have complete knowledge of the game. Use the natural logarithm as is. If you had three possible outcomes with p1 + p2 + p3 = 1 then:

E(ln(x)) = p1ln(1 + b1f) + p2ln(1 + b2f) + p3ln(1 + b3f)

If b1 is total loss of bet then is -f, if b2 returns 10% of the bet then is +0.1f, etc.

Take derivative and set equal to 0 and solve for f. Is a quadradic equation and one solution for a game with positive expectation for the player will yield 0 < f < 1. This will hold true for higher order equations.

If more than five outcomes and thus an equation greater than the fourth power then you're forced to numerically approximate but very doable in modern times.

Can see a worked out example 2/3 the way down on this page. I've plugged its logarithm equation into Wolfram Alpha to numerically approximate the f that maximizes E(ln(x)) without needing to take the derivative. Also a link to a calculator from the bottom of the first page.