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

2026/6/25 14:23:04

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 的期望距离。

先给出正确的解法。定义 Eout(u) 表示从节点 u 出发到达终点 t 的期望距离，则有Eout(u)=∑v∈N+(u)pu,v(wu,v+Eout(v))

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

再给出一种错误的解法。定义 Ein(u) 表示从起点 s 到达节点 u 的期望距离，试图构造递推式Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u)

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

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

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

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

求解从 s 到 t 的期望距离，本质上是一个图上的随机游走问题。该过程满足离散时间马尔可夫链的无后效性：P(Xn+1∣Xn=xn,Xn−1=xn−1,…,X0=x0)=P(Xn+1∣Xn=xn)

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

定义 Poutu 表示从 u 到终点 t 的所有路径构成的集合，由期望的定义有Eout(u)=∑P∈Poutup(P)⋅d(P)

其中 P∈Poutu 表示一条从 u 到 t 的路径，p(P) 表示路径 P 上所有边的概率之积，d(P) 表示路径 P 上所有边的权值之和。

进一步，根据路径的第一条边（即 u 的一条出边 (u,v)，其中 v∈N+(u)），可将 Poutu 划分为 |N+(u)| 个互不相交的子集 Pout(u,v)⊆Poutu。定义 ⊕ 表示路径（或边）的拼接运算，那么对于 Pout(u,v) 中的任意路径 P，均可表示为 P=(u,v)⊕Pv⇝t，其中 Pv⇝t∈Poutv 表示从 v 到 t 的后缀路径。

因此，对于经过特定出边 (u,v) 的路径，其期望贡献 Eout(u,v)(u) 的推导如下：

Eout(u,v)(u)=∑P∈Pout(u,v)p(P)⋅d(P)=∑P∈Pout(u,v)p((u,v)⊕Pv⇝t)⋅d((u,v)⊕Pv⇝t)=∑P∈Pout(u,v)pu,v⋅p(Pv⇝t)⋅(wu,v+d(Pv⇝t))=pu,v⎛⎜⎝wu,v∑P∈Pout(u,v)p(Pv⇝t)+∑P∈Pout(u,v)p(Pv⇝t)⋅d(Pv⇝t)⎞⎟⎠=pu,v⎛⎜⎝wu,v∑P∈Poutvp(P)+∑P∈Poutvp(P)⋅d(P)⎞⎟⎠=pu,v⎛⎜⎝wu,v∑P∈Poutvp(P)+Eout(v)⎞⎟⎠

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

定义 S(u)=∑P∈Poutup(P)，证明对任意 u∈V 均有 S(u)=1。对于终点 t，规定其到自身的空路径概率为 1，即 S(t)=1。对 DAG 按拓扑逆序进行归纳，假设节点 u 的所有出边指向的节点 v∈N+(u) 均满足 S(v)=1。由全概率公式有 S(u)=∑v∈N+(u)pu,v⋅S(v)，代入归纳假设及上述设定 ∑v∈N+(u)pu,v=1，可得 S(u)=∑v∈N+(u)pu,v⋅1=1。证毕。

因此有 Eout(u,v)(u)=pu,v(wu,v+Eout(v))。最后，将所有出边的贡献求和，即得Eout(u)=∑v∈N+(u)Eout(u,v)(u)=∑v∈N+(u)pu,v(wu,v+Eout(v))

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

接下来用相同的思路剖析错误方法中的递推式。定义 Pinu 表示从起点 s 到节点 u 的所有路径构成的集合，子集 Pin(v,u)⊆Pinu 表示其中以边 (v,u) 作为最后一条边的路径集合。对于任意 P∈Pin(v,u)，可拆分为 P=Ps⇝v⊕(v,u)，其中 Ps⇝v∈Pinv 表示从 s 到 v 的前缀路径。

对于经过特定入边 (v,u) 的期望贡献 Ein(v,u)(u)，类似地有：

Ein(v,u)(u)=∑P∈Pin(v,u)p(P)⋅d(P)=∑P∈Pin(v,u)p(Ps⇝v⊕(v,u))⋅d(Ps⇝v⊕(v,u))=∑P∈Pin(v,u)p(Ps⇝v)⋅pv,u⋅(d(Ps⇝v)+wv,u)=pv,u⎛⎜⎝∑P∈Pin(v,u)p(Ps⇝v)⋅d(Ps⇝v)+wv,u∑P∈Pin(v,u)p(Ps⇝v)⎞⎟⎠=pv,u⎛⎜⎝∑P∈Pinvp(P)⋅d(P)+wv,u∑P∈Pinvp(P)⎞⎟⎠=pv,u⎛⎜⎝Ein(v)+wv,u∑P∈Pinvp(P)⎞⎟⎠

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

将其记为到达概率 π(u)=∑P∈Pinup(P)，根据全概率公式容易得到其递推式 π(u)=∑v∈N−(u)pv,u⋅π(v)，其中初始条件为 π(s)=1。将 π(v) 代回先前的推导，才能得到真正正确的递推式Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u⋅π(v))

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

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

具体而言，Eout(u) 本质上是一个条件期望，等价于 E[d(Pu⇝t)∣X0=u]。由全期望公式展开得E[d(Pu⇝t)∣X0=u]=∑v∈N+(u)E[d(Pu⇝t)∣X1=v,X0=u]⋅P(X1=v∣X0=u)

其中条件转移概率 P(X1=v∣X0=u) 恰好对应边 (u,v) 的转移概率 pu,v。根据马尔可夫性E[d(Pu⇝t)∣X1=v,X0=u]=E[wu,v+d(Pv⇝t)∣X0=v]=wu,v+E[d(Pv⇝t)∣X0=v]

代回即得E[d(Pu⇝t)∣X0=u]=∑v∈N+(u)(wu,v+E[d(Pv⇝t)∣X0=v])⋅pu,v

其与 Eout(u) 的递推式完全一致。

而对于反向推导，Ein(u) 本质上是无条件的绝对期望 E[d(Ps⇝u)]。定义事件 Av 为从 s 到达节点 v，事件 B(v,u) 为在节点 v 处选择了边 (v,u)。同样利用全期望公式展开E[d(Ps⇝u)]=∑v∈N−(u)E[d(Ps⇝u)∣Av,B(v,u)]⋅P(Av,B(v,u))

其中联合概率 P(Av,B(v,u))=π(v)⋅pv,u，而条件期望E[d(Ps⇝u)∣Av,B(v,u)]=E[d(Ps⇝v)+wv,u∣Av,B(v,u)]=E[d(Ps⇝v)∣Av,B(v,u)]+wv,u

由于游走满足马尔可夫性，当已知到达 v（即事件 Av）时，后续选择哪条出边（Bv,u）与之前走过的总路程（d(Ps⇝v)）相互独立，故 E[d(Ps⇝v)∣Av,B(v,u)]=E[d(Ps⇝v)∣Av]。此时，E[d(Ps⇝v)∣Av] 表示在到达 v 的前提下从 s 到 v 的条件期望，而 Ein(v) 是绝对期望 E[d(Ps⇝v)]。

两者的关系需通过全期望公式对是否到达 v 进行拆解来确立：E[d(Ps⇝v)]=E[d(Ps⇝v)∣Av]⋅P(Av)+E[d(Ps⇝v)∣¬Av]⋅P(¬Av)

由于未到达 v 时距离 d(Ps⇝v) 视为 0，故后半部分为 0，且 P(Av)=π(v)。从而有 E[d(Ps⇝v)]=E[d(Ps⇝v)∣Av]⋅π(v)，即 E[d(Ps⇝v)∣Av]=E[d(Ps⇝v)]π(v)。

将此式代回前式，可得E[d(Ps⇝u)]=(E[d(Ps⇝v)]π(v)+wv,u)⋅π(v)⋅pv,u=pv,u(E[d(Ps⇝v)]+wv,u⋅π(v))

这与修正后的 Ein(u) 递推式一致。

总结

回顾最初错误的递推式 Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u)，其错误根源在于推导中隐式地默认了 E[d(Ps⇝v)∣Av]=E[d(Ps⇝v)]，即条件期望等于绝对期望。而该等式成立的唯一条件是 π(v)=1，即从起点必然走到节点 v。在 Eout(u) 的推导中，由于从任何节点出发必然到达终点 t，概率归一化始终成立。但在 Ein(u) 中，从起点出发并不一定经过 v，π(v) 是一个小于 1 的概率，归一化条件不再满足，故不可随意将绝对期望与条件期望混为一谈。