跳到主要內容

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

留言

這個網誌中的熱門文章

[數學分析] 什麼是若且唯若 "if and only if"

數學上的 if and only if  ( 此文不討論邏輯學中的 if and only if,只討論數學上的 if and only if。) 中文翻譯叫做  若且唯若 (or 當且僅當) , 記得當初剛接觸這個詞彙的時候,我是完全不明白到底是甚麼意思,查了翻譯也是愛莫能助,畢竟有翻跟沒翻一樣,都是有看沒有懂。 在數學上如果看到 if and only if  這類的句子,其實是表示一種 雙條件句 ,通常可以直接將其視為" 定義(Definition)" 待之,今天要分享的是這樣的一個句子如何用比較直觀的方法去看他 假設我們現在有 兩個邏輯陳述句 A 與  B. 注意到,在此我們不必考慮這兩個陳述句到底是什麼,想表達什麼,或者到底是否為真(true),這些都不重要。只要知道是兩個陳述即可。 現在,考慮新的陳述:  "A if and only if B" 好了,現在主角登場,我們可以怎麼看待這個句子呢? 事實上我們可以很直覺的把這句子拆成兩部分看待,也就是 "( A if B ) and ( A only if B )" 那麼先針對第一個部分  A if B  來看, 其實這句就是說  if B then A, 更直白一點就是 "if B is true, then A is also true".  在數學上等價可以寫為 "B implies A" .  或者更常用一個箭頭符號來表示 "B $\Rightarrow$  A"  現在針對第二個部分  A only if B 此句意指  "If B is not true, then A is also not true". 所以如果已知 A is true,  那麼按照上句不難推得 B is also true 也就是說  A only if B  等價為 "If A is true then B is also true". 同樣,也可以寫作   "A implies B"   或者用箭頭表示  "A   $\Rightarrow$     B".

[數學分析] 淺談各種基本範數 (Norm)

這次要介紹的是數學上一個重要的概念: Norm: 一般翻譯成 範數 (在英語中 norm 有規範的意思,比如我們說normalization就是把某種東西/物品/事件 做 正規化,也就是加上規範使其正常化),不過個人認為其實翻譯成 範數 也是看不懂的...這邊建議把 Norm 想成長度就好 (事實上norm是長度的抽象推廣), 也許讀者會認為好端端的長度不用,為何又要發明一個 norm 來自討苦吃?? 既抽象又艱澀。 事實上想法是這樣的: 比如說現在想要比較兩個數字 $3$ , $5$ 之間的大小,則我們可以馬上知道 $ 3 < 5 $;同樣的,如果再考慮小數與無理數如 $1.8753$ 與 $\pi$,我們仍然可以比較大小 $1.8753 < \pi = 3.1415...$ 故可以發現我們有辦法對 "純量" 做明確的比大小,WHY? 因為前述例子中 $3$, $5$, $1.8753$ or $\pi$ 其各自的大小有辦法被 "measure "! 但是如果是現在考慮的是一組數字 我們如何去measure 其大小呢?? 比如說 \[x:=[1, -2, 0.1, 0 ]^T \]上式的大小該是多少? 是 $1$? $-2$? $0.1$??? 再者如果更過分一點,我們考慮一個矩陣 \[A = \left[ {\begin{array}{*{20}{c}} 1&2\\ 3&4 \end{array}} \right] \],想要知道這個矩陣的大小又該怎麼辦?? 是 $1$ ? $2$ 還是 $4$ ?..其實現階段我們說不清楚。 也正是如此,可以發現我們確實需要新的 "長度" 的定義來幫助我們如何去 measure 矩陣/向量/甚至是函數的大小。 故此,我們首先定義甚麼是Norm,(也就是把 "長度" or "大小" 的本質抽離出來) ================== Definition: Norm 考慮 $V$ 為一個向量空間(Vector space),則我們說  Norm 為一個函數 $||\cdot|| : V \rightarrow \mathbb{R}$ 且滿足下列性質