直线醉汉行走变体问题求解及马尔可夫链方法咨询

问题描述 #

我正在尝试解决醉汉行走的一个变体问题：
醉汉当前站的位置，再往悬崖方向走一步就会掉下去。他随机迈步，要么远离悬崖，要么朝向悬崖。每一步中，他远离悬崖的概率是$\frac{2}{3}$，朝向悬崖的概率是$\frac{1}{3}$。请问他最终逃离悬崖的概率是多少？

我的思路困惑 #

一开始我想画概率树，得到了这样一个无穷级数：
$$ \sum_{n=0}^{\infty} \left(\frac{2}{3}\right)^{n\left(\frac{1}{3}\right)}{n+1} $$
但这个式子没考虑到比如醉汉在位置2和1之间来回走几次，然后才掉下去的情况。于是我修正成了这个级数：
$$ \sum_{n=0}^{\infty} \binom{2n+1}{n} \left(\frac{2}{3}\right)^{n\left(\frac{1}{3}\right)}{n+1} $$
我的想法是，这个式子把所有恰好走了n步远离悬崖、n+1步朝向悬崖然后掉下去的情况都加起来了。但这个级数的和是1.5，大于1，显然不是有效的概率。

想请教一下我哪里错了？另外，怎么用马尔可夫链/转移矩阵来解决这个问题（我对这两个概念不太熟悉）？

问题分析与解法分享 #

先说说你的级数错在哪

你那个组合数$\binom{2n+1}{n}$是从2n+1步里选n步走远离方向的组合数，但这里有个致命漏洞：这些路径里包含了中途已经掉下去的情况！举个例子，当n=1时，组合数是$\binom{3}{1}=3$，对应的三条路径：

• 远→近→近：这条没问题，最后一步才掉下去
• 近→远→近：但第一步走“近”的时候，醉汉已经直接掉下去了，后面两步根本不会发生！
• 近→近→远：同样，第一步就掉下去了，后面的步数不存在

你把这些提前终止的无效路径也算进总和里了，自然就会超过1，这就是问题所在。

解法一：递推法（最直观）

我们先定义一个变量：$P_k$表示醉汉在距离悬崖k步的位置时，最终能逃离悬崖的概率（你的问题里初始位置就是k=1，因为再走一步就掉下去）。

先明确两个边界条件：

• 如果醉汉已经掉下去了（k=0），那肯定没法逃离，所以$P_0=0$
• 当醉汉离悬崖足够远时，他几乎肯定能一直往远离的方向走，最终逃离，所以当k趋向无穷大时，$P_k→1$

接下来找递推关系：当醉汉在位置k时，下一步有$\frac{2}{3}$的概率走到k+1（更远），$\frac{1}{3}$的概率走到k-1（更近），所以：
$$ P_k = \frac{2}{3}P_{k+1} + \frac{1}{3}P_{k-1} $$
整理成标准线性递推方程：
$$ 2P_{k+1} - 3P_k + P_{k-1} = 0 $$
解这个方程的特征方程是$2r^2 -3r +1=0$，算出两个根是$r=1$和$r=\frac{1}{2}$，所以通解是：
$$ P_k = A + B\left(\frac{1}{2}\right)^k $$
代入边界条件：

• 当k=0时，$0 = A + B$ → $B=-A$
• 当k→∞时，$\left(\frac{1}{2}\right)^k$趋向0，所以$1 = A$，进而$B=-1$

最终得到$P_k = 1 - \left(\frac{1}{2}\right)^k$。你的问题里初始位置k=1，所以$P_1=1-\frac{1}{2}=\frac{1}{2}$——也就是说，醉汉最终逃离悬崖的概率是$\frac{1}{2}$。

解法二：马尔可夫链方法（适合拓展复杂问题）

如果你想用马尔可夫链来解，我们先把醉汉的位置定义为链的状态：

• 状态0：已经掉下去（这是个吸收态，一旦进入就再也出不来了）
• 状态1：初始位置（离悬崖1步）
• 状态2：离悬崖2步
• ...
• 状态k：离悬崖k步（k≥1）

然后构建转移矩阵$T$，其中$T_{i,j}$表示从状态i走到状态j的概率：

• 对于状态0：$T_{0,0}=1$，其他$T_{0,j}=0$（吸收态，一直待在这）
• 对于状态k≥1：$T_{k,k+1}=\frac{2}{3}$（往远离悬崖走），$T_{k,k-1}=\frac{1}{3}$（往悬崖走），其他$T_{k,j}=0$

我们要求的是从状态1出发，最终不被吸收到状态0的概率（也就是逃离的概率）。这在马尔可夫链里叫吸收概率，解法其实和递推法本质一致：设$P_k$是从状态k出发不被吸收到0的概率，同样得到递推式$P_k=\frac{2}{3}P_{k+1}+\frac{1}{3}P_{k-1}$，结合边界条件$P_0=0$和$\lim_{k→∞}P_k=1$，最终算出$P_1=\frac{1}{2}$。

要是你觉得抽象，也可以用简化的方程联立理解：设x是从状态1出发逃离的概率，y是从状态2出发逃离的概率。那么：

• 从状态1出发，有$\frac{1}{3}$概率直接掉下去（逃离失败），$\frac{2}{3}$概率走到状态2，所以$x = \frac{2}{3}y$
• 从状态2出发，每一步都有$\frac{2}{3}$的概率往更远处走（最终逃离的概率趋近于1），$\frac{1}{3}$的概率回到状态1，结合递推的通解逻辑，最终也能得到$x=\frac{1}{2}$的结果。

备注：内容来源于stack exchange，提问作者Matthew Kaplan