July | 2014 | Thiago G. Martins

Assume that a gambler has the possibility to bet a fraction ${f}$ of his capital in the outcome of a specific event. The Kelly criterion first presented in [1] and summarized below find the ${f}$ that maximizes the exponential rate of growth of the gambler’s capital under different scenarios, which is equivalent to maximizing period by period the expected log utility based on the current capital.

Discussion on why this choice of optimization makes sense was formally discussed in [2] and might be the subject of a future post. Intuitively, it makes sense to use this criterion if you bet regularly and reinvest your profits.

Exponential rate of growth

Lets define a quantity ${G}$ called the exponential rate of growth of the gambler’s capital, where

$\displaystyle G = \underset{N \rightarrow \infty}{lim} \frac{1}{N} \log \frac{V_N}{V_0} \ \ \ \ \ (1)$

and ${V_N}$ is the gambler’s capital after ${N}$ bets, ${V_0}$ is his starting capital, and the logarithm is to the base two. ${G}$ is the quantity we want to maximize.

Perfect knowledge

In the case of perfect knowledge, the gambler would know the outcome of the event before anyone else and would be able to bet his entire capital at each bet. Then, ${V_N = 2^N V_0}$ and ${G = 1}$ .

Binary events

Consider now a binary event where the gambler has a probability ${p}$ of success and a probability ${q = 1 - p}$ of failure. In this case the gambler would go broke for large ${N}$ with probability ${1}$ if he betted all his capital in each bet, even though the expected value of his capital after ${N}$ bets is given by

$\displaystyle E[V_N] = (2p)^N V_0$

Because of that, let us assume that the gambler will bet a fraction ${l}$ of his capital each time. Then

$\displaystyle V_N = (1+l)^W (1-l)^L V_0$

where ${W}$ and ${L}$ are the number of wins and losses after ${N}$ bets. Following the definition given in Eq. (1), it can be shown that

$\displaystyle G = p \log (1 + l) + q \log(1-l),\text{ with prob. 1} \ \ \ \ \ (2)$

Maximizing Eq. (2) with respect to ${l}$ gives

$\displaystyle l = p - q \quad \text{ and } \quad G_{\text{max}} = 1 + p \log p + q\log q$

where ${p - q}$ is called the edge.

If the payoff is ${B}$ for a win and ${-1}$ for a loss, then the edge is ${Bp - q}$ , the odds are ${B}$ , and

$\displaystyle l = \frac{Bp - q}{B} = \frac{\text{edge}}{\text{odds}}$

Multiple outcome events

Lets now consider the case where the event has more than two possible outcomes, not necessarily equally likely.

– Fair odds and no “track take”

Lets first consider the case of fair odds and no “track take”, that is

$\displaystyle \text{odds}_s = \frac{1}{p_s}\quad \text{ and } \quad \sum \frac{1}{\text{odds}_s} = 1$

where ${p_s}$ is the probability of observing the outcome ${s}$ in a given event, as estimated by the entity offering the odds.

Consider ${a_s}$ to be the fraction of the gambler’s capital that he decides to bet on ${s}$ based on his belief of the probability of observing the outcome ${s}$ in a given event. The gambler’s estimated probability for an outcome ${s}$ will be denoted by ${p^{(g)}_s}$ .

Since there is no “track take”, there is no loss in generality in assuming that

$\displaystyle \sum a_s = 1.$

That is, the gambler bets his total capital divided among the possible outcomes.

In this case, [1] have shown that

$\displaystyle a_s = p^{(g)}_s$

That is, the gambler should allocate his capital according to how likely he thinks each outcome is.

– Unfair odds and no “track take”

In this case

$\displaystyle \sum \frac{1}{\text{odds}_s} = 1$

but ${\text{odds}_s}$ are not necessarily equal to ${1/p_s}$ . Since there is no track take we can still consider ${\sum a_s = 1}$ .

Here, the value of ${a_s}$ that maximizes ${G}$ is again given by ${a_s = p^{(g)}_s}$ . Interesting conclusions can be taken from this result:

As with the case of fair odds, ${G}$ is maximized by putting ${a_s = p^{(g)}_s}$ . That is, the gambler ignores the posted odds in placing his bets!
Subject to ${\sum (1/\text{odds}_s) = 1}$ , the value of ${G}$ is minimized when ${\text{odds}_s = 1/p_s}$ . That is, any deviation from fair odds helps the gambler.

– When there is a “track take”

In case there is a track take, it can no longer be assumed that ${\sum a_s = 1}$ . Let ${b = 1 - \sum a_s}$ be the fraction not bet by the gambler.

The maximization process derived in [1] may be summarized as follows:

(a) Permute indices so that ${p^{(g)}_s \times \text{odds}_s \geq p^{(g)}_{s+1} \times \text{odds}_{s+1}}$
(b) Set b equal to the minimum positive value of
$\displaystyle \frac{1 - p_t}{1 - \sigma _t},\quad \text{where}\quad p_t = \sum _1^t p^{(g)}_s,\quad \sigma_t = \sum _1^t 1/\text{odds}_t$
(c) Set ${a_s = \max(p^{(g)}_s - b/\text{odds}_s, 0)}$ . The ${a_s}$ will sum to ${1 - b}$ .

It should be noted that if ${p^{(g)}_s \times \text{odds}_s < 1}$ for all ${s}$ no bets are placed. But if the largest ${p^{(g)}_s \times \text{odds}_s > 1}$ some bets might be made for which ${p^{(g)}_s \times \text{odds}_s < 1}$ , i.e. the expected gain is negative. This violates the criterion of the classical gambler who never bets on such events.

References:

[1] Kelly, J. L. (1956). A new interpretation of information rate. Information Theory, IRE Transactions on, 2(3), 185-189.
[2] Breiman, L. (1961). Optimal gambling systems for favorable games.
[3] MacLean, L. C., Thorp, E. O., Ziemba, W. T. (Eds.). (2011). The Kelly capital growth investment criterion: Theory and practice (Vol. 3). world scientific.

Thiago G. Martins

Data Scientist at Yahoo!

Monthly Archives: July 2014

The Kelly criterion for gambling