前言

  最近在做图上随机游走的期望题时，发现不同的状态定义会得到不同结果。其中一个状态的定义与转移看上去都蛮对的，但实际是错误的，我看了好久都看不出来，最后手推才发现其中的问题，原因是混淆了条件期望与绝对期望。这次的推导过程让我受益匪浅，故将其记录下来。

案例引入

  先引入一个简单的例子，给定一个 $4$ 个节点 $4$ 条边的有向带权图：

1 2 1
1 3 1
2 4 1
3 4 0

  设节点 $1$ 为起点，节点 $4$ 为终点。每条边都有对应的转移概率，节点 $1$ 转移至节点 $2$ 与节点 $3$ 的概率均为 $0.5$，节点 $2$ 与节点 $3$ 转移至终点 $4$ 的概率均为 $1$。问题要求解从起点 $1$ 到达终点 $4$ 的期望距离。

  先给出正确的解法。定义 $E^{\text{out}}(u)$ 表示从节点 $u$ 出发到达终点 $t$ 的期望距离，则有 $$E^{\text{out}}(u) = \sum\limits_{v \in \mathcal{N}^+(u)} p_{u,v} \left(w_{u,v} + E^{\text{out}}(v)\right)$$

  其中 $\mathcal{N}^+(u)$ 表示节点 $u$ 的所有出边指向的节点集合，$p_{u,v}$ 是选择边 $(u,v)$ 的转移概率，$w_{u,v}$ 是边 $(u,v)$ 的权值。对应到上图中，$E^{\text{out}}(4) = 0$，$E^{\text{out}}(3) = 1.0 \times (0+0) = 0$，$E^{\text{out}}(2) = 1.0 \times (1+0) = 1$，因此 $E^{\text{out}}(1) = 0.5 \times (1+1) + 0.5 \times (1+0) = 1.5$。该结果的正确性可以通过枚举所有路径直观验证：从起点 $1$ 到终点 $4$ 的所有可能路径仅有 $1 \overset{1}{\rightarrow} 2 \overset{1}{\rightarrow} 4$ 与 $1 \overset{1}{\rightarrow} 3 \overset{0}{\rightarrow} 4$，两者的发生概率均为 $0.5$，由期望的定义可得期望距离为 $0.5 \times 2 + 0.5 \times 1 = 1.5$。

  再给出一种错误的解法。定义 $E^{\text{in}}(u)$ 表示从起点 $s$ 到达节点 $u$ 的期望距离，试图构造递推式 $$E^{\text{in}}(u) = \sum\limits_{v \in \mathcal{N}^-(u)} p_{v,u} \left(E^{\text{in}}(v) + w_{v,u}\right)$$

  其中 $\mathcal{N}^-(u)$ 表示指向节点 $u$ 的所有入边来源节点集合。对应到图中，$E^{\text{in}}(1) = 0$，$E^{\text{in}}(2) = 0.5 \times (0+1) = 0.5$，$E^{\text{in}}(3) = 0.5 \times (0+1) = 0.5$，进而 $E^{\text{in}}(4) = 1.0 \times (0.5+1) + 1.0 \times (0.5+0) = 2.0$。这与正确结果矛盾，说明该递推方法有误。下面将通过严格的数学推导，剖析这两种方法背后的逻辑差异。

基于路径概率和的正误剖析

  首先对一般化场景给出前提设定：

1. 图 $G = (V,E)$ 是弱连通的有向无环简单图（DAG）。
2. 图中存在唯一的起点 $s \in V$ 与唯一的汇点（即出度为 $0$ 的节点），记该汇点为终点 $t$。
3. 从图中任意节点出发沿边移动，必然在有限步内到达 $t$。
4. 对于图中除 $t$ 外的任意节点，其所有出边上的转移概率之和恒为 $1$。

  求解从 $s$ 到 $t$ 的期望距离，本质上是一个图上的随机游走问题。该过程满足离散时间马尔可夫链的无后效性：$$P(X_{n+1} \mid X_{n} = x_{n}, X_{n-1} = x_{n-1}, \ldots, X_{0} = x_{0}) = P(X_{n+1} \mid X_{n} = x_{n})$$

  即下一跳状态仅依赖于当前所在节点。结合上述设定，此随机游走可建模为一个吸收马尔可夫链，其中 $t$ 为吸收态，其余节点为瞬态，且从任意瞬态出发均以概率 $1$ 最终到达吸收态。

  定义 $\mathcal{P}_u^{\text{out}}$ 表示从 $u$ 到终点 $t$ 的所有路径构成的集合，由期望的定义有 $$E^{\text{out}}(u) = \sum\limits_{P \in \mathcal{P}_u^{\text{out}}} p(P) \cdot d(P)$$

  其中 $P \in \mathcal{P}_u^{\text{out}}$ 表示一条从 $u$ 到 $t$ 的路径，$p(P)$ 表示路径 $P$ 上所有边的概率之积，$d(P)$ 表示路径 $P$ 上所有边的权值之和。

  进一步，根据路径的第一条边（即 $u$ 的一条出边 $(u,v)$，其中 $v \in \mathcal{N}^+(u)$），可将 $\mathcal{P}_u^{\text{out}}$ 划分为 $\lvert \mathcal{N}^+(u) \rvert$ 个互不相交的子集 $\mathcal{P}_{(u,v)}^{\text{out}} \subseteq \mathcal{P}_u^{\text{out}}$。定义 $\oplus$ 表示路径（或边）的拼接运算，那么对于 $\mathcal{P}_{(u,v)}^{\text{out}}$ 中的任意路径 $P$，均可表示为 $P = (u,v) \oplus P_{v \leadsto t}$，其中 $P_{v \leadsto t} \in \mathcal{P}_v^{\text{out}}$ 表示从 $v$ 到 $t$ 的后缀路径。

  因此，对于经过特定出边 $(u,v)$ 的路径，其期望贡献 $E^{\text{out}}_{(u,v)}(u)$ 的推导如下：

$$
\begin{align*}
E^{\text{out}}_{(u,v)}(u)
&= \sum_{P \in \mathcal{P}_{(u,v)}^{\text{out}}}{p(P) \cdot d(P)} \\
&= \sum_{P \in \mathcal{P}_{(u,v)}^{\text{out}}}{p((u,v) \oplus P_{v \leadsto t}) \cdot d((u,v) \oplus P_{v \leadsto t})} \\
&= \sum_{P \in \mathcal{P}_{(u,v)}^{\text{out}}}{p_{u,v} \cdot p(P_{v \leadsto t}) \cdot (w_{u,v}+d(P_{v \leadsto t}))} \\
&= p_{u,v} \left(w_{u,v}\sum_{P \in \mathcal{P}_{(u,v)}^{\text{out}}}{p(P_{v \leadsto t})} + \sum_{P \in \mathcal{P}_{(u,v)}^{\text{out}}}{p(P_{v \leadsto t}) \cdot d(P_{v \leadsto t})}\right) \\
&= p_{u,v} \left(w_{u,v}\sum_{P \in \mathcal{P}_{v}^{\text{out}}}{p(P)} + \sum_{P \in \mathcal{P}_{v}^{\text{out}}}{p(P) \cdot d(P)}\right) \\
&= p_{u,v} \left(w_{u,v}\sum_{P \in \mathcal{P}_{v}^{\text{out}}}{p(P)} + E^{\text{out}}(v)\right)
\end{align*}
$$

  其中 $\sum\limits_{P \in \mathcal{P}_{v}^{\text{out}}} p(P)$ 表示从 $v$ 到 $t$ 的所有路径概率之和。根据上述设定，该和恰好等于 $1$。直觉上，因为 $v$ 必然能到达 $t$，且离开每个节点的出边概率完备，所有可能的路径概率理应构成一个完备事件组。严格证明可通过数学归纳法给出。

  定义 $S(u) = \sum\limits_{P \in \mathcal{P}_{u}^{\text{out}}} p(P)$，证明对任意 $u \in V$ 均有 $S(u) = 1$。对于终点 $t$，规定其到自身的空路径概率为 $1$，即 $S(t) = 1$。对 DAG 按拓扑逆序进行归纳，假设节点 $u$ 的所有出边指向的节点 $v \in \mathcal{N}^+(u)$ 均满足 $S(v) = 1$。由全概率公式有 $S(u) = \sum\limits_{v \in \mathcal{N}^+(u)} p_{u,v} \cdot S(v)$，代入归纳假设及上述设定 $\sum\limits_{v \in \mathcal{N}^+(u)} p_{u,v} = 1$，可得 $S(u) = \sum\limits_{v \in \mathcal{N}^+(u)} p_{u,v} \cdot 1 = 1$。证毕。

  因此有 $E^{\text{out}}_{(u,v)}(u) = p_{u,v} \left(w_{u,v} + E^{\text{out}}(v)\right)$。最后，将所有出边的贡献求和，即得 $$E^{\text{out}}(u) = \sum\limits_{v \in \mathcal{N}^+(u)} E^{\text{out}}_{(u,v)}(u) = \sum\limits_{v \in \mathcal{N}^+(u)} p_{u,v} \left(w_{u,v} + E^{\text{out}}(v)\right)$$

  与正确方法中的定义一致。

  接下来用相同的思路剖析错误方法中的递推式。定义 $\mathcal{P}_u^{\text{in}}$ 表示从起点 $s$ 到节点 $u$ 的所有路径构成的集合，子集 $\mathcal{P}_{(v,u)}^{\text{in}} \subseteq \mathcal{P}_u^{\text{in}}$ 表示其中以边 $(v,u)$ 作为最后一条边的路径集合。对于任意 $P \in \mathcal{P}_{(v,u)}^{\text{in}}$，可拆分为 $P = P_{s \leadsto v} \oplus (v,u)$，其中 $P_{s \leadsto v} \in \mathcal{P}_v^{\text{in}}$ 表示从 $s$ 到 $v$ 的前缀路径。

  对于经过特定入边 $(v,u)$ 的期望贡献 $E^{\text{in}}_{(v,u)}(u)$，类似地有：

$$
\begin{align*}
E^{\text{in}}_{(v,u)}(u)
&= \sum_{P \in \mathcal{P}_{(v,u)}^{\text{in}}}{p(P) \cdot d(P)} \\
&= \sum_{P \in \mathcal{P}_{(v,u)}^{\text{in}}}{p(P_{s \leadsto v} \oplus (v,u)) \cdot d(P_{s \leadsto v} \oplus (v,u))} \\
&= \sum_{P \in \mathcal{P}_{(v,u)}^{\text{in}}}{p(P_{s \leadsto v}) \cdot p_{v,u} \cdot (d(P_{s \leadsto v})+w_{v,u})} \\
&= p_{v,u} \left(\sum_{P \in \mathcal{P}_{(v,u)}^{\text{in}}}{p(P_{s \leadsto v}) \cdot d(P_{s \leadsto v})} + w_{v,u}\sum_{P \in \mathcal{P}_{(v,u)}^{\text{in}}}{p(P_{s \leadsto v})}\right) \\
&= p_{v,u} \left(\sum_{P \in \mathcal{P}_{v}^{\text{in}}}{p(P) \cdot d(P)} + w_{v,u}\sum_{P \in \mathcal{P}_{v}^{\text{in}}}{p(P)}\right) \\
&= p_{v,u} \left(E^{\text{in}}(v) + w_{v,u}\sum_{P \in \mathcal{P}_{v}^{\text{in}}}{p(P)}\right)
\end{align*}
$$

  在上述推导中，如果错误地假定 $\sum\limits_{P \in \mathcal{P}_{v}^{\text{in}}} p(P) = 1$，便会得到 $E^{\text{in}}_{(v,u)}(u) = p_{v,u} \left(E^{\text{in}}(v) + w_{v,u}\right)$，进而汇总得出错误的递推式。事实上，$\sum\limits_{P \in \mathcal{P}_{v}^{\text{in}}} p(P)$ 表示的是从起点 $s$ 出发最终恰好到达节点 $v$ 的所有路径概率之和。与“从 $v$ 必然到达终点 $t$”这一必然事件不同，从 $s$ 出发的游走在每一步都有多种选择，到达某个特定的中间节点 $v$ 并非必然事件，因此该概率之和通常严格小于 $1$。

  将其记为到达概率 $\pi(u) = \sum\limits_{P \in \mathcal{P}_{u}^{\text{in}}} p(P)$，根据全概率公式容易得到其递推式 $\pi(u) = \sum\limits_{v \in \mathcal{N}^-(u)} p_{v,u} \cdot \pi(v)$，其中初始条件为 $\pi(s) = 1$。将 $\pi(v)$ 代回先前的推导，才能得到真正正确的递推式 $$E^{\text{in}}(u) = \sum\limits_{v \in \mathcal{N}^-(u)} p_{v,u} \left(E^{\text{in}}(v) + w_{v,u} \cdot \pi(v)\right)$$

条件期望与绝对期望的混淆

  从概率论的更本质视角来看，上述正推与倒推的差异，根源在于条件期望与绝对期望的混淆。在正向推导中，由于 $\pi(v) = 1$ 的归一化特性，给定当前状态的条件已被概率归一化所消化，因此看似未显式使用条件概率。而在反向推导中，归一化不再成立，混淆两者便会导致错误。

  具体而言，$E^{\text{out}}(u)$ 本质上是一个条件期望，等价于 $\mathbb{E}[d(P_{u \leadsto t}) \mid X_0=u]$。由全期望公式展开得 $$\mathbb{E}[d(P_{u \leadsto t}) \mid X_0=u] = \sum\limits_{v \in \mathcal{N}^+(u)} \mathbb{E}[d(P_{u \leadsto t}) \mid X_1=v,X_0=u] \cdot P(X_1=v \mid X_0=u)$$

  其中条件转移概率 $P(X_1=v \mid X_0=u)$ 恰好对应边 $(u,v)$ 的转移概率 $p_{u,v}$。根据马尔可夫性 $$\mathbb{E}[d(P_{u \leadsto t}) \mid X_1=v,X_0=u] = \mathbb{E}[w_{u,v} + d(P_{v \leadsto t}) \mid X_0=v] = w_{u,v} + \mathbb{E}[d(P_{v \leadsto t}) \mid X_0=v]$$

  代回即得 $$\mathbb{E}[d(P_{u \leadsto t}) \mid X_0=u] = \sum\limits_{v \in \mathcal{N}^+(u)} \left(w_{u,v} + \mathbb{E}[d(P_{v \leadsto t}) \mid X_0=v]\right) \cdot p_{u,v}$$

  其与 $E^{\text{out}}(u)$ 的递推式完全一致。

  而对于反向推导，$E^{\text{in}}(u)$ 本质上是无条件的绝对期望 $\mathbb{E}[d(P_{s \leadsto u})]$。定义事件 $A_v$ 为从 $s$ 到达节点 $v$，事件 $B_{(v,u)}$ 为在节点 $v$ 处选择了边 $(v,u)$。同样利用全期望公式展开 $$\mathbb{E}[d(P_{s \leadsto u})] = \sum\limits_{v \in \mathcal{N}^-(u)} \mathbb{E}[d(P_{s \leadsto u}) \mid A_v, B_{(v,u)}] \cdot P(A_v, B_{(v,u)})$$

  其中联合概率 $P(A_v, B_{(v,u)}) = \pi(v) \cdot p_{v,u}$，而条件期望 $$\mathbb{E}[d(P_{s \leadsto u}) \mid A_v, B_{(v,u)}] = \mathbb{E}[d(P_{s \leadsto v}) + w_{v,u} \mid A_v, B_{(v,u)}] = \mathbb{E}[d(P_{s \leadsto v}) \mid A_v, B_{(v,u)}] + w_{v,u}$$

  由于游走满足马尔可夫性，当已知到达 $v$（即事件 $A_v$）时，后续选择哪条出边（$B_{v,u}$）与之前走过的总路程（$d(P_{s \leadsto v})$）相互独立，故 $\mathbb{E}[d(P_{s \leadsto v}) \mid A_v, B_{(v,u)}] = \mathbb{E}[d(P_{s \leadsto v}) \mid A_v]$。此时，$\mathbb{E}[d(P_{s \leadsto v}) \mid A_v]$ 表示在到达 $v$ 的前提下从 $s$ 到 $v$ 的条件期望，而 $E^{\text{in}}(v)$ 是绝对期望 $\mathbb{E}[d(P_{s \leadsto v})]$。

  两者的关系需通过全期望公式对是否到达 $v$ 进行拆解来确立：$$\mathbb{E}[d(P_{s \leadsto v})] = \mathbb{E}[d(P_{s \leadsto v}) \mid A_v] \cdot P(A_v) + \mathbb{E}[d(P_{s \leadsto v}) \mid \neg A_v] \cdot P(\neg A_v)$$

  由于未到达 $v$ 时距离 $d(P_{s \leadsto v})$ 视为 $0$，故后半部分为 $0$，且 $P(A_v) = \pi(v)$。从而有 $\mathbb{E}[d(P_{s \leadsto v})] = \mathbb{E}[d(P_{s \leadsto v}) \mid A_v] \cdot \pi(v)$，即 $\mathbb{E}[d(P_{s \leadsto v}) \mid A_v] = \frac{\mathbb{E}[d(P_{s \leadsto v})]}{\pi(v)}$。

  将此式代回前式，可得 $$\mathbb{E}[d(P_{s \leadsto u})] = \left(\frac{\mathbb{E}[d(P_{s \leadsto v})]}{\pi(v)} + w_{v,u}\right) \cdot \pi(v) \cdot p_{v,u} = p_{v,u} \left(\mathbb{E}[d(P_{s \leadsto v})] + w_{v,u} \cdot \pi(v)\right)$$

  这与修正后的 $E^{\text{in}}(u)$ 递推式一致。

总结

  回顾最初错误的递推式 $E^{\text{in}}(u) = \sum\limits_{v \in \mathcal{N}^-(u)} p_{v,u} \left(E^{\text{in}}(v) + w_{v,u}\right)$，其错误根源在于推导中隐式地默认了 $\mathbb{E}[d(P_{s \leadsto v}) \mid A_v] = \mathbb{E}[d(P_{s \leadsto v})]$，即条件期望等于绝对期望。而该等式成立的唯一条件是 $\pi(v) = 1$，即从起点必然走到节点 $v$。在 $E^{\text{out}}(u)$ 的推导中，由于从任何节点出发必然到达终点 $t$，概率归一化始终成立。但在 $E^{\text{in}}(u)$ 中，从起点出发并不一定经过 $v$，$\pi(v)$ 是一个小于 $1$ 的概率，归一化条件不再满足，故不可随意将绝对期望与条件期望混为一谈。

参考资料

  图上随机游走 - OI Wiki：https://oi-wiki.org/graph/graph-random-walk/

  面向高中生的马尔可夫链（Markov Chains）和游走相关的概率递推问题：https://zhuanlan.zhihu.com/p/653026889

  概率统计随机过程之条件期望与重期望公式 _ SurprisedCat：https://surprisedcat.github.io/studynotes/%E6%A6%82%E7%8E%87%E7%BB%9F%E8%AE%A1%E9%9A%8F%E6%9C%BA%E8%BF%87%E7%A8%8B%E4%B9%8B%E6%9D%A1%E4%BB%B6%E6%9C%9F%E6%9C%9B%E4%B8%8E%E9%87%8D%E6%9C%9F%E6%9C%9B%E5%85%AC%E5%BC%8F/