洛奇绵羊问题

我们的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段:

一个男孩来到了一个美丽的山谷,有一条小河在谷中流淌。他看到河一边的草地上有一群黑绵羊,另一边的草地上有一群白绵羊。羊群被施以一种魔法:每个时刻都恰有一只绵羊发出咩咩的叫声。如果发出叫声的是白绵羊,就会有一只黑绵羊趟过小河跑过来并且变成白绵羊;如果发出叫声的是黑绵羊,则会有一只白绵羊趟过小河跑过去并且变成黑绵羊。每个时刻发出叫声的绵羊是完全随机的,整个过程没有绵羊出生或者死亡,一直持续到所有绵羊都变成同一种颜色为止。

问题是这样的:

问题:如果男孩可以选择在初始时刻 \(0\),或者是每个魔法时刻 \(1,2,\ldots\) 结束后将任意数量的白绵羊赶出山谷,那么为了最终得到尽可能多的黑绵羊,他应该采取怎样的策略?

洛奇绵羊问题出自 Willianms 的教材 Probability with Martingales,是一个很有趣的问题。这种在随机的环境中施加一个控制的力,以最大化期望收益的问题属于随机控制的范畴。

首先说明不论男孩采取怎样的策略,最终羊群都会以概率 1 全部变成同一种颜色。

\(\Omega=\{ (w,b)\in\mathbb{Z}_{\geq0}\times\mathbb{Z}_{\geq0}\}\) 是羊群所有可能的状态组成的集合,其中 \(w\)\(b\) 分别表示白绵羊和黑绵羊的数目。男孩采取的一个策略 \(S\) 就是从一个状态 \((w,b)\) 移动到另一个状态 \((w',b')\) 的规则:根据当前 \((w,b)\) 的值,男孩决定到底是按兵不动 (不做任何干预),还是赶走 \(c\) 只白绵羊,把状态 \((w,b)\) 变成状态 \((w-c,b)\),这里 \(0<c\leq w\) 是一个正整数。如果男孩始终不做任何干预的话,那么羊群状态将始终保持在线段 \[\{ x,y\ |\ x\geq0, y\geq0, x+y=w+b\}\] 上,这是一个互通的 Markov 链,因此以概率 1 撞到吸收状态 \((0,w+b)\)\((w+b,0)\),即最终变成同一种颜色。如果男孩在某个时刻移走了 \(c\) 只白绵羊,那么系统将会被强制转移到线段 \(\{ x,y\ |\ x\geq0, y\geq0, x+y=w+b-c\}\) 上,如此下去。由于男孩只能进行有限次移走绵羊的操作,可见不论男孩策略如何,羊群总是会最终变成同色的。

对任何策略 \(S\),我们用 \(V_S(w,b)\) 表示从 \((w,b)\) 状态出发,在策略 \(S\) 下最终得到的黑绵羊数量的期望值。这里 \(V_S\) 是一个由 \(S\) 决定的确定的函数,它不包含随机性。\(V_S\) 叫做策略 \(S\) 的值函数。显然 \(V_S\) 总是满足边界条件 \[V_S(0,b)=b,\quad V_S(w,0)=0.\]

假设我们能够找到这样一个策略 \(A\),它的值函数 \(V_A\) 有如下性质,那么它就是最佳策略:

最优策略的充分条件:如果策略 \(A\) 的值函数 \(V_A\) 满足如下条件:对任何初始状态 \((w,b)\) 和任何的策略 \(S\),设羊群在策略 \(S\) 下第 \(n\) 个魔法时刻结束后的状态为 \((W_n,B_n)\),序列 \(\{V_A(W_n,B_n),n=0,1,\ldots\}\) 是上鞅,则策略 \(A\) 就是最优的。

注意这里是把任一策略 \(S\) 下的状态序列 \((W_n, B_n)\) 代入策略 \(A\) 的值函数中。

其中的道理非常简单:对任何策略 \(S\),其吸收状态 \((W_\infty,B_\infty)\) 中必有一个分量是 0,从而由值函数边界条件有 \(B_\infty=V_A(W_\infty,B_\infty)\),所以 \[\mathbb{E}[B_\infty]=\mathbb{E}[V_A(W_\infty,B_\infty)]\leq \mathbb{E}[V_A(w,b)]=V_A(w,b).\] 其中最后一个等号是因为 \(V_A(w,b)\) 是一个常数,常数的期望等于自身。

在教材中,Williams 直接“猜出”了策略 \(A\)

策略 \(A\):如果当前黑绵羊的数量多于白绵羊,则什么也不做;否则就把白绵羊的数量变为黑绵羊的数量减 1。

显然 \(V_A\) 有如下性质:

  1. 边界条件 \(V_A(0,b)=b\)\(V_A(w,0)=0\)
  2. \(V_A(w,b)=V_A(w-1,b), w\geq b>0\)
  3. \(V_A(w,b)=\frac{w}{w+b}V_A(w+1,b-1)+\frac{b}{w+b}V_A(w-1,b+1)\), \(b>w>0\)

\(V_A\) 由边界条件 1 和递推关系 2, 3 完全决定。

从定义上看,关系 2 只在一半的区域上成立,而关系 3 则在另一半的区域上成立。但是花费一番功夫,我们其实可以证明它们各自的“弱形式”在整个区域上都是对的:

引理:在区域 \(\Omega\) 上,\(V_A\) 函数满足如下的不等式:

  1. \(V_A(w,b)\geq V_A(w-1,b), w>0\)
  2. \(V_A(w,b)\geq \frac{w}{w+b}V_A(w+1,b-1)+\frac{b}{w+b}V_A(w-1,b+1)\), \(w>0, b>0\)

4, 5 合起来说的就是无论男孩策略如何,\(\{ V_A(W_n,B_n)\}\) 总是一个上鞅!因此策略 \(A\) 确实是最优的。

引理的证明是纯粹的分析,过程比较繁琐,我把它留给 Williams 的教材第 15.3 节。写出 \(V(w,b)\) 的显式表达式来是很难的,Willianms 证明了 \[\lim_{k\to\infty}V(k,k)-(2k+\frac{\pi}{4}-\sqrt{\pi k})=0.\] 因此如果开始有黑、白绵羊各 10000 只,则策略 \(A\) 下黑绵羊的期望数目大约是 19824 只。

我对 Williams 给出的估计不太放心,于是用书中给出的递推关系写了一段代码验证了一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from decimal import *

pi = 3.14159265358979
getcontext().prec = 20

def solve_sheep(n):
p = [0 for _ in range(n + 1)]
v = [0 for _ in range(n + 1)]
v[1] = 1
p[1] = Decimal(0.5)
for k in range(2, n + 1):
p[k] = (1 - 1 / Decimal(2 * k)) * p[k - 1]
for k in range(1, n):
w = (1 - p[k]) / (1 + p[k])
v[k + 1] = w * v[k] + (1 - w) * (2 * k + 1)

return v[n]

def estimate_sheep(n):
return 2 * n + pi / 4 - (pi * n)**0.5

print(solve_sheep(10000))
print(estimate_sheep(10000))

递推公式给出的真实值结果是 19823.5422285701,渐进公式给出的结果是 19823.540013,好吧它们确实很接近。更令人惊奇的是,对所有的 \(n\geq1\),渐进公式与真实值的整数部分都是一样的!换言之,你完全可以把 Williams 给出的渐进公式当做准确的解来使用!这真的有点刷新我对 Stirling 公式的认知。

猜出最优策略、证明弱化的不等式、给出渐进公式,每一步都是神操作啊。


更新:Williams 的证明关键是用 \(v_k=V(k,k)\) 来表出所有的 \(V(w, b),\,b>w>0\)

\[\begin{cases}V(k-c, k+c)=v_k+(2k-v_k)a_c,\\ V(k+1-c, k+c)=v_k+(2k+1-v_k)b_c.\end{cases}\]

其中

\[\begin{cases}a_c=2^{-(2k-2)}\sum\limits_{j=k}^{k+c-1}\dbinom{2k-1}{j},\\b_c=\left(2^{2k-1}+\frac{1}{2}\dbinom{2k}{k}\right)^{-1}\sum\limits_{j=k}^{k+c-1}\dbinom{2k}{j}.\end{cases}\]

Williams 没有解释这组公式是怎么求出来的,它看起来很吓人,其实道理不复杂。我们用 \(V(k-c,k+c)\) 为例子来说明:

\(g(c) = V(k-c, k+c),0\leq c\leq k\),则 \(g(0)=v_k,\,g(k)=2k\),由前面的 3 知其满足递推关系

\[g(c) = \frac{k-c}{2k}g(c-1) + \frac{k+c}{2k}g(c+1),\quad 1\leq c \leq k-1.\]

\(h(c) = g(c) - v_k\),则 \(h(c)\) 同样满足上述递归关系,但是边界条件为 \(h(0)=0\)\(h(k)=2k-v_k\geq 0\)。进一步设 \(h'(c)=h(c) / h(k)\),则 \(h'(c)\) 也满足同样递推关系,但边界条件为 \(h'(0)=0, h'(k)=1\)。这些变换的目的是将线性递推序列的边界条件从 \(g(0)=vk,\,g(k)=2k\) 调整为 \(h'(0)=0,\,h'(k)=1\),但线性递推关系不变,从而可以方便地解出通项公式来。

由递推关系有

\[\begin{align*}h'(c+1)-h'(c) &= \frac{k-c}{k+c}(h'(c)-h'(c-1))\\&=\cdots\\&=\frac{(k-c)\cdots(k-1)}{(k+c)\cdots(k+1)}(h'(1)-h'(0))\\&=\frac{\dbinom{2k-1}{k+c}}{\dbinom{2k-1}{k}}h'(1).\end{align*}\]

于是

\[1=h'(k)=\sum\limits_{c=0}^{k-1}h'(c+1)-h'(c)=h'(1)\frac{\sum\limits_{c=0}^{k-1}\dbinom{2k-1}{k+c}}{\dbinom{2k-1}{k}}=h'(1)\dfrac{2^{2k-2}}{\dbinom{2k-1}{k}}.\]

\(h'(1)=2^{-(2k-2)}\binom{2k-1}{k}\),于是

\[h'(c) = \sum\limits_{j=0}^{c-1}\frac{\dbinom{2k-1}{k+j}}{\dbinom{2k-1}{k}}h'(1)=2^{-(2k-2)}\sum\limits_{j=k}^{k+c-1}\dbinom{2k-1}{j}.\]

由于 \(g(c)=V(k-c,k+c)\)\(h'(c)\) 之间的关系为

\[h'(c)=\frac{g(c)-v_k}{2k-v_k},\]

此即为结论。

 | 

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器