你很難想像，賽馬賭局與資料壓縮竟然息息相關? 資訊理論大師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)=0，W(b,p)會有最大值D(p||r)。這意味著賭客估計勝率越貼近真實的話，可獲得越大利潤；當賭客認為的機率與實際輸贏的機率一樣，便是最佳下注比例可獲得的最大對數報酬D(p||r)。
可以觀察到，如果莊家給的馬匹賠率都一樣，共有m匹馬，也就是r=1/m，則可推導出Doubling Rate與Entropy Rate的和為不變量 W*(p) + H(p)
= log(m)。其中H(p)為真實機率分佈p的entropy(熵)。不難看出真實機率分佈的entropy越低，這樣的賭局越有利可圖。這也很合理，想像一下是一枚公正的銅板好預測 (entropy高)，還是一枚人頭機率80%，數字機率20%銅板(entropy低)好預測? 在給定均勻賠率的條件下，自然是越好預測越有利可圖!
那這跟資料壓縮有什麼關係呢? Cover已經證明賽馬賭局要賭的好，賭客必須對每匹馬拿冠軍的機率估計得準確，這關係到賭客該如何下注以求取期望獲利最大化。一樣的，在編碼理論來說，有一種方式稱為熵編碼 (Entropy Encoding)。熵編碼必須針對字母出現的頻率進行估計。簡單的說，頻率出現越高的，允許用越短的編碼去表示；頻率出現越低的，可以用比較長的編碼去表示，如此便能達到確實的資料壓縮效果。因此，若字母機率分佈估計得越準確，則越可獲得接近最佳壓縮的編碼效果，算術編碼(arithmetic coding)即為一例。
Cover將這兩件事作連結了! 預估字母出現的頻率 對應到 預估馬匹冠軍的機率。而透過Cover的演算法，證明賭局的獲利取決於預估馬匹冠軍的機率，資料壓縮的好壞取決於預估字母出現的頻率。也就是說若有能力預估準確的馬匹冠軍，便有能力預估字母出現頻率。也就是賽馬賺越多，資料壓縮比例約好。
此文參考 Elements of Information Theory: Chapter
6, GAMBLING and DATA COMPRESSION
0 意見:
張貼留言