2015年1月8日 星期四

[博弈論] Kelly criterion - Simplest Case

這次要介紹 凱利 J. Kelly, Jr 在 1956 年利用 Information Theory 所提出的一套 賭博理論結果,又稱作 凱利判準 (Kelly Criterion) ,此結果其後又被其在同僚 E. D. Throp 進一步推廣,且在近幾十年中已被逐步推廣且應用在 避險基金 與 投信銀行 等金融業中。以下我們將簡介最簡單的 Kelly criterion 型式:

凱利判準 (Kelly Criterion): 賭徒參與賭局,應追求 最大化 長期 報酬增長率 $G$ (asymptotically maximize the growth rate of wealth)
凱利公式 (Kelly formula): 此公式用來計算 每次賭金押注應該是多少可達成最大化 長期報酬增長率 $G$。

不過在介紹之前我們先考慮以下一個簡單的賭局情形:

Example
考慮 某賭徒身懷 $V_0$ 元全身資產 興致勃勃的 參與 某 投擲銅板 賭局,若銅板出現正面,則賭徒可贏得 $1$ 元,反之若出現反面則 賭徒輸掉 $1$元。且每次投擲銅板之間彼此互為獨立,現在給定 銅板出現正面機率為 $p$ 則反面出現的機率為 $1-p$ 並且 定義隨機變數 $X_k$表示 第 $k$ 次 投擲銅板,若銅板出現正面 我們記做 $X_k = 1$ 反之則記做 $X_k = -1$。

試問 (a) 賭徒在 第 $k$ 次 投擲銅板 的獲利期望值為何 $E[X_k]=?$
(b) 令第 $k$ 次賭注為 $B_k$ $(k=1,...,n)$,試問累計到 $n$ 次投擲銅板時 的獲利期望值為何 $E[V_n]=?$

Solution
(a) 第 $k$ 次 投擲銅板 的獲利期望值 由定義可知
\[\begin{array}{l}
E\left[ {{X_k}} \right] = 1 \cdot P\left( {{X_k} = 1} \right) + \left( { - 1} \right) \cdot P\left( {{X_k} =  - 1} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}\;
\end{array} = 1 \cdot p + \left( { - 1} \right) \cdot \left( {1 - p} \right) = 2p - 1
\end{array}\]
(b) 對 $k=1,2,...$ 我們有 $V_k = V_{k-1} + X_kB_k $ 故
\[{V_n} = {V_0} + \sum\limits_{k = 1}^n {B_k}{X_k}
\]現在對上式取期望值可得
\[\begin{array}{l}
E{V_n} = {V_0} + \sum\limits_{k = 1}^n E [{B_k}{X_k}]\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {V_0} + \sum\limits_{k = 1}^n {E[{B_k}]E[{X_k}]} \ \ \ \ \ (*) \\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {V_0} + \sum\limits_{k = 1}^n {\left( {2p - 1} \right)E[{B_k}]}
\end{array}\]

Comments:
1. 注意到若 $2 p -1 >0$ 則表示第 $k$ 次 投擲銅板賭局的 獲利的期望值為正 ($EX_k >0$)。
2. 式 $(*)$ 中利用了 $B_k$ 與 $X_k$ 的獨立性 (儘管 $B_k$ 與 $X_{k-1}$ 有關 )。


有了以上想法我們開始檢驗以下幾種策略。假設你已知此投擲銅板的賭局的一個 "內線"消息,也就是此銅板是不公平的銅板,其出現正面的機率為 $p > \frac{1}{2}$ ,若你是賭徒試問應如何建構必勝法?

===============
策略 A: 既然已知出現正面機率較高,應該一次就押注全部的錢就對了。
===============
ANS: 若採用此策略,不難想像如果這位賭徒運氣不佳,前面好幾次都連續出現 反面,則 賭徒如果採用此全部押注的策略,只要出現一次反面就會輸個精光。且如果你說運氣很好 比如說此賭徒連贏 $n$ 次機率 為 $p^n $ 且 $0 < p < 1$ 故現在若 $n \to \infty$ 可想而知 賭徒連續贏無窮次的機率為 $0$ almost surely,亦即此賭徒必定破產。

對於 策略A 的結論如下:
只要輸一次賭徒就破產,且長期而言 ($n \to \infty$ ) 賭徒連贏的機率是 $0$,故若將全部資金投入賭局絕非必勝法。


故此很明顯我們該採取 將資金分批賭,那麼該如何分配這些資金才能 最大化賭徒贏錢的機會? 或者說 創造某種必勝法呢?

===============
策略 B: Martingale ! 每輸一次就加倍賭金。
===============
ANS: 此法看似必勝法事實上要求賭徒具備無窮資本。相關細節請讀者參閱本 BLOG 相關 Martingale 理論的介紹。


===============
策略 C: 利用 Kelly criterion 幫助我們決定每次賭注金的金額,使得長期而言,賭徒可贏得最大化 Geometric mean 收益。
===============

Kelly 定義 賭徒 參與第 $N$ 次賭局的資金 長期成長率 $G$ 為
\[G: = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}{\log _2}\left( {\frac{{{V_N}}}{{{V_0}}}} \right)\] 其中 $V_N$ 為 $N$ 次賭局後賭徒的手上的資金,$V_0$ 為 賭徒的初始資金。(NOTE: 我們在此將成長率定為 $\log_2$ 是依照 Kelly 1956 原文,事實上亦可直接訂為 $\ln(\cdot)$)

由於賭徒事先知道一個 "內線"消息,也就是此銅板是不公平的銅板,其出現正面的機率為 $p > \frac{1}{2}$ ,且此時賭徒只考慮投注比率為 $K$ ,而 $W$ 與 $L$ 各自代表贏得賭局 或者 輸掉賭局的次數,那麼考慮  $N$ 次賭局之後 (注意 $W + L = N$),賭徒剩餘資金可表示為
\[
V_N = (1 + K)^W(1 - K)^L V_0
\]且賭徒資金成長率 $G$ 亦可計算如下
\[\begin{array}{l}
G = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}{\log _2}\left( {\frac{{{V_N}}}{{{V_0}}}} \right)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}{\log _2}\left( {\frac{{{{(1 + K)}^W}{{(1 - K)}^L}{V_0}}}{{{V_0}}}} \right)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}{\log _2}\left( {{{(1 + K)}^W}{{(1 - K)}^L}} \right)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\left[ {W{{\log }_2}(1 + K) + L{{\log }_2}(1 - K)} \right]\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \mathop {\lim }\limits_{N \to \infty } \left[ {\frac{W}{N}{{\log }_2}(1 + K) + \frac{L}{N}{{\log }_2}(1 - K)} \right]\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = p{\log _2}(1 + K) + \left( {1 - p} \right){\log _2}(1 - K)
\end{array}\]注意到上式 $-G$ 為 convex function of $K$,故可對其求解最佳 $K$ 值 (透過一階必要條件 $dG/dK =0$ )可得
\[\begin{array}{l}
\frac{{dG}}{{dK}} = 0\\
 \Rightarrow  - \frac{{1 - p}}{{\left( {1 - K} \right)\log \left[ 2 \right]}} + \frac{p}{{\left( {1 + K} \right)\log \left[ 2 \right]}} = 0\\
 \Rightarrow K = 2p - 1
\end{array}\]亦即 Kelly criterion 指出 若賭徒每次都以 $K = 2p-1$ 比率的賭金進行賭局,則可以最大化 Geometric mean 報酬率。且賭金成長率的最大值 $G_{max}$ 如下
\[\begin{array}{l}
{G_{\max }} = {\left. G \right|_{K = 2p - 1}} = p{\log _2}(2p) + \left( {1 - p} \right){\log _2}(2 - 2p)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = p\left[ {{{\log }_2}(2) + {{\log }_2}(p)} \right] + \left( {1 - p} \right)\left[ {{{\log }_2}2 + {{\log }_2}(1 - p)} \right]\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = 1 + p{\log _2}(p) + \left( {1 - p} \right){\log _2}(1 - p)
\end{array}\]

故以前例而言,若已知 $p = 0.55$ (因為已知小道消息幫助我們確認正面出現機率較高) 且賭徒身上帶著 $V_0$ 元作為賭本, 則 每次賭注金 應為 $(2 p - 1) V_0 = 0.1 V_0$ 亦即每次下注 $10 \%$。
Comments
以前述討論為例,若賭徒每次下注都低於 $10 \%$,則長期而言賭徒仍會持續勝利,但是獲利的成長率會較 每次都下注 $10 \%$ 來的慢 (因為非最佳解)。


上述的結果可以進一步推廣如下:首先引入 賠率 (賠率 := 贏的金額 / 輸的金額 );比如說下注金 $2$元,若賭贏則贏得 $4$ 元,賭輸則輸掉 $2$ 元。則此時賠率為 $4/2 = 2$ 。

Generalization of Kelly formula for Uneven payoff game  (1984, Thorp)
若已知賠率 $B$ 與獲勝機率 $p >0$ 且 $(B+1)p-1 >0$,則前述的 Kelly formula 可修正為
\[
K = \frac{(B + 1)p - 1} {B}
\] 上述結果來自於對下式最大化:
\[
\max_K G(K)
\]其中 $G(K) = p\ln \left( {1 + BK} \right) + \left( {1 - p} \right)\ln \left( {1 - K} \right)$

Example: 考慮賠率為 $B = 2$ 且 $p = 0.55$ 則 ,每次的最佳下注金比率應為
\[K = \frac{{(B + 1)p - 1}}{B} = \frac{{(2 + 1)\left( {0.55} \right) - 1}}{2} = 0.325
\]

Comment:
1. 事實上,讀者可以在文獻中找到更保守的投資方法,稱為 Half-Kelly (or fractiaonal-Kelly),一類常見的做法是限定 $ K^\star := 1/2 K^*$ 其中 $K^*$ 為 Kelly 最佳解。但不論是 Kelly 或者 Half-Kelly,此法則都還是有相當大的限制與問題:首先是 當賭徒把最佳解調降來得到 frctional-Kelly optimum 本身便相當具有爭議,此作法大概可以說成是把最佳化方法丟掉然後隨便亂調一個夠小的 Kelly optimum 並聲稱此解仍為最佳,既然如此何必費工做最佳化呢? 再者, Kelly Criterion 所求得的最佳比率 $K^*$ 儘管 "長期" 而言能最大化成長率,但不保證有限期間的績效,也就是說很有可能在有限期間透過 $K^*$ 去投資的 sampled path 仍會發生在某時刻大幅度資產減少 (亦即 會有極為巨大的 最大跌幅 (Max Drawdown) ),在 [4] 中我們證明就算是最基本的投擲銅板的情況,其 期望的最大跌幅仍超過 50% 以上。此現象在許多文獻中都被提及,一般將此性質稱為 Kelly optimum 具有過度投資的特性 (或稱 Kelly Criterion 是 too aggressive)。

2. 許多文獻試圖應用 Kelly Criterion 到股票市場之中,但實際應用上仍有非常多的限制,比如說有部分文獻透過 Talyor Approximation method 來求解最佳比率 $K^*$ 而無視 凱莉問題本質上是 concave program, 此類近似法可以給出漂亮的解析解並且看似合理,但其實仍潛藏諸多限制與謬誤。有興趣的讀者可參考個人的著作 [4].

3. 應用 Kelly Criterion 到股票市場有另外一類更嚴重的問題:回憶若 Kelly Criterion 應用在賭局情況,則賭徒大可假設 報酬的機率分佈已知,但是股票市場的機率分佈是完全未知,連最基本的 i.i.d. 或者 stationarity 報酬假設都僅只有在交易時間不長的情況下成立。有興趣的讀者在查閱相關文獻不難發現若貿然應用 Kelly Criterion 並透過模擬方式宣稱回測結果幾乎都無可避免上述的嚴重謬誤。


ref:
[1] Kelly, J. L., A New Interpretation of Information Rate," Bell System Technical Journal, 1956
[2] Thorp, E. O., "The Mathematics of Gambling," Lyle Stuart, Secaucus,NJ. 1984
[3] Thorp, E. O., The Kelly Criterion in Blackjack Sports Betting, and The Stock Market, 2007
[4] Hsieh, C.H., and Barmish, B. R., "On Kelly Betting: Some Limitations,"  Proceedings of 53rd Annual Allerton Conference, pp. 165-172, Monticello, IL., 2015