洛奇绵羊问题

2011-04-08

附录
References

今天的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段：

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

问题是这样的：

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

洛奇绵羊问题出自 (Williams 1991)，是一个很有趣的问题。这种在随机的环境中施加一个控制的力，以最大化期望收益的问题属于随机控制的范畴。

我们首先说明不论男孩采取怎样的策略，最终羊群都会以概率 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)\mid x\geq0, y\geq0, x+y=w+b\}\] 上，这是一个互通的 Markov 链，因此以概率 1 撞到吸收状态 $(0,w+b)$ 或 $(w+b,0)$，即最终变成同一种颜色。如果男孩在某个时刻移走了 $c$ 只白绵羊，那么系统将会被强制转移到线段 \[\{ (x,y)\mid 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\label{eq:boundary}\tag{$\ast$}.\]

假设我们能够找到这样一个策略 $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，从而由值函数边界条件 $(\ref{eq:boundary})$ 有 $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$ 有如下性质：

$V_A$ 的递推关系.

边界条件 $V_A(0,b)=b$，$V_A(w,0)=0$。
$V_A(w,b)=V_A(w-1,b), w\geq b>0$。
$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$ 函数满足如下的不等式：

$V_A(w,b)\geq V_A(w-1,b), w>0$。
$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)$ 的显式表达式来是很难的，Williams 证明了 \[\lim_{k\to\infty}V(k,k)-(2k+\frac{\pi}{4}-\sqrt{\pi k})=0.\label{eq:vkk}\tag{$\ast\ast$}\] 因此如果开始有黑、白绵羊各 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，准确的有点离谱啊！这真的有点刷新我对 Stirling 公式的认知。

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

附录

Williams 书中对渐进公式 $(\ref{eq:vkk})$ 的证明比较难读，我这里解释下其中的想法。关键是用对角线上的值 $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$，由前面 $V_A$ 的递推关系中的 3 知其满足递推关系

\[g(c) = \frac{k-c}{2k}g(c-1) + \frac{k+c}{2k}g(c+1),\quad 1\leq c \leq k-1.\] 这是一个 $[0,k]$ 上的递推序列，并且已知边界条件 $g(0)$ 和 $g(k)$，我们来求解这个序列。

记

\[h(c) = \frac{g(c) - g(0)}{g(k)-g(0)} = \frac{g(c) - v_k}{g(k)-v_k}.\label{eq:hc}\tag{1}\]

则 $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).\label{eq:hrec}\tag{2}\end{align}\]

利用 $(\ref{eq:hrec})$ 我们可以解出 $h(1)$ 来：

\[1=h(k)=\sum_{c=0}^{k-1}\big(h(c+1)-h(c)\big)=h(1)\frac{\sum_{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}$。再次利用 $(\ref{eq:hrec})$ 可得

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

将上式代入 $(\ref{eq:hc})$ 即得结论。

References

Williams, David. 1991. Probability with Martingales. Cambridge University Press.

上一篇：模式的等待时间与反直觉概率

下一篇：飞船空间跳跃问题