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 $k$th 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 $k$th 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.