和之前一样，我们还是通过一个有趣的问题来引入主题。

问题：在 \(n\times n\) 的正方形网格图 \(G_n\) 的所有生成树中等概率地随机任选一个，记这个随机生成树为 \(T\)，\(T\) 叫做 \(G_n\) 的一个均匀生成树。对 \(G_n\) 中任一顶点 \(v\)，\(v\) 是 \(T\) 的叶节点的概率是多少？

这个问题可以换一种更通俗的描述：

等价问题：对一个完全随机的 \(n\times n\) 的完美迷宫，它包含的“死角”的比例是多少？

为什么这两个问题是一回事？

一个迷宫称作是完美的，如果迷宫中的任何两个房间之间都有且仅有唯一的道路相连，这正是生成树的等价描述！迷宫中的一个房间称作是“死角”，当且仅当它只有一条道路与其它房间相通，没有其它出路，这正是叶节点的等价描述！

下图显示了三个不同的均匀生成树，它们分别来自大小为 \(80\times 80\)，\(120\times120\) 和 \(200\times200\) 的三个网格图，这三个生成树的叶节点（用蓝色标出）占全体顶点的比例分别为 \(1884/6400=0.294375\)，\(4234/14400\approx0.294028\)，\(11776/40000=0.2944\)。咦？看起来好像是在围着一个固定的值波动喔？

80x80, 0.294375	120x120, 0.294028	200x200, 0.2944

本文的主题就是证明对 \(G_n\) 的一个均匀生成树 \(T\)，\(T\) 包含的叶节点的比例随着 \(n\) 趋于无穷收敛到常数 \(8(\pi-2)/\pi^3\approx 0.2945449\) （想不到 \(\pi\) 会出现在这里吧？）。可见上面三个模拟的数值与真实的极限值已经非常接近。

实际上对于度数是 \(2,3,4\) 的顶点，它们的比例也随着 \(n\to\infty\) 趋于固定的值，详细结果见下表：

度数	极限概率	近似值
1：死角	\[\dfrac{8}{\pi^2}\left(1-\dfrac{2}{\pi}\right)\]	0.294
2：拐角 + 直路	\[\dfrac{4}{\pi}\left(2-\dfrac{9}{\pi}+\dfrac{12}{\pi^2}\right)\]	0.447
3：岔路	\[2\left(1-\dfrac{2}{\pi}\right)\left(1-\dfrac{6}{\pi}+\dfrac{12}{\pi^2}\right)\]	0.222
4：十字路口	\[\left(\dfrac{4}{\pi}-1\right)\left(1-\dfrac{2}{\pi}\right)^2\]	0.036

所以在一个随机的完美迷宫中，最多的其实是“拐角” 和“直路” (45%)，其次是“死角” (30%)，再次是“丁字岔路” (22%)，而“十字路口”是非常少的 (3.6%)。进一步也不难算出拐角和直路的极限概率分别为 \((32-20\pi+4\pi^2)/\pi^3\approx 0.279\) 和 \((16-16\pi+4\pi^2)/\pi^3\approx 0.168\)。

这些概率是怎样计算出来的呢？它和我们这个系列的主题二维随机游动又有何关系呢？这里面的故事相当精彩。粗略地说，上面这些关于随机生成树的概率量，都可以翻译为图上随机游动的概率量，把整个图看做一个电网络，它们又可以翻译为这个电网络的物理量，而这些物理量是可以用各种方法（主要是线性代数）来算的。上面提到的这些概率值都可以从一个矩阵出发通过求其主子式得到 （或者稍微加点变化），这个矩阵叫做转移电流矩阵 (transfer current matrix)，其定义为：对给定的图 \(G\)，将 \(G\) 看作一个电网络，每条边的电阻都是单位 1。在其中一条边 \(e\) 的两端加上电极，使得流入整个网络的电流总量为 1 个单位，记此时流过边 \(e'\) 的电流总量为 \(Y(e,e')\)，则矩阵 \(Y=Y(e,e')_{e,e'\in E}\) 叫做网络 \(G\) 的转移电流矩阵。

对 \(G\) 的任何 \(k\) 条边 \(e_1,\ldots,e_k\)，定义 \(k\times k\) 矩阵 \(Y^{(k)}\) 为 \(Y^{(k)}(i,j)=Y(e_i,e_j)\)，则我们有如下结论 （转移电流矩阵定理）：设 \(T\) 是一个随机生成树，则边 \(e_1,\ldots,e_k\) 都属于 \(T\) 的概率 \[\mathbb{P}(e_1,\ldots,e_k \in T)=\det Y^{(k)}.\] 举个例子，\(\mathbb{Z}^2\) 中与原点 \((0, 0)\) 相邻的四条边为 \(e_1=(1,0)\)，\(e_2=(0, 1)\)，\(e_3=(-1,0)\)，\(e_4=(0, -1)\)，我们后面会计算出这四条边对应的转移电流矩阵为

\[ Y^{(4)}= \begin{pmatrix} \frac{1}{2} & \frac{1}{2}-\frac{1}{\pi} & \frac{2}{\pi}-\frac{1}{2} & \frac{1}{2}-\frac{1}{\pi}\\ \frac{1}{2}-\frac{1}{\pi} & \frac{1}{2} & \frac{1}{2}-\frac{1}{\pi} & \frac{2}{\pi}-\frac{1}{2}\\ \frac{2}{\pi}-\frac{1}{2} & \frac{1}{2}-\frac{1}{\pi} & \frac{1}{2} & \frac{1}{2}-\frac{1}{\pi}\\ \frac{1}{2}-\frac{1}{\pi} & \frac{2}{\pi}-\frac{1}{2} & \frac{1}{2}-\frac{1}{\pi} & \frac{1}{2} \end{pmatrix}. \]

于是原点的度数等于 4 的概率是 \[\mathbb{P}(e_1,e_2,e_3,e_4\in\mathbb{T})=\det Y^{(4)}=\left(\frac{4}{\pi}-1\right)\left(1-\frac{2}{\pi}\right)^2\approx 0.0361.\] 这正是上面列出的十字路口的概率！

如果是计算概率 \(\mathbb{P}(e_1,e_2,e_3\notin T, e_4\in T)\) 呢？方法如下，把要排除掉的 \(e_1,e_2,e_3\) 对应的 \(Y^{(4)}\) 的前三行全部取负值，并且给前三个对角元加上 1，保持第 4 行不变，得到

\[ Y^{(4)}_{\overline{123}4}=\begin{pmatrix} \frac{1}{2} & \frac{1}{\pi}-\frac{1}{2} & -\frac{2}{\pi}+\frac{1}{2} & \frac{1}{\pi}-\frac{1}{2}\\ \frac{1}{\pi}-\frac{1}{2} & \frac{1}{2} & \frac{1}{\pi}-\frac{1}{2} & -\frac{2}{\pi}+\frac{1}{2}\\ -\frac{2}{\pi}+\frac{1}{2} & \frac{1}{\pi}-\frac{1}{2} & \frac{1}{2} & \frac{1}{\pi}-\frac{1}{2}\\ \frac{1}{2}-\frac{1}{\pi} & \frac{2}{\pi}-\frac{1}{2} & \frac{1}{2}-\frac{1}{\pi} & \frac{1}{2}\end{pmatrix}. \]

则 \[\mathbb{P}(e_1,e_2,e_3\notin T, e_4\in T)=\det Y^{(4)}_{\overline{123}4}=\frac{2}{\pi^2}-\frac{4}{\pi^3}.\] 于是原点是叶节点的概率是 \(4\times\det Y^{(4)}_{\overline{123}4}\approx 0.2945\)，这正是之前看到的死角的比例。

所以解决问题的关键就是求解 \(\mathbb{Z}^2\) 上的转移电流矩阵，本文接下来就来介绍具体的理论。这个故事并无特别的难点，但确实比较长。我主要参考了 Lyons 等人关于图随机游动的专著 ¹，Stanley 的代数组合学教材 ² 以及网上一些公开的讲义。

1 图上的线性代数

一个网络 \(\mathcal{N}=(G, c)\) 由一个有限图 \(G=(V,E)\) 和一个权值函数 \(c:E\to\mathbb{R}_{\geq0}\) 组成。这里 \(G\) 是连通的无向图，其每条边 \(e\in E\) 有一个权值 \(c(e)\in[0, +\infty)\)，叫做 \(e\) 的电导，其倒数 \(r(e)=1/c(e)\) 叫做 \(e\) 的电阻。

设 \(x,\,y\in V\) 是两个顶点，我们用 \(x\sim y\) 表示 \(x,y\) 是相邻的。由于本文主要考察边上的流函数，而流函数是有方向的，所以我们约定边集 \(E\) 同时包含有序对 \((x,y)\) 和 \((y,x)\)，即一条边作为有序对在 \(E\) 中出现两次。当 \(e=(x,y)\) 时，我们记 \(-e=(y,x)\) 为 \(e\) 的反向边。并用记号 \(E_{1/2}\) 表示对每个 \(e\)，在 \(e\) 和 \(-e\) 中任选一个组成的集合。\(E_{1/2}\) 的一个选取方式对应 \(E\) 的一个定向，不过我们一般不必明确写出这个选取方式。此外当 \(e=(x,y)\) 时，我们称 \(e^-=x\) 为 \(e\) 的尾部，\(e^+=y\) 为 \(e\) 的头部。为了记住这一点，你可以把 \(e\) 想象成一个从 \(x\) 到 \(y\) 的箭头：\(x\xrightarrow{e}y\)。注意在反向边 \(-e\) 中 \(x\) 变为头部，\(y\) 变为尾部。

对每个 \(e\in E\)，当 \(e=(x,y)\) 时我们也记 \(c(x,y)=c(e)\)。我们要求电导函数 \(c(x,y)\) 关于 \(x,y\) 是对称的：\(c(x,y)=c(y,x)\)。所以当写 \(c(e)\) 的时候我们不用关心 \(e\) 的定向。对每个顶点 \(x\in V\)，记 \(c(x)=\sum_{y\sim x}c(x,y)\)。

所有 \(V\) 上的实值函数 \(f:V\to\mathbb{R}\) 构成一个内积空间 \(\ell^2(V)\)： \[(f,\, g)_V = \sum_{x\in V}c(x)f(x)g(x).\]

所有 \(E\) 上的反对称实值函数 \(\theta: E\to\mathbb{R}\) 也构成一个内积空间 \(\ell^2_{-}(E)\)： \[(\theta,\,\theta')_E = \frac{1}{2}\sum_{e\in E}r(e)\theta(e)\theta'(e)=\sum_{e\in E_{1/2}}r(e)\theta(e)\theta'(e).\] 这里反对称的意思是对任何 \(e=\{x,y\}\) 有 \(\theta(x, y)=-\theta(y,x)\)。注意上式右边的求和与边的定向是无关的，如果换成 \(-e\) 的话乘积 \(\theta(e)\theta'(e)\) 还是不变的，即内积的定义与 \(E_{1/2}\) 的选取方式无关。

以上定义基本上与 Lyons 等人的书保持一致，但是接下来的叙述会有比较大的差别。

梯度和散度

定义 1.1：

1. 定义梯度算子 \(\nabla: \ell^2(V)\to\ell^{2}_{-}(E)\) 为 \[(\nabla f)(x,y) = c(x, y)\big[f(x)-f(y)\big]=c(e)\big[f(e^-)-f(e^+)\big].\] 如果把 \(f\) 理解为每个顶点处的电压的话，梯度算子给出的是电压之差除以电阻值，即经过边 \(e\) 的有向电流。

2. 定义散度算子 \(\mathrm{div}:\ell^{2}_{-}(E)\to\ell^2(V)\) 为 \[(\mathrm{div}\,\theta)(x) = \frac{1}{c(x)}\sum_{y\sim x}\theta(x, y)=\frac{1}{c(x)}\sum_{e^-=x}\theta(e).\] 上式右边可能有的求和项大于 0，有的小于 0。如果把 \(\theta\) 理解为每条边上的有向电流的话，散度算子给出的是每个顶点处的净流出量。

3. 定义拉普拉斯算子 \(\Delta:\ell^2(V)\to\ell^{2}(V)\) 为 \[ (\Delta f)(x) = (\mathrm{div}\,\nabla f)(x) = f(x)-\sum_{y\sim x}\frac{c(x,y)}{c(x)}f(y). \] 如果 \((\Delta f)(x)=0\) 对 \(x\in V\) 成立，我们就称 \(f\) 在 \(x\) 处是调和的。

定理 1.1：梯度算子和散度算子是一对共轭算子：对任何 \(f\in\ell^2(V)\) 和 \(\theta\in\ell_{-}^2(E)\) 有 \[(f,\,\mathrm{div}\,\theta)_V = (\nabla f,\,\theta)_E.\]

证明：上式对 \(f\) 是线性的，所以我们只要对形如 \(\mathbb{1}_{\{ x \}},x\in V\) 的元素验证即可。这时左边是 \(c(x)\cdot(\mathrm{div}\,\theta)(x)\)，右边是 \(\sum_{y\sim x}\theta(x,y)\)，二者当然相等。\(\blacksquare\)

定义 1.2：我们称映射 \(\mathrm{div}\) 的核 \(\mathrm{Ker\,div}\) 为环空间 (cycle space)，记作 \(\lozenge\)。称映射 \(\nabla\) 的像 \(\mathrm{Im}\nabla\) 为星空间 (star space)，记作 \(\bigstar\)。环空间和星空间都是 \(\ell_{-}^2(E)\) 的子空间。

定理 1.2：\(\ell_{-}^2(E)\) 是环空间和星空间的正交直和：\(\ell_{-}^2(E)=\lozenge\oplus\bigstar\)。

证明：由于 \(\{\mathbb{1}_{\{ x \}},x\in V\}\) 构成 \(\ell^2(V)\) 的一组基，所以它们在 \(\nabla\) 下的像构成 \(\bigstar\) 的一组基。从定理 1.1 的证明中我们已经看到对任何 \(\theta\in\ell^2_{-}(E)\) 有 \[(\nabla \mathbb{1}_{\{ x \}},\,\theta)_E=c(x)(\mathrm{div}\,\theta)(x).\] 于是 \(\theta\) 与任何 \(\nabla \mathbb{1}_{\{ x \}}\) 正交当且仅当 \((\mathrm{div}\,\theta)(x)=0\) 对任何 \(x\in V\) 成立，即当且仅当 \(\theta\in\lozenge\)，从而 \(\lozenge\) 和 \(\bigstar\) 互为正交补空间，证毕。

环空间和星空间的解释

我们来解释一下为什么这两个子空间叫做“环空间”和“星空间”。

首先是环空间。对任一 \(e\in E\)，记 \[\chi^e=\mathbb{1}_{\{ e \}} - \mathbb{1}_{\{ -e \}}\in\ell^2_{-}(E)\] 为边 \(e\) 的示性函数，即 \(\chi^e\) 在 \(e\) 和 \(-e\) 上取值分别为 \(\pm1\)，在其它边上都是 0。

显然 \(\chi^{e}=-\chi^{-e}\)。

设 \(e_1=(v_1,v_2), e_2=(v_2,v_3),\ldots,e_k=(v_k,v_1)\) 首尾相接构成一条回路 \(C\)，即 \[v_1\xrightarrow{\quad e_1 \quad}v_2\xrightarrow{\quad e_2 \quad}\cdots\xrightarrow{\quad e_{k-1} \quad}v_k\xrightarrow{\quad e_k \quad}v_1.\]

定义 \(C\) 对应的环函数 \(f^C = \sum_{i=1}^k\chi^{e_i}\)，则从 \(v_1\) 出发绕 \(C\) 一圈一路上经过的所有边 \(f\) 的值都是 \(+1\) （沿着反方向绕都是 \(-1\))，于是 \(f^C\) 在 \(C\) 包含的每个顶点上 1 进 1 出，在 \(C\) 之外的顶点上 0 进 0 出，从而 \(f^C\in\lozenge\)。反之，我们断言 \(\lozenge\) 可以由所有的环函数 \(f^C\) 张成，这就是为什么 \(\lozenge\) 叫做环空间。

设 \(\theta\in\lozenge\)，定义 \(\theta\) 的支集为 \[\mathrm{supp}(\theta)=\{e\in E\mid\theta(e)\ne0\}.\] 如果 \(\mathrm{supp}(\theta)\) 非空，则它必然包含一个回路，否则 \(\mathrm{supp}(\theta)\) 构成的子图中必然有一个叶顶点 （度数恰好为 1)，从而这一点处的散度不可能为 0，矛盾！于是 \(\mathrm{supp}(\theta)\) 包含一个回路 \(C\)，我们可以选择合适的常数 \(\alpha\) 使得 \(\widetilde{\theta}=\theta-\alpha f^C\) 在某个 \(e\in C\) 上为 0，则 \(\widetilde{\theta}\) 的支集严格小于 \(\theta\)。对 \(\widetilde{\theta}\) 重复此操作一直下去必然可以在有限次后将支集变为空集，这就证明了 \(\theta\) 可以表示为形如 \(f^C\) 的线性组合。

星空间也有一个类似的形象描述。对每个顶点 \(x\)，我们也有一个 \(\ell^2_{-}(E)\) 上的函数与之对应：\(\sum_{e^-=x}c(e)\chi^e\)。这个函数很直观，它的支集是从 \(x\) 出发伸出去的星状结构。

对任何 \(\theta\in\ell^2_{-}(E)\)，我们有 \[(\mathrm{div}\,\theta)(x)=\sum_{e^-=x}\theta(e)=\sum_{e^-=x}\left(c(e)\chi^e,\theta\right)_E=\left(\sum_{e^-=x}c(e)\chi^e,\theta\right)_E.\] 由于 \(\theta\in\lozenge\) 当且仅当 \((\mathrm{div}\,\theta)(x)=0\) 对所有 \(\in V\) 成立，也就是 \(\theta\) 与所有 \(\sum_{e^-=x}c(e)\chi^e\) 正交，所以我们证明了 \(\left\{\sum_{e^-=x}c(e)\chi^e\mid x\in V\right\}\) 可以生成 \(\bigstar\)。

补充阅读

这一节一下出现了好几个算子，以及环空间和星空间的概念，对初次接触的人来说有点名词爆炸，所以这里补充一段阅读材料：

我们在高中物理所学的基尔霍夫定律（电流、电压）是基尔霍夫于 1845 年发表的，那时他只有 21 岁。两年后的 1847 年基尔霍夫发表了另一篇文章，系统阐述了怎样用求解线性方程组的方法计算电路中的电流。第二篇文章很有意思，基尔霍夫证明了在一个有 \(v\) 个中间节点和 \(e\) 条边的电路中，我们可以对每个中间节点列出一个方程（流入=流出），这样得到的 \(v\) 个方程是线性相关的，但是删掉任何一个方程以后剩下的 \(v-1\) 个方程都是线性无关的；此外我们还可以对每个“基本回路”列出一个方程（电压绕回路一圈改变为 0），得到 \(\mu\) 个线性方程，其中 \(\mu\) 是电路包含的“基本回路”的个数。这 \(\mu\) 个方程和前面 \(v-1\) 个方程合起来仍然是线性无关的，于是我们就有了 \(\mu+v-1\) 个独立的方程，这些方程就足以解出所有边上的电流！

什么是基本回路？直观上理解很容易：下图标注了 \(\alpha,\beta,\gamma\) 三个基本回路，它们不能拆解为更小回路的组合：

基本回路的准确定义是，取 \(G\) 的一个生成树 \(T\)，则对任何 \(e\in G\backslash T\)，将 \(e\) 加入 \(T\) 以后都会形成某个回路 \(\chi^e\)，\(\chi^e\) 就是一个基本回路。

1. 由于 \(T\) 包含 \(v-1\) 条边，所以 \(G\backslash T\) 有 \(e-v+1\) 条边，所以这样的回路有 \(e-v+1\) 个。
2. 这 \(e-v+1\) 个回路是线性无关的，因为它们当中任何一个都不能表示为其它回路的线性组合。这是因为，假设基本回路 \(\chi^e\) 是由 \(T\cup\{e\}\) 得到的，由于其它回路的支集都不含 \(e\)，所以它们的组合的支集也不会包含 \(e\)。
3. 于是环空间 \(\lozenge\) 中包含 \(e-v+1\) 个线性无关的回路，从而 \(\dim\lozenge\geq e-v+1\)。
4. 我们来证明 \(\dim\bigstar=v-1\)，于是由 \(\dim\ell^2_{-}(E)=e\) 即得 \(\dim\lozenge= e-v+1\)。这是因为 \(\mathrm{Ker}\,\nabla\) 显然是 1 维的：它由所有 \(V\) 上的常函数构成，所以 \[\dim\bigstar=\dim\ell^2(E)-\dim\mathrm{Ker}\,\nabla=v-1.\]

总结一下：

1. 环空间的维数是 \(\dim\bigstar=e-v+1\)，由基本回路张成，对每一个基本回路可以利用电压定律列一个独立方程。
2. 星空间的维数是 \(v-1\)，由任何 \(v-1\) 个中间节点张成，对这 \(v-1\) 个顶点中的每一个都可以用电流定律列一个独立方程。

1, 2 合起来正好可以解出全部 \(e\) 条边上的电流！

2 网络中的流

流和电流

仍然设 \(\mathcal{N}=(G,c)\) 是一个网络，\(Z\) 是 \(V\) 的一个子集，\(a\notin Z\) 是一个顶点。

定义 2.1：我们称 \(\theta\in\ell_{-}^2(E)\) 是一个从 \(a\) 到 \(Z\) 的流，如果以下两个条件成立：

1. \((\mathrm{div}\,\theta)(a)\geq 0\)。
2. 对任何 \(x\notin \{a\}\cup Z\) 有 \((\mathrm{div}\,\theta)(x)=0\)。

\(a\) 叫做 \(\theta\) 的源点，\(Z\) 叫做 \(\theta\) 的汇点。

定义流 \(\theta\) 的强度为从源点 \(a\) 流入网络的量： \[\mathrm{strength}(\theta)=\sum_{x\sim a}\theta(a, x).\] 我们也把 \(\mathrm{strength}(\theta)\) 记作 \(\|\theta\|\)，如果有 \(\|\theta\|=1\) 成立，就称 \(\theta\) 是一个单位流。

此外定义 \(\theta\) 的能量为 \[\mathcal{E}(\theta)=(\theta,\,\theta)_E.\]

此定义自动蕴含了 \(\sum_{z\in Z}(\mathrm{div}\,\theta)(z)=-(\mathrm{div}\,\theta)(a)\leq0\)：考虑 \(V\) 上的常函数 \(1\)，则 \(\nabla 1=0\)，于是 \[0=(\nabla 1,\,\theta)_E=(1,\,\mathrm{div}\,\theta)_V=(\mathrm{div}\,\theta)(a)+\sum_{z\in Z}(\mathrm{div}\,\theta)(z).\] 即对整个网络来说，从 \(a\) 流出的量等于流入 \(Z\) 的量，中间没有任何“淤积”。

定义 2.2：设 \(\theta\) 是一个从 \(a\) 到 \(Z\) 的流，如果还有 \(\theta=\nabla g\in\bigstar\) 成立，就称 \(\theta\) 是一个电流，\(g\) 叫做 \(\theta\) 的电势。

我们总结一下流和电流的特点：

1. 你可以把 \(a\) 理解为电源正极，\(Z\) 理解为网络接地的部分。
2. 流函数要求对任何 \(x\notin \{a\}\cup Z\) 有 \((\mathrm{div}\,\theta)(x)=0\) 等价于物理中的基尔霍夫电流定律：任何中间节点的流量守恒。
3. 电流函数要求 \(\theta=\nabla g\in\bigstar\) 等价于物理中的欧姆定律，即电流 \(\theta\) 等于电势差除以电阻 \(r(e)\)。

转移电流矩阵

在本文中，我们最关心的电流函数是将一条边 \(e=\{x,y\}\) 的端点 \(x\) 通入单位电流，另一端点 \(y\) 接地时网络中对应的电流函数，此函数记作 \(i^e\)。对任一边 \(e'\)，\(i^e(e')\) 就是此时流过 \(e'\) 的电流量。

证明：显然 \(\chi^e\) 是从 \(x\) 到 \(y\) 的单位流，且在任何 \(z\notin e\) 处散度为 0。\(\chi^e\) 在 \(\bigstar\) 的投影是通过减去一个 \(\mathrm{div}\) 处处为 0 的流得到的，这不改变任何顶点处的散度值，所以投影分量仍然是从 \(x\) 到 \(y\) 的单位流且在任何 \(z\notin e\) 处散度为 0。又由于投影分量属于 \(\bigstar\) 所以还满足欧姆定律，从而必然是电流 \(i^e\)。\(\blacksquare\)

证明：记 \(P_\bigstar\) 为从 \(\ell^2_{-}(E)\) 到 \(\bigstar\) 的投影算子，则 \(P_\bigstar\) 是自共轭算子以及 \(P_\bigstar^2=P_\bigstar\)，从而 \[(i^e, i^{e'})_E=(P_\bigstar\chi^e,P_\bigstar\chi^{e'})_E=(P_\bigstar\chi^e,\chi^{e'})_E=(i^e,\chi^{e'})_E=r(e')i^e(e').\] 即得结论。\(\blacksquare\)

证明：设 \(f,g\) 是任何这样的两个单位流，则 \(f-g\) 处处净流量为 0，即 \(f-g\in\lozenge\)，从而 \(P_\bigstar f = P_\bigstar g = i\)，所以电流 \(i\) 是唯一确定的。注意到 \((i, f-i)_E=0\)，所以 \[\mathcal{E}(f)=(f,\,f)_{E} = (i,i)_{E} + (f-i,f-i)_{E}\geq (i,i)_{E}=\mathcal{E}(i).\] 于是我们证明了电流能量的最小性。为了证明它等于 \(x,\, y\) 之间的等效电阻，可以利用 \[(i,i)_E = (i, \chi^e)_E = r(x,y)i(x,y)\chi^e(x,y) = r(x,y)i(x,y)= U(x)-U(y).\] 其中 \(U(x)-U(y)\) 是 \(x,\,y\) 之间的电势差，而流入网络的总电流是 1，所以这个电势差等于网络的等效电阻。

由此结论可以进一步得出 Rayleigh 单调原理：如果把一个网络的电阻调低的话，则原来的单位电流会变成一个能量更小的单位流，而此单位流的能量又大于等于新网络对应的单位电流的能量，所以新网络的等效电阻相比之前是下降的。

3 概率解释

在这一节中，我们会给出电势、电流对应的概率解释。假设 \(a\) 是一个顶点，\(Z\) 是一个顶点集合且 \(a\notin Z\)。

• 我们考虑从一点 \(x\) 出发，转移概率为 \(P(x,y)=c(x,y)/c(x)\) 的随机游动 \(\{X_t,t\geq0\}\)，其中 \(X_0=x\)。这个随机游动是可逆的 Markov 链，以 \(\{c(x),x\in V\}\) 为平稳测度：\(c(x)P(x,y)=c(y)P(y,x)\)。

• 我们同时考虑在 \(a\) 点接上电源正极，并将 \(Z\) 接地，则电流从 \(a\) 流入并从 \(Z\) 流出。我们将建立随机游动和这一电网络之间的联系。

电压的概率解释 （第一种）

电压有一个很简单的解释，它是直线上随机游动中赌徒获胜/破产概率的类比。

考虑从 \(x\) 出发的随机游动，设 \(\tau_a\) 是这一随机游动首次到达 \(a\) 点的时间 （类比赌徒获胜），\(\tau_Z\) 是这一随机游动首次到达集合 \(Z\) 的时间 （类比赌徒输光），并考虑概率 \[h(x) = \mathbb{P}_x(\tau_a<\tau_Z).\] 其中我们规定 \(h(a)=1, h(Z)=0\)，则 \(h(x)\) 在任何 \(x\notin \{a\}\cup Z\) 上是调和的： \[h(x) = \sum_{y\sim x}P(x, y)h(y).\] 此即为全概率公式，下一步到某个 \(y\sim x\) 的概率是 \(P(x,y)\)，从 \(y\) 继续出发获胜的概率是 \(h(y)\)，求和即可。

现在假设 \(a\) 点加上的电压大小是 1，则其电势 \(v(a)=1\)，由于 \(Z\) 接地所以 \(v(Z)=0\)。我们断言电势函数 \(v(x)\) 在任何一点 \(x\notin\{a\}\cup Z\) 处也是调和的： \[v(x) = \sum_{y\sim x}P(x, y)v(y).\] 这是因为设 \(v\) 对应的电流是 \(i\)，则

\[ \begin{align*} v(x) - \sum_{y\sim x}P(x, y)v(y)&= \sum_{y\sim x}P(x, y)(v(x)-v(y))\\&= \sum_{y\sim x}\frac{c(x,y)}{c(x)}i(x,y)r(x,y)\\&= \frac{1}{c(x)}\sum_{y\sim x}i(x,y)\\&= 0. \end{align*} \]

其中最后一个等号是根据基尔霍夫定律对任何中间节点 \(x\) 有 \((\mathrm{div}\,i)(x)=0\)。

现在获胜概率 \(\mathbb{P}_x(\tau_a<\tau_Z)\) 和电势函数 \(v(x)\) 在 \(\{a\}\cup Z\) 上有相同的边界条件，在 \((\{a\}\cup Z)^c\) 上都是调和的，则它俩必然是同一个函数！（提示：考虑两个函数之差并利用有限图上的调和函数必然在边界上取得最大最小值） 于是我们得到

电压的概率解释：在 \(a\) 加上单位 1 的电压，将 \(Z\) 接地，则任一顶点 \(x\) 处的电势等于从 \(x\) 出发的随机游动在到达 \(Z\) 之前先到达 \(a\) 的概率：\(v(x)=\mathbb{P}_x(\tau_a<\tau_Z)\)。

如果 \(a\) 处不是单位电压的话，则结论中的 \(v(x)\) 应替换为 \(v(x)/v(a)\)。

电阻、电压 （第二种）、电流的概率解释

在这一节中，我们将使用 Green 函数给出电流的概率解释，以及电压的第二种解释。

Green 函数是图上拉普拉斯算子的“基本解”，用它可以表示出一般的带边界条件的调和函数。

记 \(\mathbb{P}(a\to Z)=\mathbb{P}_a(\tau_Z < \tau_a^+)\) 为从 \(a\) 出发的随机游动在返回 \(a\) 之前先到达 \(Z\) 的概率。此概率称作从 \(a\) 到 \(Z\) 的逃逸概率。

仍然在 \(a\) 处加上电压，\(Z\) 接地，考虑此网络的电势 \(v\) 和电流 \(i\)。

引理 3.1： \[\frac{v(a)}{\| i\|} = \frac{1}{c(a)\mathbb{P}(a\to Z)}.\]

注意 \(v(a)/\|i\|\) 正是网络的等效电阻。

证明：

\[ \begin{align*} \mathbb{P}(a\to Z) &= \sum_{x\sim a}P(a, x)\mathbb{P}_x(\tau_Z < \tau_a)\\&= \sum_{x\sim a}\frac{c(a,x)}{c(a)}\left(1-\frac{v(x)}{v(a)}\right)\\&= \sum_{x\sim a}\frac{c(a,x)}{c(a)}\frac{v(a)-v(x)}{v(a)}\\&= \sum_{x\sim a}\frac{i(a,x)}{c(a)v(a)}\\&= \frac{\|i\|}{c(a)v(a)}. \end{align*} \]

\(\blacksquare\)

对任何边 \(x\sim y\)，定义随机变量 \(N_{x\to y}^Z\) 为从 \(a\) 出发的随机游动在访问 \(Z\) 之前从 \(x\) 走到 \(y\) 的次数，则我们有如下定理：

证明：

1. 首先边界条件给出了 \(\mathcal{G}_Z(a, Z)=0\)。此外 \(\mathcal{G}_Z(a, a)\) 是一个每次试验成功概率为 \(\mathbb{P}(a\to Z)\) 的几何分布的随机变量的期望，故 \[\mathcal{G}_Z(a, a)=\frac{1}{\mathbb{P}(a\to Z)},\] 再由上面的引理，有 \[\frac{\mathcal{G}_Z(a, a)}{c(a)}=\frac{1}{c(a)\mathbb{P}(a\to Z)}=v(a).\] 所以 \(\mathcal{G}_Z(a, x)/c(x)\) 在边界上与电势函数是一致的，只要再证明在任意中间节点 \(x\) 的调和性质。注意随机游动必然是从与 \(x\) 相邻的顶点走过去访问 \(x\)，所以 \[\frac{\mathcal{G}_Z(a, x)}{c(x)}=\frac{1}{c(x)}\sum_{y\sim x}\mathbb{E}_a[N_{y\to x}^Z].\] 另一方面

   \[ \begin{align*} \mathbb{E}_a[N_{y\to x}^Z]&= \mathbb{E}_a\left[\sum_{0\leq t<\tau_Z}\mathbb{1}_{\{ X_t=y,X_{t+1}=x \}}\right]\\&= \sum_{0\leq t<\tau_Z}\mathbb{P}\left[X_t=y,X_{t+1}=x\right]\\&= \sum_{0\leq t<\tau_Z}\mathbb{P}(X_t=y)P(y,x)\\&= P(y,x)\mathbb{E}_a\left[\sum_{0\leq t<\tau_Z}\mathbb{1}_{\{ X_t=y \}}\right]\\&= P(y,x)\mathcal{G}_Z(a,y). \end{align*} \label{eq:cross} \]

   所以代入求和后有

   \[ \frac{1}{c(x)}\sum_{y\sim x}\mathbb{E}_a[N_{y\to x}^Z]=\frac{1}{c(x)}\sum_{y\sim x}P(y,x)\mathcal{G}_Z(a,y)=\sum_{y\sim x}P(x,y)\frac{\mathcal{G}_Z(a,y)}{c(y)}. \]

   其中我们使用了 Markov 链的可逆性：\(c(x)P(x,y)=c(y)P(y,x)\)。这就证明了 \(\mathcal{G}_Z(a, x)/c(x)\) 在中间节点的调和性，从而它就是电势函数，这证明了 1。

2. 直接验证即可： \[\begin{align*}\mathbb{E}_a\left[N_{x\to y}^Z - N_{y\to x}^Z\right]&=P(x,y)\mathcal{G}_Z(a,x)-P(y,x)\mathcal{G}_Z(a,y)\\&=P(x,y)c(x)v(x) - P(y,x)c(y)v(y)\\&=c(x,y)(v(x)-v(y))\\&=i(x,y).\end{align*}\]

\(\blacksquare\)

4 Wilson 生成树算法

这一节的目的是介绍怎样将一条给定边 \(e\) 属于一个随机生成树 \(T\) 的概率 \(\mathbb{P}(e\in T)\) 表示为随机游动中的概率。这里的关键是 Wilson 算法，它通过擦圈的随机游动按照一定的权重分布在全体生成树中随机地取样，这里一个生成树 \(T\) 的权重 \(w(T)=\prod_{e\in T}c(e)\)，任一生成树 \(T_0\) 被选中的概率为 \(w(T_0)/\sum_{T}w(T)\)。

在下文中“随机生成树”一词均指服从上述权重分布的随机生成树。

Wilson 算法的步骤如下：

1. 任取一个根节点 \(r\)，维护一个树 \(T\)，初始时 \(T=\{r\}\)。
2. 任取一个顶点 \(v\notin T\)，从 \(v\) 出发作 \(G\) 上的擦圈随机游动，直到随机游动撞到 \(T\) 为止，然后将随机游动的路径 \(p\) 加入 \(T\) 中：\(T=T\cup p\)。
3. 重复步骤 2 直到 \(T\) 是一个生成树为止。

下面这个动画演示了 Wilson 算法的过程，你可以随时单击画布来重启动画。

Wilson 算法正确性的证明比较繁琐，这里不再赘述，你可以参考我 之前的一篇文章。初次遇到这个算法的话可以先跳过证明，只记住结论。这个算法的重点就是初始时的根节点是可以任意选取的，每次进行擦圈的随机游动时选择的出发顶点也可以是任意的，这都不影响得到的生成树 \(T\) 的分布。

一个非常出人意料的结论，它把生成树、随机游动和电网络统一在一起。

证明：在 Wilson 算法中将初始根节点选为 \(y\)，并将第一次出发作擦圈随机游动的顶点选为 \(x\)，则此随机游动首次到达 \(y\) 有两种可能：

1. 是从边 \((x,y)\) 走到 \(y\) 的，此随机游动的路径属于 \(T\)，自然也有 \(e\in T\)。
2. 是从其它边走到 \(y\) 的，则此随机游动的路径属于 \(T\) 但不可能有 \(e\in T\)，否则 \(T\) 中会出现回路。

于是我们证明了 \(e\in T\) 当且仅当从 \(x\) 出发的随机游动首次到达 \(y\) 是从边 \(e\) 走过去的。

另一方面在 定理 3.1 中取 \(Z=\{y\}\) 有

\[ i^e(x,y)=\mathbb{E}_x\left[N^{\{y\}}_{x\to y} - N^{\{y\}}_{y\to x}\right]. \]

注意到从 \(x\) 出发的随机游动不可能在到达 \(y\) 之前从 \(y\) 走到 \(x\)，所以 \(N^{\{y\}}_{y\to x}=0\)。同时它在到达 \(y\) 之前从 \(x\) 走到 \(y\) 的次数只能是 0 或者 1，所以 \(N^{\{y\}}_{x\to y}\in\{0,1\}\)，从而 \[\mathbb{E}_xN^{\{y\}}_{x\to y}=\mathbb{P}_x(N^{\{y\}}_{x\to y}=1)=\mathbb{P}_x\left[\text{the first visit to $y$ is across $(x,y)$}\right].\] 这就完成了证明。

5 图的收缩

设 \(\mathcal{N}=(G,c)\) 是一个网络，\(F\subset E\) 是边的子集且 \(F\) 不含回路 （不考虑边的方向），\(G\) 关于 \(F\) 的图收缩是一个图变换：如果 \(G\) 中的两个顶点可以被 \(F\) 中的路径连接，则它们在新图中坍缩为同一个顶点；并且 \(F\) 中的每条边 \(f\) 的两个端点变成新顶点的一条自边 (loop)。这样得到的新图记作 \(G/F\)。注意当一条边 \(e\notin F\) 如果和 \(F\) 中的边构成回路的话，它在 \(G/F\) 中也会变成自边。

在上图中，虽然 \(e_1,e_2\) 不属于 \(F\)，但是由于它们的两端可以被 \(F\) 中的路径连接，所以在收缩后 \(e_1,e_2\) 也都变成了自边。我们保留这些自边，于是在收缩变换下 \(G\) 的边集 \(E\) 与 \(G/F\) 的边集 \(\widehat{E}\) 一一对应。

严格的说图的收缩是 \(G\) 的一个分割 (partition)：在 \(G\) 的顶点集 \(V\) 上定义等价关系 \(\cong\) 为：\(x\cong y\) 当且仅当 \(x\) 与 \(y\) 可以被 \(F\) 中的路径连接，则 \(G/F\) 的顶点是 \(V/\cong\) 下的等价类，\(G\) 中的边 \(e=(x,y)\) 在 \(G/F\) 中的边变为 \(e=([x],[y])\)，其中 \([x]\) 是 \(x\) 所在的等价类。

我们想知道图 \(G\) 中的电流函数 \(i^e\) 和图 \(G/F\) 中的电流函数 \(\widehat{i^e}\) 之间的关系。这里需要假定 \(e\) 在 \(G/F\) 中没有变成一条自边。收缩 \(F\) 以后 \(i^e\) 仍然是 \(G/F\) 中从 \(e\) 的一端到另一端的单位流，但一般不再是电流。根据 推论 2.4，\(\widehat{i^e}\) 应该是 \(i^e\) 在 \(G/F\) 的星空间 \(\widehat{\bigstar}\) 上的投影分量，所以我们需要找出这个投影映射。

下面的论证读起来会有点让人恼火，但它的直观含义并不难理解：\(i^e\) 不是 \(G/F\) 中的电流的原因是，\(i^e\) 可能在某些 \(F\) 中的边上的值不是 0，而这些边在 \(G/F\) 中变成了自边，自边的电流应该是 0。所以为了从 \(i^e\) 得到 \(\widehat{i^e}\)，我们可以在某些 \(F\) 中的边两端加上电压，使得它们产生的电流可以和 \(i^e\) 在 \(F\) 上的电流抵消，这样处理后的 \(i^e\) 转到 \(G/F\) 中就是我们想要的电流了。即我们给 \(i^e\) 减去 \(Z=\text{span}\{i^f,f\in F\}\) 中的一个电流，这相当于取 \(i^e\) 在 \(Z\) 的正交补 \(Z^\bot\) 上的投影分量。由于 \(F\) 中的边在 \(G/F\) 中变成了自边，所以每个 \(i^f\) 都是从单个顶点流入流出，不会影响任何顶点处的守恒性。

我们下面就来论证上面这个直观分析是正确的。论证细节比较琐碎，如果理解了想法的话跳过去也不影响阅读。

记 \(\chi^F=\{\chi^f,f\in F\}\)，\(Z=\mathrm{span}\{i^f,f\in F\}=P_\bigstar\chi^F\)，则 \(Z\subset\bigstar\)。我们来证明对 \(G/F\) 的环空间 \(\widehat{\lozenge}\) 有 \[\widehat{\lozenge} = \lozenge + \chi^F.\] 首先若 \(C\) 是 \(G\) 中的环： \[v_1\xrightarrow{e_1}v_2\xrightarrow{e_2}\cdots\xrightarrow{e_{k-1}}v_k\xrightarrow{e_k}v_1. \]

那自然有

\[ [v_1]\xrightarrow{e_1}[v_2]\xrightarrow{e_2}\cdots\xrightarrow{e_{k-1}}[v_k]\xrightarrow{e_k}[v_1]. \]

从而 \(C\) 也是 \(G/F\) 中的环，其对应的 \(f^C\in\widehat{\lozenge}\)。此外 \(F\) 中的边在 \(G/F\) 变成自边，所以 \(\chi^F\) 也属于 \(\widehat{\lozenge}\)。即 \(\widehat{\lozenge} \supseteq \lozenge + \chi^F\)。

反之对 \(G/F\) 中的一个环 \(C_{G/F}\)，我们显然可以通过适当插入 \(F\) 中的边来得到 \(G\) 中的一个环 \(C\) （把每个等价类顶点展开为由 \(F\) 中的边组成的路径即可），对应的 \(f^C\) 是 \(f^{C_{G/F}}\) 加上一些 \(\chi^f\) 的和，所以 \(\widehat{\lozenge} \subseteq \lozenge + \chi^F\)，从而反向的包含关系也成立，二者确实相等。

现在我们有 \[\ell^2_{-}(E) = \bigstar\oplus\lozenge=\widehat{\bigstar}\oplus\widehat{\lozenge}.\] 以及 \(\widehat{\lozenge}\supseteq\lozenge\)，从而 \(\widehat{\bigstar}\subseteq\bigstar\)。所以我们进一步有 \[\widehat{\lozenge}=(\bigstar\cap\widehat{\lozenge})\oplus\lozenge.\]

上式右边显然是个直和，且包含在左边中。为了看出左边也包含在右边中，设 \(x\in\widehat{\lozenge}=y+z\)，其中 \(y\in\bigstar,z\in\lozenge\)，显然 \(y=x-z\in\bigstar\cap\widehat{\lozenge}\)。

从而 \[\ell^2_{-}(E)=\widehat{\bigstar}\oplus\widehat{\lozenge}=\widehat{\bigstar}\oplus(\bigstar\cap\widehat{\lozenge})\oplus\lozenge.\] 我们来证明中间的 \(\bigstar\cap\widehat{\lozenge}\) 等于 \(Z=P_\bigstar\chi^F\)。为此只要注意到 \[\bigstar\cap\widehat{\lozenge} = P_{\bigstar}\widehat{\lozenge}=P_{\bigstar}\lozenge + P_{\bigstar}\chi^F=Z.\] 于是 \[\ell^2_{-}(E) =\widehat{\bigstar}\oplus Z\oplus\lozenge.\] 所以对 \(G\) 的一条边 \(e\)，如果它在 \(G/F\) 中没有变成一条自边的话，则电流 \(i^e\) 和 \(\widehat{i^e}\) 的关系为 \[\widehat{i^e}=P_{\widehat{\bigstar}}(\chi^e)=P_{Z}^\bot P_{\bigstar}\chi^F=P_{Z}^\bot i^e.\]

至此我们就验证了之前的直观想法。

接下来是一个引理：

证明：首先不难验证对 \(G\) 的任何边集 \(C\)，\(C\cup F\) 包含回路当且仅当 \(C\) 在 \(G/F\) 中包含回路。这是因为如果 \(C\cup F\) 包含回路的话，那么对回路的顶点取等价类以后自然得到了一个 \(G/F\) 中的回路。反之如果 \(C\) 在 \(G/F\) 中包含回路的话，那么适当插入 \(F\) 中的边以后就可以得到 \(G\) 的回路，即 \(C\cup F\) 是包含回路的。

于是我们得到 \(T_{G/F}\) 是 \(G/F\) 的生成树当且仅当 \(T_G = T_{G/F}\cup F\) 是 \(G\) 的生成树。

由于 \(\{T_G,F\subset T_G\}\) 上的分布是条件分布 \(\mathbb{P}(\cdot\,\big|\, F\subset T_G)\)，所以当 \(T_G\leftrightarrow T_{G/F}\) 时有 \(\mathbb{P}(e\in T_G \,\big| \, F\subset T_G) = \mathbb{P}(e\in T_{G/F})\)。结合 定理 4.1，引理的成立就是显然的事情了。\(\blacksquare\)

于是结合 推论 2.2 我们有如下定理：

6 转移电流定理

定理 6.1 [转移电流定理]：设 \(\{e_1,\ldots,e_k\}\) 一组边的集合，\(T\) 是一个随机生成树，\(Y\) 是 如前定义的转移电流矩阵，定义 \(k\times k\) 矩阵 \(Y^{(k)}(i,j)=Y(e_i,e_j)\)，则 \[\mathbb{P}(e_1,\ldots,e_k\in T) = \det Y^{(k)}.\]

推论：考虑其中 \(r\) 条边 \(\{e_1,\ldots,e_r\}\) 不属于 \(T\)，另外 \(k-r\) 条边 \(\{e_{r+1},\ldots,e_k\}\) 属于 \(T\) 的概率 \(\mathbb{P}(e_1,\ldots,e_r\notin T, e_{r+1},\ldots,e_k\in T)\)，令 \(M^{(r)}\) 是对 \(Y^{(k)}\) 的前 \(r\) 行取反，给前 \(r\) 个对角元加上 1，并保持后 \(k-r\) 行不变得到的矩阵：

\[ M^{(r)}(i, j) =\begin{cases}\delta_{ij} - Y^{(k)}(i, j), & i\leq r\\Y^{(k)}(i,j), & r+1\leq i\leq k.\end{cases} \]

则 \[\mathbb{P}(e_1,\ldots,e_r\notin T, e_{r+1},\ldots,e_k\in T)=\det M^{(r)}.\]

我们首先说明怎样用转移电流定理得出推论的结论。对排除的边的个数 \(r\) 归纳，\(r=0\) 的情形就是转移电流定理。设推论对任何小于 \(r\) 的情形成立，对 \(r\) 的情形，考虑矩阵

\[ P(i, j) = \begin{cases} \delta_{ij} - Y^{(k)}(i,j), & i < r \\ \delta_{ij}, & i = r \\ Y^{(k)}(i,j), & r+1\leq i\leq k. \end{cases} \]

则 \(M^{(r)},M^{(r-1)},P\) 在所有 \(i\ne r\) 的行都相等，但是 \(M^{(r)}\) 和 \(M^{(r-1)}\) 的第 \(r\) 行之和等于 \(P\) 第 \(r\) 行，于是根据行列式的多重线性性质， \[\det M^{(r)}+\det M^{(r-1)}=\det P.\] 将 \(\det P\) 按照 \(P\) 的第 \(r\) 行展开并对 \(\{e_1,\ldots,e_{r-1},e_{r+1},\ldots,e_k\}\) 利用归纳假设，得到

\[ \det P=\mathbb{P}(e_1,\ldots,e_{r-1}\notin T, e_{r+1},\ldots,e_k\in T). \]

又对 \(\{e_1,\ldots,e_{r-1},e_r,\ldots,e_k\}\) 利用归纳假设得到

\[ \det M^{(r-1)} = \mathbb{P}(e_1,\ldots,e_{r-1}\notin T, e_{r},\ldots,e_k\in T) \]

相减即得结论。

回到转移电流定理的证明。分两种情形：

1. 如果 \(\{e_1,\ldots,e_k\}\) 中包含某个回路 \(C\) 的话，我们可以适当重排它们并选取 \(a_i\in\{+1,-1,0\}\) 使得 \(\sum_{i=1}^k a_i\chi^{e_i}=f_C\in\lozenge\)，这里对不属于 \(C\) 的 \(e_i\) 取 \(a_i=0\)，对属于 \(C\) 的 \(e_i\) 通过选择 \(a_i=\pm1\) 使得它们的方向为依次首尾相接。根据基尔霍夫电压定律，对任何电流 \(i^{e_m}\,(1\leq m\leq k)\)，其绕回路一圈电势的改变为 0，所以 \[ 0 = \sum*{i=1}^kr(e_i)i^{e_m}(a_ie_i)=\sum*{i=1}^ka*ir(e_i)i^{e_m}(e_i)=\sum*{i=1}^ka_ir(e_i)Y^{(k)}(e_m,e_i).\] 所以 \(Y^{(k)}\) 的列是线性相关的，从而 \(\mathbb{P}(e_1,\ldots,e_k\in T)=\det Y^{(k)}=0\)，结论成立。

2. 如果 \(\{e_1,\ldots,e_k\}\) 中不包含回路的话，对边的个数 \(k\) 归纳，定理 4.1 已经给出了 \(k=1\) 的情形，所以可以假设 \(k>1\) 且结论对所有小于 \(k\) 的情形成立。我们注意到 \(Y^{(k)}\) “差不多”是一个 Gram 矩阵 （见 之前的推论)： \[Y^{(k)}(i,j)=Y(e_i,e_j)=c(e_j)(i^{e_i},i^{e_j})_E.\] 即 \(Y^{(k)}\) 不过是对每个 \(j\)，在 Gram 矩阵 \(I^{(k)}=\big((i^{e_i},i^{e_j})\big)_{1\leq i,j\leq k}\) 的第 \(j\) 列上乘以 \(c(e_j)\) 得到的，所以 \[ \det Y^{(k)} = \left(\prod_{i=1}^k c(e_i)\right)\det I^{(k)}. \] 回忆内积空间中 Gram 矩阵的行列式的几何意义是其张成的平行多面体的体积的平方，它等于 \(\{i^{e_1},\ldots,i^{e_{k-1}}\}\) 张成的底面 \(Z\) 面积平方乘以 \(i^{e_k}\) 到这个底面距离的平方： \[ \det I^{(k)} = \big\|P_Z^\bot i^{e_k}\big\|^2\det I^{(k-1)}. \] 其中 \(Z=\mathrm{span}\{i^{e_1},\ldots,i^{e_{k-1}}\}\)，\(P_Z^\bot\) 是到 \(Z\) 的正交补空间 \(Z^\bot\) 的投影算子。把 \(\prod_{i=1}^kc(e_i)\) 乘回去就得到 \[ \det Y^{(k)} = c(e_k) \big\|P_Z^\bot i^{e_k}\big\|^2 \det Y^{(k-1)}. \] 另一方面根据条件概率公式有 \[ \mathbb{P}(e_1,\ldots,e_k\in T)= \mathbb{P}(e_k\in T\,\big|\, e_1,\ldots,e_{k-1}\in T)\cdot \mathbb{P}(e_1,\ldots,e_{k-1}\in T). \] 而根据 定理 5.1 的结论 \[ \mathbb{P}(e_k\in T\,\big|\, e_1,\ldots,e_{k-1}\in T) = c(e_k) \big\|P_Z^\bot i^{e_k}\big\|^2, \] 从而 \(\det Y^{(k)}\) 和 \(\mathbb{P}(e_1,\ldots,e_k\in T)\) 有相同的初始条件和递推关系，从而它们相等，转移电流定理得证。

7 回答本文开头的问题

如本文开头所述，解决 \(\mathbb{Z}^2\) 中顶点在随机迷宫中度数分布的问题归结为求解 \(\mathbb{Z}^2\) 上的转移电流矩阵，即令所有边的电导值均为 1，在一条边 \(e=(x,y)\) 两端通入单位电流时，流过另一条边 \(e'\) 的电流流量，这等价于求解对应的电势函数 \(v\)，也等价于求解 \(\mathbb{Z}^2\) 上拉普拉斯算子的解

\[ (\Delta v)(x) = \mathbb{1}_{\{ x=e^- \}} - \mathbb{1}_{\{ x=e^+ \}}. \]

这一步可以通过 Fourier 分析的方法来做，比如 Lyons 等人的教材就是采用的这种方法。但是假定你看过本系列的 第一篇文章 的话，我们可以省很多事情，直接用二维随机游动的势核函数 \(a(x)\) 来构造电势函数 \(v\)。注意到 \(a(x)\) 在除去原点之外的任何点是调和的，并且在原点处的值为 0。记

\[ g(u) = \frac{a(u-y)-a(u-x)}{4}. \]

则 \(g\) 在除去 \(x,y\) 外任何点处是调和的，从而 \(i=\nabla g\) 满足欧姆定律、在除 \(x,y\) 之外满足基尔霍夫定律，且 \(g(x)=a(x-y)/4 = -g(y)\)。又

\[ \begin{align*} \|i\| &= \sum_{z\sim x}i(x, z)=\sum_{z\sim x}[g(x)-g(z)]\\ &=a(x-y)-\sum_{z\sim x}\frac{a(z-y)-a(z-x)}{4}\\ &=\left(a(x-y)-\sum_{z\sim x}\frac{a(z-y)}{4}\right) + \sum_{z\in\{\pm(1,0),\pm(0,1)\}}\frac{a(z)}{4}\\ &=1. \end{align*} \]

其中最后一个等号是因为势核在除去原点之外是调和的，且在原点的四个邻居处值为 1。

于是 \(v(u)=g(u)-g(y)\) 即为当 \(x\) 通入单位电流，\(y\) 接地时 \(\mathbb{Z}^2\) 上的电势函数，从而其在任何一边 \(e'=(z,w)\) 上的电流为

\[ i(z,w) = g(z) - g(w)=\frac{1}{4}\big[a(z-y)-a(z-x)-a(w-y)+a(w-x)\big]. \]

当 \(e=(x,y)\) 和 \(e'=(z,w)\) 都取自原点相邻的四条边时，根据下图中的势核值代入上式即得本文开头的转移电流矩阵。

举个例子验证一下：取 \(e_1=(0, 0)\to(1,0)\)，\(e_2=(0,0)\to (0,1)\)，则 \(x=z=(0,0)\)，\(y=(1,0)\)，\(w=(0,1)\)，于是 \[i^{e_1}(e_2)=\frac{a(-1,0)-a(0, 0)-a(-1,1)+a(0,1)}{4}=\frac{1}{2}-\frac{1}{\pi}.\] Bingo!

参考文献

上一篇：Escher 风格的非周期密铺

下一篇：Coxeter 群，有限状态机与均匀密铺