電子信箱 service [at] bituzi.com
幣圖誌首頁 facebook粉絲團 google plus google plus

賽馬賭局賭的好,資料壓縮壓的巧--論賽馬與編碼!


你很難想像,賽馬賭局與資料壓縮竟然息息相關? 資訊理論大師Thomas M. Cover (1938~2012)在其著作中說明了這件事:

“A GOOD Gambler is also a GOOD Data Compressor!”

考慮n匹馬競賽,哪匹馬會得到冠軍? 若每匹馬都有各自的賠率,這樣的賭局該如何分配資金比例下注長期下來會獲得最大報酬? Kelly針對這樣的問題已給出最佳解法,即按照每匹馬奪冠的機率進行資金比例分配,稱為比例賭法 (Proportional Gambling)。熟習凱利法則(Kelly criterion) 的朋友可發現,其實這就是銅版賭局的變形。
 然而,Kelly考慮的是可以玩無限多次條件下,如何讓資產成長最大化的投資方式。可惜人生是有限的,賭局當然不可能玩無限多次。在玩有限次的情況下,輸贏分佈比例可能會與當初 "你以為的機率分佈" 有所落差,使得就算用了 "你以為的最佳下注比例",也沒有賺到 "你以為該賺的錢" !

Cover 針對這個問題給了一些有趣的結果。首先針對賭局與賭客的賭法定義Doubling Rate函數 W(b,p),其中b為賭客將資金下注在每匹馬的比例,或者b亦可解釋為賭客認為每匹馬得冠軍的機率,p為每匹馬實際得冠軍的機率(這件事情只有事後才會知道)W(b,p)計算的其實就是在下注b,實際勝率為p的情況下,賭客對數報酬率的期望值 (Expected Log-return)Cover推導出一個有趣的結果,事實上W(b,p)可表示為:

W(b,p) = D(p||r) – D(p||b)

其中r為每匹馬賠率相對應的公平機率,或著可解釋為市場莊家認為的機率,D為相對熵(relative entropy),用來衡量兩個分佈之間的距離。可以觀察到的是,如果賭客認為的機率與實際馬匹得到冠軍的機率很接近,則後項D(p||b)會很小。甚至若p=b,則D(p||b)=0W(b,p)會有最大值D(p||r)。這意味著賭客估計勝率越貼近真實的話,可獲得越大利潤;當賭客認為的機率與實際輸贏的機率一樣,便是最佳下注比例可獲得的最大對數報酬D(p||r)

可以觀察到,如果莊家給的馬匹賠率都一樣,共有m匹馬,也就是r=1/m,則可推導出Doubling RateEntropy Rate的和為不變量 W*(p) + H(p) = log(m)。其中H(p)為真實機率分佈pentropy()。不難看出真實機率分佈的entropy越低,這樣的賭局越有利可圖。這也很合理,想像一下是一枚公正的銅板好預測 (entropy),還是一枚人頭機率80%,數字機率20%銅板(entropy)好預測? 在給定均勻賠率的條件下,自然是越好預測越有利可圖!

那這跟資料壓縮有什麼關係呢? Cover已經證明賽馬賭局要賭的好,賭客必須對每匹馬拿冠軍的機率估計得準確,這關係到賭客該如何下注以求取期望獲利最大化。一樣的,在編碼理論來說,有一種方式稱為熵編碼 (Entropy Encoding)。熵編碼必須針對字母出現的頻率進行估計。簡單的說,頻率出現越高的,允許用越短的編碼去表示;頻率出現越低的,可以用比較長的編碼去表示,如此便能達到確實的資料壓縮效果。因此,若字母機率分佈估計得越準確,則越可獲得接近最佳壓縮的編碼效果,算術編碼(arithmetic coding)即為一例。

Cover將這兩件事作連結了! 預估字母出現的頻率 對應到 預估馬匹冠軍的機率。而透過Cover的演算法,證明賭局的獲利取決於預估馬匹冠軍的機率,資料壓縮的好壞取決於預估字母出現的頻率。也就是說若有能力預估準確的馬匹冠軍,便有能力預估字母出現頻率。也就是賽馬賺越多,資料壓縮比例約好。

此文參考 Elements of Information Theory: Chapter 6, GAMBLING and DATA COMPRESSION


0 意見: