案例引入
先引入一个简单的例子,给定一个 44 个节点 44 条边的有向带权图:
1 2 1 1 3 1 2 4 1 3 4 0设节点 11 为起点,节点 44 为终点。每条边都有对应的转移概率,节点 11 转移至节点 22 与节点 33 的概率均为 0.50.5,节点 22 与节点 33 转移至终点 44 的概率均为 11。问题要求解从起点 11 到达终点 44 的期望距离。
先给出正确的解法。定义 Eout(u)�out(�) 表示从节点 u� 出发到达终点 t� 的期望距离,则有Eout(u)=∑v∈N+(u)pu,v(wu,v+Eout(v))�out(�)=∑�∈�+(�)��,�(��,�+�out(�))
其中 N+(u)�+(�) 表示节点 u� 的所有出边指向的节点集合,pu,v��,� 是选择边 (u,v)(�,�) 的转移概率,wu,v��,� 是边 (u,v)(�,�) 的权值。对应到上图中,Eout(4)=0�out(4)=0,Eout(3)=1.0×(0+0)=0�out(3)=1.0×(0+0)=0,Eout(2)=1.0×(1+0)=1�out(2)=1.0×(1+0)=1,因此 Eout(1)=0.5×(1+1)+0.5×(1+0)=1.5�out(1)=0.5×(1+1)+0.5×(1+0)=1.5。该结果的正确性可以通过枚举所有路径直观验证:从起点 11 到终点 44 的所有可能路径仅有 11→21→41→12→14 与 11→30→41→13→04,两者的发生概率均为 0.50.5,由期望的定义可得期望距离为 0.5×2+0.5×1=1.50.5×2+0.5×1=1.5。
再给出一种错误的解法。定义 Ein(u)�in(�) 表示从起点 s� 到达节点 u� 的期望距离,试图构造递推式Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u)�in(�)=∑�∈�−(�)��,�(�in(�)+��,�)
其中 N−(u)�−(�) 表示指向节点 u� 的所有入边来源节点集合。对应到图中,Ein(1)=0�in(1)=0,Ein(2)=0.5×(0+1)=0.5�in(2)=0.5×(0+1)=0.5,Ein(3)=0.5×(0+1)=0.5�in(3)=0.5×(0+1)=0.5,进而 Ein(4)=1.0×(0.5+1)+1.0×(0.5+0)=2.0�in(4)=1.0×(0.5+1)+1.0×(0.5+0)=2.0。这与正确结果矛盾,说明该递推方法有误。下面将通过严格的数学推导,剖析这两种方法背后的逻辑差异。
基于路径概率和的正误剖析
首先对一般化场景给出前提设定:
- 图 G=(V,E)�=(�,�) 是弱连通的有向无环简单图(DAG)。
- 图中存在唯一的起点 s∈V�∈� 与唯一的汇点(即出度为 00 的节点),记该汇点为终点 t�。
- 从图中任意节点出发沿边移动,必然在有限步内到达 t�。
- 对于图中除 t� 外的任意节点,其所有出边上的转移概率之和恒为 11。
求解从 s� 到 t� 的期望距离,本质上是一个图上的随机游走问题。该过程满足离散时间马尔可夫链的无后效性:P(Xn+1∣Xn=xn,Xn−1=xn−1,…,X0=x0)=P(Xn+1∣Xn=xn)�(��+1∣��=��,��−1=��−1,…,�0=�0)=�(��+1∣��=��)
即下一跳状态仅依赖于当前所在节点。结合上述设定,此随机游走可建模为一个吸收马尔可夫链,其中 t� 为吸收态,其余节点为瞬态,且从任意瞬态出发均以概率 11 最终到达吸收态。
定义 Poutu��out 表示从 u� 到终点 t� 的所有路径构成的集合,由期望的定义有Eout(u)=∑P∈Poutup(P)⋅d(P)�out(�)=∑�∈��out�(�)⋅�(�)
其中 P∈Poutu�∈��out 表示一条从 u� 到 t� 的路径,p(P)�(�) 表示路径 P� 上所有边的概率之积,d(P)�(�) 表示路径 P� 上所有边的权值之和。
进一步,根据路径的第一条边(即 u� 的一条出边 (u,v)(�,�),其中 v∈N+(u)�∈�+(�)),可将 Poutu��out 划分为 |N+(u)||�+(�)| 个互不相交的子集 Pout(u,v)⊆Poutu�(�,�)out⊆��out。定义 ⊕⊕ 表示路径(或边)的拼接运算,那么对于 Pout(u,v)�(�,�)out 中的任意路径 P�,均可表示为 P=(u,v)⊕Pv⇝t�=(�,�)⊕��⇝�,其中 Pv⇝t∈Poutv��⇝�∈��out 表示从 v� 到 t� 的后缀路径。
因此,对于经过特定出边 (u,v)(�,�) 的路径,其期望贡献 Eout(u,v)(u)�(�,�)out(�) 的推导如下:
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)⎞⎟⎠�(�,�)out(�)=∑�∈�(�,�)out�(�)⋅�(�)=∑�∈�(�,�)out�((�,�)⊕��⇝�)⋅�((�,�)⊕��⇝�)=∑�∈�(�,�)out��,�⋅�(��⇝�)⋅(��,�+�(��⇝�))=��,�(��,�∑�∈�(�,�)out�(��⇝�)+∑�∈�(�,�)out�(��⇝�)⋅�(��⇝�))=��,�(��,�∑�∈��out�(�)+∑�∈��out�(�)⋅�(�))=��,�(��,�∑�∈��out�(�)+�out(�))
其中 ∑P∈Poutvp(P)∑�∈��out�(�) 表示从 v� 到 t� 的所有路径概率之和。根据上述设定,该和恰好等于 11。直觉上,因为 v� 必然能到达 t�,且离开每个节点的出边概率完备,所有可能的路径概率理应构成一个完备事件组。严格证明可通过数学归纳法给出。
定义 S(u)=∑P∈Poutup(P)�(�)=∑�∈��out�(�),证明对任意 u∈V�∈� 均有 S(u)=1�(�)=1。对于终点 t�,规定其到自身的空路径概率为 11,即 S(t)=1�(�)=1。对 DAG 按拓扑逆序进行归纳,假设节点 u� 的所有出边指向的节点 v∈N+(u)�∈�+(�) 均满足 S(v)=1�(�)=1。由全概率公式有 S(u)=∑v∈N+(u)pu,v⋅S(v)�(�)=∑�∈�+(�)��,�⋅�(�),代入归纳假设及上述设定 ∑v∈N+(u)pu,v=1∑�∈�+(�)��,�=1,可得 S(u)=∑v∈N+(u)pu,v⋅1=1�(�)=∑�∈�+(�)��,�⋅1=1。证毕。
因此有 Eout(u,v)(u)=pu,v(wu,v+Eout(v))�(�,�)out(�)=��,�(��,�+�out(�))。最后,将所有出边的贡献求和,即得Eout(u)=∑v∈N+(u)Eout(u,v)(u)=∑v∈N+(u)pu,v(wu,v+Eout(v))�out(�)=∑�∈�+(�)�(�,�)out(�)=∑�∈�+(�)��,�(��,�+�out(�))
与正确方法中的定义一致。
接下来用相同的思路剖析错误方法中的递推式。定义 Pinu��in 表示从起点 s� 到节点 u� 的所有路径构成的集合,子集 Pin(v,u)⊆Pinu�(�,�)in⊆��in 表示其中以边 (v,u)(�,�) 作为最后一条边的路径集合。对于任意 P∈Pin(v,u)�∈�(�,�)in,可拆分为 P=Ps⇝v⊕(v,u)�=��⇝�⊕(�,�),其中 Ps⇝v∈Pinv��⇝�∈��in 表示从 s� 到 v� 的前缀路径。
对于经过特定入边 (v,u)(�,�) 的期望贡献 Ein(v,u)(u)�(�,�)in(�),类似地有:
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)⎞⎟⎠�(�,�)in(�)=∑�∈�(�,�)in�(�)⋅�(�)=∑�∈�(�,�)in�(��⇝�⊕(�,�))⋅�(��⇝�⊕(�,�))=∑�∈�(�,�)in�(��⇝�)⋅��,�⋅(�(��⇝�)+��,�)=��,�(∑�∈�(�,�)in�(��⇝�)⋅�(��⇝�)+��,�∑�∈�(�,�)in�(��⇝�))=��,�(∑�∈��in�(�)⋅�(�)+��,�∑�∈��in�(�))=��,�(�in(�)+��,�∑�∈��in�(�))
在上述推导中,如果错误地假定 ∑P∈Pinvp(P)=1∑�∈��in�(�)=1,便会得到 Ein(v,u)(u)=pv,u(Ein(v)+wv,u)�(�,�)in(�)=��,�(�in(�)+��,�),进而汇总得出错误的递推式。事实上,∑P∈Pinvp(P)∑�∈��in�(�) 表示的是从起点 s� 出发最终恰好到达节点 v� 的所有路径概率之和。与“从 v� 必然到达终点 t�”这一必然事件不同,从 s� 出发的游走在每一步都有多种选择,到达某个特定的中间节点 v� 并非必然事件,因此该概率之和通常严格小于 11。
将其记为到达概率 π(u)=∑P∈Pinup(P)�(�)=∑�∈��in�(�),根据全概率公式容易得到其递推式 π(u)=∑v∈N−(u)pv,u⋅π(v)�(�)=∑�∈�−(�)��,�⋅�(�),其中初始条件为 π(s)=1�(�)=1。将 π(v)�(�) 代回先前的推导,才能得到真正正确的递推式Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u⋅π(v))�in(�)=∑�∈�−(�)��,�(�in(�)+��,�⋅�(�))
条件期望与绝对期望的混淆
从概率论的更本质视角来看,上述正推与倒推的差异,根源在于条件期望与绝对期望的混淆。在正向推导中,由于 π(v)=1�(�)=1 的归一化特性,给定当前状态的条件已被概率归一化所消化,因此看似未显式使用条件概率。而在反向推导中,归一化不再成立,混淆两者便会导致错误。
具体而言,Eout(u)�out(�) 本质上是一个条件期望,等价于 E[d(Pu⇝t)∣X0=u]�[�(��⇝�)∣�0=�]。由全期望公式展开得E[d(Pu⇝t)∣X0=u]=∑v∈N+(u)E[d(Pu⇝t)∣X1=v,X0=u]⋅P(X1=v∣X0=u)�[�(��⇝�)∣�0=�]=∑�∈�+(�)�[�(��⇝�)∣�1=�,�0=�]⋅�(�1=�∣�0=�)
其中条件转移概率 P(X1=v∣X0=u)�(�1=�∣�0=�) 恰好对应边 (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]�[�(��⇝�)∣�1=�,�0=�]=�[��,�+�(��⇝�)∣�0=�]=��,�+�[�(��⇝�)∣�0=�]
代回即得E[d(Pu⇝t)∣X0=u]=∑v∈N+(u)(wu,v+E[d(Pv⇝t)∣X0=v])⋅pu,v�[�(��⇝�)∣�0=�]=∑�∈�+(�)(��,�+�[�(��⇝�)∣�0=�])⋅��,�
其与 Eout(u)�out(�) 的递推式完全一致。
而对于反向推导,Ein(u)�in(�) 本质上是无条件的绝对期望 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)�in(�) 是绝对期望 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)�(��⇝�) 视为 00,故后半部分为 00,且 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)�in(�) 递推式一致。
总结
回顾最初错误的递推式 Ein(u)=∑v∈N−(u)pv,u(Ein(v)+wv,u)�in(�)=∑�∈�−(�)��,�(�in(�)+��,�),其错误根源在于推导中隐式地默认了 E[d(Ps⇝v)∣Av]=E[d(Ps⇝v)]�[�(��⇝�)∣��]=�[�(��⇝�)],即条件期望等于绝对期望。而该等式成立的唯一条件是 π(v)=1�(�)=1,即从起点必然走到节点 v�。在 Eout(u)�out(�) 的推导中,由于从任何节点出发必然到达终点 t�,概率归一化始终成立。但在 Ein(u)�in(�) 中,从起点出发并不一定经过 v�,π(v)�(�) 是一个小于 11 的概率,归一化条件不再满足,故不可随意将绝对期望与条件期望混为一谈。