08-网络上的随机游走（一）

回顾：可逆 Markov 链

如果存在概率测度 ，使得对所有 ，

则该 Markov 链可逆。

此时：

• 是平稳分布；
• 对任意 ，

本讲目标：电网络

• 网络、电导与电阻；
• 电压与电流；
• 有效电阻。

定义　网络是一个有限、无向、连通图

并为每条边赋予非负数

其中 称为边 的电导。

若

则把 写成

显然，

边 的电阻定义为

网络上的加权随机游走

定义　考虑顶点集 上的 Markov 链，其转移矩阵为

其中

这个过程称为图 上、边权为 的加权随机游走。

该 Markov 链关于概率测度

可逆，其中

事实上，

因此， 是 的平稳分布。

调和函数

设：

• ：状态空间；
• ：不可约转移矩阵。

如果函数

在状态 满足

则称 在 处是调和的。

固定 ，定义到达时间

定理　设 是转移矩阵为不可约矩阵 的 Markov 链， 是定义在 上的函数。定义

则 是 的唯一延拓，满足：

并且 在所有

处调和。

电压

定义　考虑网络

指定两个不同顶点：

• ：源点；
• ：汇点。

电压是顶点集 上的函数 ，并且它在

上调和。

注　电压由边界值

完全确定。

流

定义　设 是定义在有向边上的函数。 在顶点 处的散度定义为

定义　从 到 的一个流，是定义在有向边上的函数 ，满足：

1. 反对称性：

2. 节点定律：对所有

有

3.

从 到 的流 的强度定义为

强度为 1 的流称为单位流。

电流

定义　给定网络上的电压 ，与 对应的电流 定义为

电流满足：

1. Ohm 定律：

2. 回路定律：若有向边

构成一个有向回路，则

定理　如果 是从 到 的流，对每个回路都满足回路定律，并且

则

有效电阻

定义　给定网络，设 是电压， 是对应的电流。定义 与 之间的有效电阻为

定理（有效电阻与逃逸概率）　对任意 ，考虑网络上的加权随机游走，则

这里 是首次到达 的时间， 是离开初始状态 后首次返回 的时间。

有效电阻

定义　对在停时 停止的随机游走，其 Green 函数定义为

定理（有效电阻与 Green 函数）

该等式与上一页的逃逸概率公式互为倒数关系：每次从 出发，在到达 之前回到 的过程形成几何型重复访问。