[博弈論] 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