无限状态马尔可夫链中从状态0到达状态1的概率求解
我来帮你梳理这个问题的完整求解过程，咱们从建模到递推方程再到利用极限条件收尾，一步步拆解：
问题建模
首先，我们把这个随机游走问题转化为马尔可夫链来分析：
- 状态空间设为${1, 0, -1, -2, \dots}$，每个状态对应当前的部分和（比如状态$n$表示前$k$项和$X_1+\dots+X_k=n$）
- 定义$p_n$为从状态$n$出发，最终到达状态1的概率，我们的目标就是计算$p_0$
建立递推方程
根据$X_n$的概率分布，我们可以写出每个状态的递推关系：
- 对于初始状态0：
从0出发，有$\frac{1}{6}$的概率直接跳到状态1（这就成功到达目标，贡献概率$\frac{1}{6}$）；$\frac{1}{3}$的概率留在状态0，后续成功的概率还是$p_0$；$\frac{1}{2}$的概率跳到状态-1，后续成功的概率是$p_{-1}$。因此方程为：
$$p_0 = \frac{1}{6} + \frac{1}{3}p_0 + \frac{1}{2}p_{-1}$$ - 对于状态$-1$：
从-1出发，$\frac{1}{6}$的概率跳到0（后续概率$p_0$）；$\frac{1}{3}$的概率留在-1（后续概率$p_{-1}$）；$\frac{1}{2}$的概率跳到-2（后续概率$p_{-2}$），方程为：
$$p_{-1} = \frac{1}{6}p_0 + \frac{1}{3}p_{-1} + \frac{1}{2}p_{-2}$$ - 通用递推式（对任意正整数$k$）：
对于状态$-k$，同理可得：
$$p_{-k} = \frac{1}{6}p_{-k+1} + \frac{1}{3}p_{-k} + \frac{1}{2}p_{-k-1}$$
化简递推关系
先把通用递推式整理一下，将含$p_{-k}$的项移到左边：
$$\frac{2}{3}p_{-k} = \frac{1}{6}p_{-k+1} + \frac{1}{2}p_{-k-1}$$
两边乘以6消去分母，得到线性齐次递推方程：
$$p_{-k+1} - 4p_{-k} + 3p_{-k-1} = 0$$
解这个递推的特征方程$r^2 - 4r + 3 = 0$，得到两个根$r=1$和$r=3$，因此递推的通解形式为：
$$p_{-k} = A + B \cdot \left(\frac{1}{3}\right)^k$$
其中$A$和$B$是待确定的常数，我们可以用$p_0$来表示它们：
- 当$k=0$时，$p_0 = A + B$
- 从$p_0$的方程解出$p_{-1}$：整理$p_0 = \frac{1}{6} + \frac{1}{3}p_0 + \frac{1}{2}p_{-1}$，可得$p_{-1} = \frac{4}{3}p_0 - \frac{1}{3}$
- 代入$k=1$时的通解：$p_{-1} = A + \frac{B}{3}$
联立这两个式子，解出$A = \frac{3p_0 - 1}{2}$，$B = \frac{1 - p_0}{2}$，因此通解可以写成：
$$p_{-k} = \frac{3p_0 - 1}{2} + \frac{1 - p_0}{2} \cdot \left(\frac{1}{3}\right)^k$$
利用极限条件确定$p_0$
现在需要一个额外条件来锁定$p_0$：观察$p_{-k}$的性质——当$k$越来越大时，状态$-k$离目标状态1越来越远，而且每次走步有$\frac{1}{2}$的概率往更负的方向移动，只有$\frac{1}{6}$的概率往正方向移动，直观上，当$k \to \infty$时，从状态$-k$出发到达1的概率应该趋近于0（毕竟从无穷远的负状态走到1的可能性几乎为0）。
当$k \to \infty$时，$\left(\frac{1}{3}\right)^k \to 0$，所以$p_{-k} \to A$，根据上面的分析，这个极限等于0，即：
$$A = \frac{3p_0 - 1}{2} = 0$$
解这个方程直接得到$p_0 = \frac{1}{3}$，这就是我们要证明的结果！
备注：内容来源于stack exchange，提问作者romperextremeabuser
