Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

Friday, August 10, 2012

The Kelly Betting Stategy

The Kelly betting strategy is for optimizing the expected growth rate of an investment when making a series of bets in which one has an advantage. The strategy is well-known in economics (as well as in gambling) and plays a huge role in real-life investing. 
"the Kelly criterion is integral to the way we manage money." -Legg Mason Capital Management CEO Bill Miller [1].
As an example, consider a game where a single die is rolled. An investor is willing to make with us a series of bets on each roll that a 6 is not rolled. That is, our kth bet is that a 6 will be rolled. If we put down a bet for a particular roll and win, the investor will give us back x times the amount we bet (this includes the money we initially put down). If we lose, the investor will keep our money. Let p be the probability that we will win the bet-- in this case \frac{1}{6}.

Before we think of a betting strategy, we first need to confirm that the expected money that we win in one bet is positive. Otherwise, it would be improvident for us to make any bets against this investor. Taking a basis of a one dollar bet and considering that we gain $(x-1) with probability p (a win) and lose $1 with probability 1-p:
E($ you earn in a single bet of $1) = p[$(x – 1)] - (1 – p)[$1] = px-1.

We need px>1 for the law of large numbers to dictate that we will have a net gain after placing many bets. Thinking of p as fixed, if x is too small and drives px<1—the investor is not willing to give us a good payoff* if we win—then we are expected to lose money because the investor has an advantage by risking little of his money in the bet but getting a relatively large reward from our bet if he wins. Thinking of x as fixed, we need the probability of winning a single bet, p, to be large enough to drive px>1-- if we are very unlikely to win the bet, it would be shortsighted for us to bet at all. 

Let’s assume that the investor offers us a payoff such that px>1. You have a bank account with V_0 dollars that you intend to invest. The dilemma is this: you definitely want to make bets that a 6 is rolled, as px>1 that guarantees you will earn a positive return after a large number of bets. If you win a bet, you should bet some of the extra money you just won in the next bet to increase the magnitude of your return; px>1 after all (akin to compounding interest). However, you don’t want to bet all of your investment pool each time or you will eventually lose your initial V_0 investment as well as any money you won up to that point when a number other than 6 is rolled (which is quite likely to happen).

At the two extremes, (1) you bet nothing for every bet k and lose the opportunity to gain money (2) you bet everything for every bet k and risk losing your entire savings (you certainly will eventually), after which you cannot place more bets. The Kelly betting system concerns when, for every bet k, your strategy is to bet a fixed fraction \alpha of your current investment pool**. Clearly, there is an optimum fraction \alpha of your bank account that you should bet each round in order to maximize your expected return. Let’s find it, following the derivation in the excellent book [2].


The random variable in this process is R_k, which we define by:
R_k= \{ 1,\mbox{ a 6 is rolled}
      =\{ 0,\mbox{  a six is not rolled}.

Let V_k be the size of our investment pool after the kth bet (V_0 fits in this notation). After the first bet, we have an investment pool of V_1= V_0 ( 1-\alpha) + V_0 \alpha x R_1 since we keep the V_0(1-\alpha) of our bank account that we did not bet and get back V_0 \alpha x only if we win (R_1=1 in this case). That is, V_1=V_0(1-\alpha +\alpha x R_1). After the second bet, V_2=V_1(1-\alpha) +V_1 \alpha x R_2 since we keep the V_1(1-\alpha) that we did not bet and get back V_1 \alpha x only if we win. We trace back to V_0 by our expression for V_1:
V_2=V_1 (1-\alpha+ \alpha x R_2)
V_2=V_0 (1-\alpha+ \alpha x R_1) (1-\alpha+ \alpha x R_2) and if we continue:
V_k=V_0 (1-\alpha+ \alpha x R_1) (1-\alpha+ \alpha x R_2)\cdot \cdot \cdot (1-\alpha+ \alpha x R_k).

This is where a trick comes in (sorry). Let use define a growth rate G_k such that we can write an exponential formula for the growth of our investment pool:
V_k=V_0 e^{kG_k}.
Taking the natural logarithm of both sides, we find that G_k=\frac{1}{k} \log \left(\dfrac{V_k}{V_0} \right). We know exactly what \dfrac{V_k}{V_0} is from two expressions above! Plugging this in and using a property of logarithms, that the log of a product of terms is the sum of the log of each term, we elucidate why we defined our growth factor this way:
G_k = \frac{1}{k} \log \left((1-\alpha+ \alpha x R_1) (1-\alpha+ \alpha x R_2)\cdot \cdot \cdot (1-\alpha+ \alpha x R_k) \right)
     = \frac{1}{k} \displaystyle \sum_{n=1}^{k} \log (1-\alpha +\alpha x R_n)
The above is just the average value that \log (1-\alpha +\alpha x R_n) takes on after k trials. Using the law of large numbers and letting k \rightarrow \infty, this is the expected value of \log (1-\alpha +\alpha x R). We calculate this by knowing that R=1 with probability p and R=0 with probability 1-p:
G_k=E(\log (1-\alpha +\alpha x R))= p \log (1-\alpha +\alpha x)+ (1-p) \log (1-\alpha)
Noting that G_k=G_k(\alpha) is a function of the betting fraction \alpha, we differentiate the growth rate G_k and set it to zero to solve for the \alpha that maximizes G_k (get out your paper). We finally get the optimum betting fraction in terms of the payoff for the bet and the probability of winning each bet:
\boxed{\alpha = \dfrac{px-1}{x-1}}.
The numerator px-1>0 is the expected return on a bet of one dollar and causes the optimum betting fraction to increase, which is intuitive. Of course, x>1 or we would be giving out money. As the investor is willing to payoff more, \alpha starts to look like p (take the limit as x \rightarrow \infty).

* the payoff odds are defined to be x-1, since this is really the money that you gain in the case of a win.
**investment pool is V_0 + whatever cash you won from all previous bets – whatever cash you lost from all previous bets. It is akin to buying stock and reinvesting dividends.

[1] http://www.businessweek.com/stories/2005-09-25/get-rich-heres-the-math
[2] Understanding Probability by Henk Tijms. 

No comments:

Post a Comment

Contributors