殷勤昨夜三更雨 又得浮生一日凉

洛奇绵羊问题

赵亮 / 2011-04-08


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

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

问题是这样的:

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

洛奇绵羊问题出自 Willianms 的教材 "Probability wth 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)\) 是一个常数,常数的期望等于自身。

我们的策略 \(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 给出的估计不太放心,于是利用书中给出的递推关系写了一个小程序验证了一下:

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 给出的渐进公式当做准确的解来使用!

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


更新: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\)。并且将递推关系变形后有

\[\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},\]

此即为结论。