机器猫和玩具鼠

引子

上过舒幼生老爷子课的同学应该都会对下面这道概率题印象深刻

舒老师给的标准解法是利用递归:

将所求概率记为\(P\).

猫第一步以\(\frac{1}{2}\)概率左行捉到鼠,对\(P\)的贡献为\(\frac{1}{2}\).

猫第一步以\(\frac{1}{2}\)概率右行,到达\(x=2\)位置。为捉住鼠,猫首先必须左行到\(\frac{1}{2}\)位置,这与开局时要求猫从\(x=1\)位置左行到\(x=0\)位置捉到鼠的情况相同,概率同构也为\(P\)。到达\(x=1\)位置后,游戏又回到初态,猫左行到\(x=0\)位置捉到鼠的概率仍为\(P\)。据此,猫第一步到达\(x=2\)位置,接着也能捉到鼠,对\(P\)的贡献为\(\frac{1}{2}PP\)。

综上所述,可得

\[P=\frac{1}{2}+\frac{1}{2}PP\]

即可解出\(P=1\)

很直接的一个推广就是,假定机器猫向左和向右一步的概率分别为\(q\)和\(1-q\),问此时是否还一定能抓到老鼠?

我们同样列出等式:

\[P = q + (1-q)P^2\]

不幸的是,这个二次方程有两个根:\(P = 1, q/(1-q)\)

当\(q \ge 1/2\)时,我们知道猫肯定能抓到老鼠,但是对于其他情况呢?到底是有一定的非零概率还是必然能?递归方法遇到了困难。

当然你可以谈\(q=0\)处的情况以及物理问题应有的连续性,我也可以反问\(q=1/2\)时连续性到哪去了。事实上,这种递归方法,类似于对一个连收敛性都未知的无穷级数做种种操作,期望最终能得到结果,而数学,显然不允许你这样瞎搞。

随机行走\(\cdot\)Markov过程

让我们来考虑更加一般化的问题:我们的机器猫全体可能待的位置的集合记做\(S={i,j,...}\),从给定位置\(i\)出发,下一时刻到达位置\(j\)的概率\(p_{ij}\)是一个常数。那么我们的机器猫在各个位置间来回晃动的过程被称为随机行走。如果我们将机器猫所处的每个位置都称之为一个状态,那这也可以被称为齐次Markov过程。这类过程最大的特点是,系统未来的状态只依赖于现在而不依赖于过去——机器猫才不管他是怎么到达这个地方的——或者用精准一些的符号来表达:

\[\Pr(future,past|now) = \Pr(future|now) \Pr(past|now)\]

在Markov理论中,一个基本的概念是常返性:如果从某个状态\(i\)出发,经过足够多的步骤后,一定至少回来了一次,那么这个状态被称之为常返态,否则即称之为非常返态或暂返态。对于暂返态,我们定义无穷步后至少回来一次的概率为首达概率\(f_{ii}\)

我们很容易发现常返性和猫捉老鼠问题的联系:我们假定猫一开始和玩具鼠呆在一起,觉得肚子比较胀想先散散步再开饭——额,我们假定在这个地方只能往右走——那么,玩具鼠所处位置是常返态,便等价于猫一定能回来开饭。好了,我们现在的问题转化为了如何判断一个状态是否为常返态。

常返态判定定理

回到猫捉老鼠的问题,我们研究的是无穷步后曾到达\(x=0\)的概率,换句话说,就是一减去从来没有从正整数点集走出来的概率。某些时候后面这个量更方便研究。

取\(D \subset S\),记从状态\(i \in D\)出发,\(n\)步后仍未离开\(D\)的概率为\(y_i^{(n)}\),我们很容易写出递归关系

\[
\begin{aligned}
y_i^{(0)} &= 1\\
y_i^{(n+1)} &= \sum\limits_{j \in D} p_{ij} y_j^{(n)}
\end{aligned}
\]


\[
\begin{aligned}
y_i^{(n+1)} - y_i^{(n)} &= \sum\limits_{j \in D} p_{ij}\left(y_j^{(n)}-y_j^{(n-1)}\right)\\
y_i^{(1)} - y_i^{(0)} &= y_i^{(1)} - 1 \le 0
\end{aligned}
\]

可知\(y_i^{(n)}\)随\(n\)单调不递增。

加之概率的非负性,由著名定理“单调有界有极限”可知无穷步后未从\(D\)中离开的概率\(y_i\)存在且满足方程组

\[
y_i = \sum\limits_{j \in D} p_{ij} y_j, \quad 0 \le y_i \le 1
\]

首先,零是方程的解。其次,若该方程组有一非零解\(\{z_i\}\),则有
\[
\begin{aligned}
y_i^{(1)} - z_i &= \sum\limits_{j \in D} p_{ij}\left(1 -z_i\right) \le 0\\
y_i^{(n+1)} - z_i &= \sum\limits_{j \in D} p_{ij}\left(y_j^{(n)}-z_i\right) \le 0
\end{aligned}
\]

即\(y_i\)非零。这意味着从\(D\)之外进入\(D\)后,有非零概率永远回不去了——换句话说,机器猫可能永远赶不回去开餐。

严谨一点的数学表述:状态\(i\)是常返态,等价于对于集合\(D=S\backslash i\),上述方程组无非零解。

应用

我们来看看在我们拓展版的机器猫问题中,猫到底能不能一定回去。写出方程组
\[
\begin{aligned}
y_1 &= (1-q) y_2 \\
y_n &= q y_{n-1} + (1-q) y_{n+1}, \quad n=2,3,4,...
\end{aligned}
\]

其有解\(y_n = A\sum_{k=1}^n \left(\frac{q}{1-q}\right)^k\),其中\(A\)为任意常数。

可见当\(q \le 1/2\)时,可以通过选取恰当的\(A\)来找到一个满足需求的非零解,即机器猫只能以有限的概率\(q/(1-q)\)回到\(x=0\)处。

作为一个练习,读者可以尝试证明:
考虑\(\{0,1,2,...\}\)上的Markov链,\(p_{01}=1\),对于\(x\ge 1\),\( p_{x,x+1}=1/2\),\(p_{x,x-1}=\exp(-cx^{-\alpha})/2\),\(p_{x,x}=[1-\exp(-cx^{-\alpha})]/2,c\ge 0 .\)全部状态都是常返态的充要条件是
(1)\(\alpha \gt 1\) or (2)\(c=0\) or (3) \(\alpha=1 \text{and} c\le 1\)

参考文献

王锌坤 随机过程通论(上卷),北京师范大学出版社,1996

机器猫和玩具鼠》上有 2 条评论

  1. 题干的图片,由于使用了七牛云存储测试域名而挂掉 ( ゚∀。)
    我的旧博客也受到这个困扰,而且旧博客托管在无法登录的 logdown.com 因此无法修改……

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>