图上随机游走中条件期望与绝对期望的混淆辨析

案例引入先引入一个简单的例子给定一个 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,vEout(v))out()∑∈(),(,out())其中 N(u)() 表示节点 u 的所有出边指向的节点集合pu,v, 是选择边 (u,v)(,) 的转移概率wu,v, 是边 (u,v)(,) 的权值。对应到上图中Eout(4)0out(4)0Eout(3)1.0×(00)0out(3)1.0×(00)0Eout(2)1.0×(10)1out(2)1.0×(10)1因此 Eout(1)0.5×(11)0.5×(10)1.5out(1)0.5×(11)0.5×(10)1.5。该结果的正确性可以通过枚举所有路径直观验证从起点 11 到终点 44 的所有可能路径仅有 11→21→41→12→14 与 11→30→41→13→04两者的发生概率均为 0.50.5由期望的定义可得期望距离为 0.5×20.5×11.50.5×20.5×11.5。再给出一种错误的解法。定义 Ein(u)in() 表示从起点 s 到达节点 u 的期望距离试图构造递推式Ein(u)∑v∈N−(u)pv,u(Ein(v)wv,u)in()∑∈−(),(in(),)其中 N−(u)−() 表示指向节点 u 的所有入边来源节点集合。对应到图中Ein(1)0in(1)0Ein(2)0.5×(01)0.5in(2)0.5×(01)0.5Ein(3)0.5×(01)0.5in(3)0.5×(01)0.5进而 Ein(4)1.0×(0.51)1.0×(0.50)2.0in(4)1.0×(0.51)1.0×(0.50)2.0。这与正确结果矛盾说明该递推方法有误。下面将通过严格的数学推导剖析这两种方法背后的逻辑差异。基于路径概率和的正误剖析首先对一般化场景给出前提设定图 G(V,E)(,) 是弱连通的有向无环简单图DAG。图中存在唯一的起点 s∈V∈ 与唯一的汇点即出度为 00 的节点记该汇点为终点 t。从图中任意节点出发沿边移动必然在有限步内到达 t。对于图中除 t 外的任意节点其所有出边上的转移概率之和恒为 11。求解从 s 到 t 的期望距离本质上是一个图上的随机游走问题。该过程满足离散时间马尔可夫链的无后效性P(Xn1∣Xnxn,Xn−1xn−1,…,X0x0)P(Xn1∣Xnxn)(1∣,−1−1,…,00)(1∣)即下一跳状态仅依赖于当前所在节点。结合上述设定此随机游走可建模为一个吸收马尔可夫链其中 t 为吸收态其余节点为瞬态且从任意瞬态出发均以概率 11 最终到达吸收态。定义 Poutuout 表示从 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)∈()可将 Poutuout 划分为 |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,vd(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,v1∑∈(),1可得 S(u)∑v∈N(u)pu,v⋅11()∑∈(),⋅11。证毕。因此有 Eout(u,v)(u)pu,v(wu,vEout(v))(,)out(),(,out())。最后将所有出边的贡献求和即得Eout(u)∑v∈N(u)Eout(u,v)(u)∑v∈N(u)pu,v(wu,vEout(v))out()∑∈()(,)out()∑∈(),(,out())与正确方法中的定义一致。接下来用相同的思路剖析错误方法中的递推式。定义 Pinuin 表示从起点 s 到节点 u 的所有路径构成的集合子集 Pin(v,u)⊆Pinu(,)in⊆in 表示其中以边 (v,u)(,) 作为最后一条边的路径集合。对于任意 P∈Pin(v,u)∈(,)in可拆分为 PPs⇝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)∣X0u][(⇝)∣0]。由全期望公式展开得E[d(Pu⇝t)∣X0u]∑v∈N(u)E[d(Pu⇝t)∣X1v,X0u]⋅P(X1v∣X0u)[(⇝)∣0]∑∈()[(⇝)∣1,0]⋅(1∣0)其中条件转移概率 P(X1v∣X0u)(1∣0) 恰好对应边 (u,v)(,) 的转移概率 pu,v,。根据马尔可夫性E[d(Pu⇝t)∣X1v,X0u]E[wu,vd(Pv⇝t)∣X0v]wu,vE[d(Pv⇝t)∣X0v][(⇝)∣1,0][,(⇝)∣0],[(⇝)∣0]代回即得E[d(Pu⇝t)∣X0u]∑v∈N(u)(wu,vE[d(Pv⇝t)∣X0v])⋅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,upv,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 的概率归一化条件不再满足故不可随意将绝对期望与条件期望混为一谈。