凱利公式——A New Interpretation of Information Rate

04-14

凱利公式是J. L. Kelly 在論文《A New Interpretation of Information Rate 》中提出的，這篇論文的目的是計算在不使用編碼的情況下有雜訊的信道的信息傳遞速率。

凱利認為度量這個信息速率的損失函數應該能夠衡量接收到的信息的價值，其中信息最直觀的一種價值就是在賭局中。假設有兩個勢均力敵的棒球隊進行N次比賽，一個賭徒可以通過某個信道獲取這N次比賽的結果。他可以在賭場中下注，對於每一場比賽，押中贏的隊伍可以獲得下注的雙倍的錢，否則會損失下注的資金。

假設這個賭徒獲取的所有數據都是正確的，那麼他最優的選擇是每次都押上自己全部的資金。經過N輪之後，他的資金是原來的 $2^N$ 倍。我們用一個指標G來衡量這個賭徒資本的指數增長率：

$G = lim_{N o infty }frac{1}{N} logfrac{V_N}{V_0}$

這裡的 $V_0$ 是賭徒的初始資金， $V_N$ 是賭徒經過N輪賭局之後的資金。

接下來考慮賭徒拿到的數據是有雜訊的情況，假設他拿到的數據有p的比率是錯誤的，有q的比率是正確的(q = 1 - p)。他仍可以每次都把他所有的資金都用來下注，事實上，這是使他資金期望最大的選擇(maximize $E[V_N]$ )。這種情況下：

$E[V_N] = (2q)^NV_0$

但是在這種情況下他只要在任何一局中輸掉，他就損失了所有的資金。如果p > 0, 並且他進行足夠多的賭局，他一定會輸掉他所有的錢。我們換一種思路，如果他每次拿出 $ell$ 比例的資金下注，假設他在N輪賭博中贏了W次，輸了L次，那麼經過N輪賭博他的資金為：

$V_N = ( 1 + ell)^W(1 - ell)^LV_0$

這時： $G = lim_{N o infty} frac{1}{N}(logfrac{(1 + ell)^W(1 - ell)^LV_0}{V_0} ) = lim_{N o infty} frac{1}{N}(W log(1 + ell) + L log(1 - ell))$

根據大數定律：

$G = q log(1 + ell) + p log(1 - ell))$

為了使G最大化，我們可以計算：

$frac{dG}{d ell} = q frac{1}{1 + ell} - p frac{1}{1 - ell}$

令 $frac{dG}{d ell}$ 為0得：

$q frac{1}{1 + ell} = p frac{1}{1 - ell}$

即

$ell = frac{q - p}{q + p} = 2q - 1$

此時：

$G_{max} = 1 + q log(q) + p log(p))$