朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

洛奇绵羊问题

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)\) 的显式表达式来是很难的,但是用计算机算出 \(V\) 在任一点的值是可以很快办到的。可以证明

\[\lim_{k\to\infty}V(k,k)-(2k+\frac{\pi}{4}-\sqrt{\pi k})=0.\] 因此如果开始有黑绵羊白绵羊各 10000 只,则策略 \(A\) 下黑绵羊的期望数目大约是 19824 只。