11-网络上的随机游走总结

有效电阻

考虑网络

设 是一个电势，源点为 ，汇点为 。令 为相应的电流：

定义 与 之间的有效电阻为

有效电阻与逃逸概率

有效电阻与格林函数

三种运算

仍以

定义 与 之间的有效电阻。

下列三种运算不改变有效电阻：

• 并联定律：并联支路的电导相加。
• 串联定律：串联支路的电阻相加。
• 粘合：把电势相同的顶点识别为同一个顶点。

有效电阻的估计

有效电阻与流的能量

由此得到以下推论。

• 若对每条边 都有 ，则

• 上界：对任意从 到 的单位流 ，都有

• **下界：Nash–Williams 不等式。**设 是彼此边不相交、并且都将 与 分开的割边集，则

网络上的随机游走

考虑网络

上的随机游走。

• 转移矩阵为

• 该链是可逆的。
• 平稳测度为

• 定义往返时间

• 往返时间恒等式

• 若网络是顶点传递的，则

特别地，

二叉树上的随机游走

• 树是没有环的连通图。
• 有根树有一个特别指定的顶点 ，称为根。
• 顶点 的深度是它到根的图距离。
• 叶子是度数为 的顶点。

深度为 的有根二叉树记作 。它是一棵以 为根的树，并满足：

• 的度数为 ；
• 对 ，到根距离为 的每个顶点的度数都是 ；
• 到根距离为 的顶点都是叶子，它们的度数为 。

图示：一棵深度为 的有根二叉树。根位于最上方；每个非叶顶点向下分出两个子顶点，最下层顶点为叶子。

二叉树上的随机游走

• 是一个网络；
• 每条边的电阻都是 ；
• 顶点总数为

• 边数为 。

图示：深度为 的有根二叉树，所有边均视为单位电阻。

定理

考虑该网络上的随机游走 。令 为叶子集合。定义往返时间

环面上的随机游走

二维环面定义为

两个顶点

相邻，当且仅当满足下列两种情形之一：

这是一个网络，并假设所有边的电阻均为 。

图示：将方格网格的相对边分别粘合后得到的二维环面。

定理

设 ，并令

存在常数 $0

环面上的随机游走

图示：二维离散环面的一块方格表示。顶点 位于中部偏左，顶点 位于其右下方，顶点 位于其右上方；粗线分别连接 与 、 与 ，用来示意环面上两点间路径及距离的比较。

2015 年春季