6.1 The Horse Rase

设赛马中有m匹马，第$i$只马赢的概率$p_{i}$，如果它赢了，那么payoff就是$o_{i}:1$的。意思是，每投资这匹马1元，这匹马胜利时就能获得$o_{i}$元，否则获得0元。
有两种方式描述赔率：a for 1和b to 1。

• a-for-1: 赛前赌徒投入1元，赢了收回a元，否则收回0元；
• b-to-1: 赛前进行打赌，赛后如果赌赢了获得b元，赌输了交出1元。
  从上面可以得出a-for-1 等价于 b-to-1，如果$b=a-1$
  我们假设赌徒选择将自己的财富分布在多匹马上。设分在第i号马上的比例是$b_{i}=b(i)$，有$\sum_{i}b_{i}=1,b_{i}\geq 0$。如果赌赢了就能收回$o_{i}$倍的投入，所有其他赌注会被失去。
  最后的财富是一个随机变量，而且赌徒希望能最大化他的收益。一种方式是只在$p_{i}o_{i}$最大的那一匹马上压上全部赌注，但这样也有很大的风险，因为很可能会失去所有钱。

赌徒可以重复投资，因此他的财富是每次赌注结果之积。令$S_{n}$是$n$场比赛之后赌徒的财富，于是

$$S_{n} = \prod_{i=1}^n S(X_{i})$$

where $S(X)=b(X)o(X)$ is the factor by which the gambler's wealth is multiplied when horse $X$ wins.

[!theorem] 定义(doubling rate):
一场赛马的doubling rate定义为
$$
W(\mathbf{b},\mathbf{p}) = E(\log S(X)) = \sum_{k=1}^m p_{k} \log b_{k}o_{k}
$$

The definition of doubling rate is justified by the following theorem:

[!theorem] Theorem 6.1.1
令赛马结果$X_{1},X_{2},\dots,X_{n}$ 是服从$p(x)$的独立同分布的变量，那么赌徒使用策略$\mathbf{b}$时的财富以 doubling rate $W(\mathbf{b},\mathbf{p})$指数增长，即
$$
S(n) \doteq 2^{nW(\mathbf{b},\mathbf{p})}
$$

[!Proof] Proof
Functions of independent random variables are also independent, and hence $\log(S(X_{1})),\log(S(X_{2})),\dots$ are i.i.d. , then
$$
\frac{1}{n} \log S_{n} = \frac{1}{n} \sum_{i=1}^n \log S(X_{i}) \to E(\log S(X))\qquad \text{in probability}

$$thus$$

S_{n} \doteq 2^{nW(\mathbf{b},\mathbf{p})}

$$

定义Maximum doubling rate是所有策略中最大的那个：

$$W^* (\mathbf{p}) = \max _{\mathbf{b}}W(\mathbf{b},\mathbf{p}) = \max _{\mathbf{b}:b_{i}\geq 0,\sum_{i}b_{i}= 1} \sum_{i=1}^m p_{i} \log b_{i} o_{i}$$

使用拉格朗日乘子法。

$$J(\mathbf{b} ) = \sum p_{i}\log b_{i} o_{i} + \lambda \sum b_{i}$$

对$b_{i}$求偏导等于0，得到$b_{i} = -\frac{p_{i}}{\lambda}$，进而得到$\lambda = -1,b_{i}=p_{i}$
于是进一步得到max doubling rate为：

[!theorem] Theorem 6.1.2
最优的doubling rate由下式给出：
$$
W^(\mathbf{p}) = \sum_{i}p_{i}\log o_{i} -H(\mathbf{p})
$$
在$\mathbf{b}^=\mathbf{p}$时取得

于是，我们说明了在赌徒可以重新投资，且不保留财富为现金的情形下，最优的策略是proportional betting.

We now consider a special case when the odds are fair with respect to some distribution, i.e. there is no track take and $\sum_{i} \frac{1}{o_{i}} = 1$.
记$r_{i} = \frac{1}{o_{i}}$，则$r_{i}$也可以看作马编号上的一个概率分布（也叫bookie's estimate）。
于是doubling rate重写成

$$W(\mathbf{b},\mathbf{p}) = D(\mathbf{p}\mid \mid \mathbf{r}) - D(\mathbf{p}\mid\mid \mathbf{b})$$

对于一个更特殊的情形，所有赔率均为m-for-1，此时

$$W^* (\mathbf{p}) = D\left( \mathbf{p}\mid\mid \frac{1}{m} \right) = \log m - H(\mathbf{ p})$$

从此例中，我们可清晰地看到数据压缩和doubling rate的对偶性：

[!theorem] Theorem 6.1.3(Conservation theorem):
对于均一公平的赔率，有
$$
W^*(\mathbf{p}) + H(\mathbf{p}) = \log m
$$

假设赌徒可以保留一部分钱。令$b(0)$是保留的钱比例，其他的$b(1)\dots b(m)$均为投入到各个编号的马上的钱比例。于是比赛结束前后财富的比例系数为

$$S(X) = b(0)+b(X) o(X)$$

考虑三种子情形：

1. 公平赔率：$\sum_{i} \frac{1}{o_{i}}= 1$.此时保留现金的选项不影响分析.这是因为我们可以通过取$b_{i} = \frac{1}{o_{i}}$的投注来实现保留现金。因为无论哪个马赢了，均有$S(X)=1$。此时按比例投注依然是最优的。
2. Superfair odds(超公平赔率): $\sum_{i} \frac{1}{o_{i}} < 1$。此时赔率情形比第一种还要好，所以参与者期望将现金全部投入，此时最优解依然是proportional betting.不过，我们而可以选择$\mathbf{b} = \frac{1}{o_{i}}$使得它形成一个"Dutch book"(In a Dutch book, an opponent can choose a portfolio of bets such that he is assured of winning money)，得到$o_{i}b_{i} =1$，无论哪匹马赢了。在这种分配下，$1-\sum_{i}\frac{1}{o_{i}}$被保留，使得在比赛结束后，必然能得到$1+ (1-\sum_{i} \frac{1}{o_{i}}) > 1$比例的现金。尽管这种方法没有风险，但这并不是doubling rate最高的策略。
3. Subfair odds: $\sum_{i} \frac{1}{o_{i}}>1$,这是最符合实际的情形。庄家要在每次比赛的赌注中抽一些分成。这时，通常会保留一些资产，只将部分钱投入。按比例全部投入的策略不再是log-optimal的

6.2 Gambling and Side Information

假设赌徒有一些关于比赛结果的信息。例如，赌徒可能知道一些之前场次的比赛结果。那么这些信息有多大价值呢？
可以通过财富增长的比例系数的变大 来衡量这种类型信息的价值。现在我们来看看共同信息和doubling rate之间的关系。
令$X=\{1,2,\dots,m\}$为比赛结果，概率$p(x)$,赔率$o(x)$对1，令$(X,Y)$的联合分布为$p(x,y)$，令已知y条件下的决策$b(x\mid y)\geq 0,\sum_{x}b(x\mid y)=1$。$b(x\mid y)$就是当观察到y时该策略在x号马上压下的赌注。y未知时的决策记为$b(x)$,且$b(x)\geq 0,\sum_{x}b(x)=1$
令unconditional 和conditional doubling rates为：

$$\begin{align} W^*(X) = \max _{\mathbf{b}(x)} \sum_{x}p(x)\log b(x)o(x) \\ W^*(X,\mid Y) = \max _{\mathbf{b}(x\mid y)} \sum_{x,y}p(x,y) \log b(x\mid y)o(x) \end{align}$$

[!theorem] Theorem 6.2.1

$$\Delta W = W^*(X\mid Y)-W^*(X)$$

[!Proof] Proof
$$
\begin{align}
W^(X\mid Y) &= \max {b} \sum{x,y} p(y) (D( p(x\mid y)\mid\mid o(x)) - D(p(x\mid y) \mid\mid b(x\mid y))) = \sum_{y} p(y) D(p(x\mid y)\mid\mid o(x)) \
W^(X)& = D(p(x)\mid\mid o(x)) \
W^(X\mid Y)- W^(X) &= \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)} = I(X;Y)
\end{align}
$$
;

6.3 Dependent Horse Races and Entropy Rate

赛马中最常见的side info就是这些马过去的表现了。如果每次赛马是独立的，那么该信息无用。如果我们假设每场比赛之间存在关联，那么我们可以根据过去的表现计算下一场的策略，从而得到有效的doubling rate
假设$\{X_{k}\}$序列构成随机过程，令每场比赛的策略取决于之前比赛的结果。那么在这种情况下，最佳doubling rate是(假设赔率均为uniform fair的，也就是m赔1)

$$\begin{align} W^*(X_{k}\mid X_{k-1},\dots,X_{1}) &= E\left[ \max _{b(\cdot\mid X_{k-1},\dots,X_{1})} E[\log S(X_{k}\mid X_{k-1},\dots,X_{1})]\right] \\ & = \log m - H(X_{k}\mid X_{k-1},\dots,X_{1}) \end{align}$$

这在$b^*(x_{k}\mid x_{k-1},\dots,x_{1}) = p(x_{k}\mid x_{k-1},\dots,x_{1})$达到极大。
n场比赛后，赌徒的财富为

$$S_{n} = \prod_{i=1}^n S(X_{i})$$

增长率指数为（假设m for 1）

$$\begin{align} \frac{1}{n} E \log S_{n} & = \sum E \log S(X_{i}) \\ & = \frac{1}{n} \sum (\log m - H(X_{i}\mid X_{i-1},\dots,X_{1})) \\ & = \log m - \frac{H(X_{1},X_{2},\dots,X_{n})}{n} \end{align}$$

对于有熵率$H(\mathscr{H})$的定态过程，上式极限给出$\lim_{ n \to \infty } \frac{1}{n}E \log S_{n} +H(\mathscr{H}) = \log m$

对于ergodic process，$S_{n}\doteq 2^{nW}$ with probability 1
![[第四章 Entropy Rates of Markov Process#^4a9bc6]]

其中$W = \log m - H(\mathscr{H})$

6.5 Data Compression and Gambling

下面将证明，赌博和数据压缩具有直接的联系。一个好的赌徒也是一个好的数据压缩器。
这种想法是基于如下事实：赌徒会准确预测概率分布并基于这种估计下注。令$X_{1},\dots,X_{n}$是一系列我们想压缩的随机变量。不失一般性，我们假设这些变量都是0-1取值的。在这个序列上赌博被定义为做决策（赌注）：

$$b(x_{k+1}\mid x_{1},x_{2},\dots,x_{n}) \geq 0,\qquad \sum_{x_{k+1}} b(x_{k+1}\mid x_{1},x_{2},\dots,x_{k}) = 1$$

其中$b(x_{k+1}\mid x_{1},x_{2},\dots,x_{n})$是基于之前观测到的$x_{1},\dots x_{n}$下注在$x_{k+1}$上的钱的比例。设赌注回报率相同(2-for-1)，于是序列末尾的$S_{n}$是

$$S_{n} = 2^n \prod_{k=1}^n b(x_{k+1}\mid x_{1},x_{2},\dots,x_{n}) = 2^n b(x_{1},\dots,x_{n})$$

下面我们证明更高的$S_{n}$意味着更有效的数据压缩。换言之，如果问题中的结果给出wealth $S_{n}$,那么通过压缩策略可以保存$\log S_{n}$bits

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview