对较为复杂的游走问题的探讨

lyin 问我的，回宿舍推了十分钟推出来了，记一下。

首先有一个看起来很经典的游走问题：

假设有三个点 A, B, C，有三条边 \(A \to A, A \to B, A \to C\)，概率分别为 \(p_A, p_B, p_C\)，长度均为 \(1\)，问从 \(A\) 到 \(B\) 的概率与期望步数。

这个问题很简单，我们考虑设 \(p\) 为概率，那么显然有 \(p = p_A p + p_B\)，即 \(p = \frac{1-p_A}{p_B}\)，直接看后者这个式子也是很有道理的。

考虑期望，设期望为 \(E\)，那么有一个朴素的想法是 \(E = p_B + p_A(E + 1)\)。但事实真的是这样的吗？

我们发现，这里要求的 \(E\) 并不是所有情况下的期望，因为可以看出本身发生的概率也不为 \(1\)，那么这样求上式子是存在问题的。

实际上有 \(E = p_B + p_AE + pp_A\)，可以理解为走一步本身的期望为 \(p\)，所以 \(E = p_B + p_A(E + p)\)，但是这样解释还是很牵强。

我们再看一道题：

假设有三个点 A, B, C，有三条边 \(A \to A, A \to B, A \to C\)，概率分别为 \(p_A, p_B, p_C\)，从 \(A \to A\) 消耗的步数期望为 \(E_A\)，同理定义 \(E_B, E_C\)，问从 \(A\) 到 \(B\) 的概率与期望步数。

概率还是一样的 \(p = p_A p + p_B\)，\(p = \frac{1-p_A}{p_B}\)，那期望是啥？

实际上，这次我们有 \(E = E_B + p_AE + pE_A\)。

\(\Large \textbf{？}\)

这啥玩意？

我们考虑另一种更方便分析的方式：概率生成函数。

当然这里并不是严格意义上的概率生成函数，因为总概率并不为 \(1\)，不过性质是一样的。

我们设最终要求的概率生成函数为 \(F(x)\)，走 \(A \to A\) 的概率生成函数为 \(G(x)\)，走 \(A \to B\) 的概率生成函数为 \(H(x)\)。

我们有关系式 \(F(x)=F(x)G(x) + H(x)\)，这个比较显然。

代入 \(x = 1\) 可得 \(F(1) = F(1)G(1) + H(1)\)，即上述式子 \(p = p_A p + p_B\)。

那么看看期望是怎么算的：\(F'(1) = F'(1)G(1) + F(1)G'(1) + H'(1)\)，即为上面的 \(E = E_B + p_AE + pE_A\)。

非常神奇。

有没有什么比较通俗易懂的解释啊，求解答。