Introduction
This article will explain the specific calculation method for the Kelly criterion in gambling, following Kelly’s paper. The Kelly criterion is a betting method to maximize the average growth rate of funds in compound interest investments, which in economic terms corresponds to maximizing a logarithmic utility function. This is a topic that is also often discussed in financial and investment theory, but here we will only introduce the mathematical aspects.
Let \(\small G \) denote the average growth rate of a gambler’s capital using compound interest investments. Let us denote the initial capital amount by \(\small V_0 \) and the capital amount after \(\small N\) bets by \(\small V_N\). Then,
\[ \small G = \lim_{N\rightarrow \infty}\frac{1}{N} \log \frac{V_N}{V_0} \]
holds. Let consider a simple two-choice bet (called a bold play), such as guessing the outcome of a coin toss. Let the probability of winning be expressed as \(\small p\) and the probability of losing be expressed as \(\small q(=1-p)\). Furthermore, if the ratio of the gambling stake to the capital amount per bet is expressed as \(\small f\), the capital amount after \(\small N\) bets is expressed as \(\small W\) for the number of wins and \(\small L\) for the number of losses, then
\[ \small V_N = (1+f)^{W}(1-f)^{L}V_0 \]
holds. Where, \(\small W+L=N\). Hence,
\[ \begin{align*} \small G \; & \small = \lim_{N\rightarrow \infty} \left[\frac{W}{N} \log (1+f) + \frac{L}{N} \log (1-f) \right] \\ & \small = p \log(1+f) + q\log(1-f) \end{align*} \]
can be obtained.
Find the stake \(\small f\) that maximizes the average growth rate of capital \(\small G\). If we simply differentiate it, we get
\[ \small \frac{dG}{df} = p\frac{1}{1+f} – (1-p) \frac{1}{1-f} = 0, \]
therefore,
\[ \small f^{\ast} = 2p-1 = 1-2q \]
can be obtained. Substituting these values, we can calculate that the maximum average growth rate of capital \(\small G^{\ast}\) is:
\[ \small G^{\ast} = \log2 +p\log p+q \log q. \]
In Kelly’s paper, the logarithm is calculated using the base 2, resulting in
\[ \small G^{\ast} = 1 +p\log_2 p+q \log_2 q, \]
but these are considered to be equivalent. Here, the base of the logarithm is calculated as the natural logarithm. Let us consider a similar calculation for the general case.
The General Case (When the Odds Are Fair)
Let us consider a gambling game in which there are \(\small n\) choices, such as horse racing or lotteries, and one of the choices is the winner, and the wagers placed are paid out to the winner. While a two-choice bet like the one in the previous section is called a single wager, this type of bet is called a multiple wager. A betting method in which the payout percentage remains the same regardless of the amount of the bet as in the previous section, is called fixed odds betting. However, in general gambling, a betting method called Parimutuel betting is adopted in which the payout percentage decreases as the choice becomes more popular. The following will consider the latter method. Let the probability of winning for each choice be denoted as \(\small p_1,p_2,\cdots, p_n\), and the amount bet on each choice be denoted as \(\small A_1,A_2,\cdots,A_n\). If choice \(\small i\) wins, the bet placed on that choice will be refunded at
\[ \small \alpha_i = \frac{\sum_{j=1}^n A_j}{A_i} \]
times the amount. The multiplier of the amount that will be refunded in the event of such a win is called the odds. The probability of winning calculated by working backwards from the odds is expressed as \(\small q_1,q_2,\cdots,q_n\). That is, let assume that
\[ \small q_i = \frac{1}{\alpha_i} \]
holds.
In order for gambling to be fair (a game in which the expected value of the amount returned for each unit of currency invested is 1),
\[ \small p_i \alpha_i = 1, \quad \forall\;i \]
must be true. That is,
\[ \small p_i = \frac{1}{\alpha_i} = q_i, \quad \forall\;i \]
must hold. This corresponds to cases where the probability of winning can be objectively estimated, such as with a coin toss, dice, or roulette. As in the previous section, let us denote the ratio of the bet amount to the capital amount per round as \(\small f_1,f_2,\cdots,f_n\) and assume that one must bet the entire capital. In this case, the average growth rate of the gambler’s capital is:
\[ \small G = \sum_{j=1}^n p_j \log f_j \alpha_j = \sum_{j=1}^n p_j \log f_j-\sum_{j=1}^n p_j \log p_j. \]
Find the allocation of capital \(\small f_1,f_2,\cdots,f_n\) that maximizes the average growth rate of capital \(\small G\). The optimization problem can be formulated as:
\[ \begin{align*} \small \max \; & \small \sum_{j=1}^n p_j \log f_j-\sum_{j=1}^n p_j \log p_j \\ \small \text{s.t.} \; & \small \sum_{j=1}^n f_j = 1. \end{align*} \]
Introducing the slack variable \(\small \lambda\), defining the Lagrangian as:
\[ \small L(f_1,\cdots, f_n,\lambda) = \small \sum_{j=1}^n p_j \log f_j-\sum_{j=1}^n p_j \log p_j + \lambda \left(1-\sum_{j=1}^n f_j \right), \]
and finding the Karush-Kuhn-Tucker (KKT) condition, we get
\[ \begin{align*} &\small \frac{\partial L}{\partial f_i} = \frac{p_i}{f_i}-\lambda = 0, \quad \forall \; i \\ &\small \frac{\partial L}{\partial \lambda} = 1-\sum_{j=1}^n f_j = 0. \end{align*} \]
If we add up the first equation, we get
\[ \small \sum_{i=1}^n p_i = \lambda \sum_{i=1}^n f_i. \]
Since
\[ \small \sum_{i=1}^n p_i =\sum_{i=1}^n f_i = 1 \]
holds from the definitions, \(\small \lambda = 1\) can be obtained. Therefore, the optimal fund allocation is:
\[ \small f_i^{\ast} = p_i = q_i, \]
and the optimal allocation is to allocate funds in proportion to the probability of winning estimated from the odds. In this case, the rate of capital growth is \(\small G^{\ast} = 0 \), which means that in a fair game, no matter how much you bet, you cannot increase your funds.
When the Odds Are Not Fair
Let us consider the discussion in the previous section in the case of gambling, such as horse racing, where the probability of winning is not self-evident. In this case, your own estimated probability of winning \(\small p_i\) will be different from the probability of winning calculated by working backwards from the odds \(\small q_i\). It is also assumed that there are no bookmaker fees and that all bets are returned to winners. That is, let assume
\[ \small \sum_{i=1}^n q_i = \sum_{i=1}^n \frac{1}{\alpha_i} = 1 \]
holds true. The optimization problem can be also formulated as:
\[ \begin{align*} \small \max \; & \small \sum_{j=1}^n p_j \log f_j-\sum_{j=1}^n p_j \log q_j \\ \small \text{s.t.} \; & \small \sum_{j=1}^n f_j = 1 \end{align*} \]
just like the previous section. Introducing the slack variable \(\small \lambda\), defining the Lagrangian as:
\[ \small L(f_1,\cdots, f_n,\lambda) = \small \sum_{j=1}^n p_j \log f_j-\sum_{j=1}^n p_j \log q_j + \lambda \left(1-\sum_{j=1}^n f_j \right), \]
and finding the Karush-Kuhn-Tucker (KKT) condition, we get
\[ \begin{align*} &\small \frac{\partial L}{\partial f_i} = \frac{p_i}{f_i}-\lambda = 0, \quad \forall \; i \\ &\small \frac{\partial L}{\partial \lambda} = 1-\sum_{j=1}^n f_j = 0.\end{align*} \]
The solution is the same as in the previous section, it can be obtained as:
\[ \small f_i^{\ast} = p_i \neq q_i. \]
In this case, if you believe that your estimate of the probability is more accurate than the consensus opinion, you should base your betting ratios on your estimate of the probability and ignore the probability estimated by the odds.
When There Is “Track Take”
In typical gambling, the entire bet is not distributed to the player, but the bookmaker takes a cut. This is called Track Take or House Edge (House Advantage), and in many cases this rate is quite significant. For example, in Japan, the bookmaker’s share in horse racing and boat racing is said to be 25% and in lottery it is said to be 50%. This is probably not much different in other countries. Historically in Japan, gambling halls were often held in temples, and they were called “tera-zeni (temple take).” Let us find the optimal betting ratio in this case.
The calculations are complicated, so to avoid getting bored while reading the proof, I will first show you the specific calculation method. Since the gambling house owner takes a certain percentage of the total bet \(\small 0 < \theta < 1 \) as the house edge, the odds in this case are calculated as:
\[ \small \alpha_i = \frac{(1-\theta)\sum_{j=1}^n A_j}{A_i}. \]
Therefore, the sum of \( \small q_i \) does not equal 1, so
\[ \small \sum_{i=1}^n q_i = \frac{1}{1-\theta}> 1 \]
holds. Without loss of generality, we reorder the subscripts to favor the gambler. That is, let assume \( \small p_1 /q_1 > p_2 /q_2 > \cdots > p_n / q_n \). In this case, by calculating \( \small t^{\ast} \) that satisfies
\[ \small t^{\ast} = \arg \min_t \frac{1-\sum_{j=1}^t p_j}{1-\sum_{j=1}^t q_j} \quad s.t. \;\; \sum_{j=1}^t q_j < 1 \]
(Here, \( \small \arg \min_t f(t) \) denotes the value of \( \small t \) that minimizes \( \small f(t) \).), the optimal betting ratio for the gambler can be calculated as:
\[ \begin{align*} & \small f_i = \max\{p_i-b \; q_i, 0 \} \\ & \small b = \frac{1-\sum_{j=1}^{t^{\ast}} p_j}{1-\sum_{j=1}^{t^{\ast}} q_j}. \end{align*} \]
Since the sum of \( \small q_j \) is greater than 1, \( \small t^{\ast} < n \) must hold. Hence, in this case, you will only bet on a few relatively advantageous choices, \( \small \sum_{i=1} f_i = 1-b \leq 1 \), and so you will only bet a portion of your bankroll.
Let us prove the above formula. Unlike when the odds are fair, you cannot justify betting all of your funds, so the proportion of your funds to keep on hand is represented as ( \small b ). In this case, The average growth rate of a gambler’s capital can be expressed as:
\[ \small G = \sum_{j=1}^n p_j \log \left(b+f_j \alpha_j \right). \]
As with the case without Track Take, if we set appropriate constraints, the optimization problem can be formulated as:
\[ \begin{align*} \small \max_{b, f_1, \cdots, f_n} \; & \small \sum_{j=1}^n p_j \log \left(b+ f_j \alpha_j \right) \\ \small \text{s.t.} \; & \small b + \sum_{j=1}^n f_j = 1, \; b \geq 0, \; f_j \geq 0 \; \forall j. \end{align*} \]
Introducing the slack variable \(\small k,\lambda_1,\cdots,\lambda_n \), defining the Lagrangian as:
\[ \small L(b, f_1,\cdots, f_n, k, \lambda_1,\cdots,\lambda_n) = \sum_{j=1}^n p_j \log \left(b+f_j \alpha_j \right) + k \left( 1-b- \sum_{j=1}^n f_j \right) + \sum_{i=1}^n \lambda_i f_i \]
and finding the Karush-Kuhn-Tucker (KKT) condition, we get
\[ \begin{align*} & \small \frac{\partial L}{\partial f_i} = \frac{p_i \alpha_i}{b+f_i \alpha_i}-k + \lambda_i = 0, \quad \forall \; i \\ & \small \frac{\partial L}{\partial b} = \sum_{j=1}^n \frac{p_j}{b+f_j \alpha_j} – k = 0\\ &\small \frac{\partial L}{\partial k} = 1 -b -\sum_{j=1}^n f_j = 0 \\ & \small \lambda_if_i = 0, \quad \forall \; i. \end{align*} \]
Note that if \(\small f_i > 0 \), then \( \small \lambda_i = 0 \), and if \(\small f_i = 0 \), then \( \small \lambda_i > 0 \).
By calculating the sum of the first equation for the subscript of \( \small f_i >0 \), we get
\[ \begin{align*} \small \sum_{j \in \{i|f_i > 0 \}} p_j & \small = k b \sum_{j \in \{i|f_i > 0 \}} \frac{1}{\alpha_j} + k \sum_{j \in \{i|f_i > 0 \}}f_j \\ & \small = k b \sum_{j \in \{i|f_i > 0 \}} \frac{1}{\alpha_j} + k(1-b). \end{align*} \]
For the second equation, if we calculate the subscripts for \( \small f_i >0 \) and \( \small f_i =0 \) separately,
\[ \small k b \sum_{j \in \{i|f_i > 0 \}} \frac{1}{\alpha_j} + \left( 1-\sum_{j \in \{i|f_i > 0 \}} p_j \right) = k b \]
holds. Substituting the above formula, we get \( \small k = 1 \). Therefore,
\[ \small b = \frac{1-\sum_{j \in \{i|f_i > 0 \}} p_j }{1-\sum_{j \in \{i|f_i > 0 \}} \frac{1}{\alpha_j}}= \frac{1-\sum_{j \in \{i|f_i > 0 \}} p_j }{1-\sum_{j \in \{i|f_i > 0 \}} q_j}\]
can be obtained.
\[ \small f_i = p_i-\frac{b}{\alpha_i} = p_i-b q_i, \quad f_i > 0 \]
can be obtained by substituting the above equation into the first equation of the KKT condition and rearranging. Finally, how to determine the subscripts such that \( \small f_i > 0 \) can be done by determining them in order of increasing \(\small p_i \alpha_i \). Also, as long as \(\small \sum_j q_j < 1 \) it is a profitable bet (expected return is positive), so we can determine them so that the available funds \(\small b \) are minimized within the range that satisfies this. From the above, we can prove that the capital allocation method shown first is a strategy that maximizes the expected growth rate of capital.
Reference
[1] Ethier, Stewart N. The Doctrine of Chances: Probabilistic Aspects of Gambling. Springer-Verlag, 2010.
[2] Kelly, John L. A New Interpretation of Information Rate. Bell System Technical Journal, 1956.
Comments