Wilson 均匀生成树算法
更新：在距离本文初稿完成数年后，我终于实现了一个 Python 程序，可以制作演示 Wilson 算法的 GIF 动图，见 这个 Github 项目。此外还用 Javascript + canvas 为本文写了一个动画演示，这也是我的第一个正式的 Javascript 程序 （其实就是把对应的 Python 程序修改下翻译了过来），你可以随时单击鼠标来重启动画。
Wilson 均匀生成树算法是一个很有意思的算法，我最初接触它是在念 Russel Lyons 等人的 Probability on trees and networks 一书时，在网上查阅资料发现了 这个动画。当时就大叹奇妙，一顿看起来没头没脑的操作怎么就得出了一个迷宫呢？而且这个迷宫还服从所有迷宫 （准确的说是所有完美迷宫） 上的均匀分布！
Wilson 本人给出的证明相当有技巧性，而且有一些晦涩的部分，我是花了很久才真正理解，回过头来看其实也不复杂，但是把细节说清楚需要花一番功夫。本文就来介绍这个证明。
算法的表述
考虑这样的问题：给定一个有限无向的连通图，怎样在它的所有生成树中等概率地任选一种？我们熟悉的 Prim 算法、Kruskal 算法得到的都不是完全随机的生成树，目前已知最快的算法是 Wilson 算法，它借助于擦圈的随机游动来实现。
Wilson 算法：设 \(G\) 是一个有限的、简单的、连通图。
- 任取一个顶点 \(r\)，维护一个树 \(T\)，初始时 \(T=\{r\}\)。
- 任取一个不属于 \(T\) 的顶点 \(v\)，从 \(v\) 出发作图上的随机游动，一边走一边随时擦掉路径中出现的圈 （此为 loop erased random walk），即每当走到一个以前访问过的顶点 \(x\)，则两次访问 \(x\) 之间的路径都被擦掉，直到与 \(T\) 相遇为止，这样得到一条从 \(v\) 到 \(T\) 的不含圈的路径 \(p\)，把 \(p\) 加入到 \(T\) 中，\(T=T\cup p\)。
- 重复此步骤直到 \(T\) 包含 \(G\) 的所有顶点，这时得到的 \(T\) 是一个服从均匀分布的生成树。
注意连通性保证了算法会以概率 1 结束。
Wilson 算法的描述很简单，但是单从描述上完全看不出算法的正确性来。注意其中有两个任意：
- 初始时可以任选一个初始根节点 \(r\)。
- 每次可以任选一个不属于 \(T\) 的顶点出发作随机游动。
算法的证明
在进入正式的证明前我先简要说说大致的思路。
设 \(\mathcal{T}\) 是 \(G\) 的所有生成树组成的集合。我们构造一个概率空间 \((\Omega,\mathbb{P})\)，\((\Omega,\mathbb{P})\) 的具体描述我们先按下不表。我们将寻找一个从 \(\Omega\) 到 \(\mathcal{T}\) 的映射 \(\phi\)，\(\phi\) 满足如下条件：
(1). \(\phi\) 对几乎处处的 \(\omega\in\Omega\) 有定义 （不是所有的随机游动都能得到一个生成树，但这种例外发生的概率是 0）。
(2). \(\phi\) 必须是满射。
(3). 对任何 \(T\in\mathcal{T}\)，其在 \(\Omega\) 中的原像 \(\phi^{-1}(T)\) 的测度是一个与 \(T\) 无关的常数。
一旦找到这样的概率空间 \(\Omega\) 和映射 \(\phi\)，则对任何 \(\omega\in\Omega\)，\(\phi(\omega)\) 以概率 1 是一个生成树，且其服从均匀分布。
这个映射 \(\phi\) 就是擦圈的随机游动。证明中最有技巧性的部分就在于说明，虽然在擦圈的随机游动中每次选择的顶点有任意性，但是 \(\phi\) 是一个确定的映射。
证明：
对每个 \(v\ne r\)，定义一个栈结构 \(S_v=\{S_{v,1},S_{v,2},\ldots\}\)，这里栈的长度为无穷，每个 \(S_{v,i}\) 都是随机变量，来自对 \(v\) 的邻居的均匀采样，所有的栈元素 \(\{S_{v,i}\}\) 都是独立的。顶点 \(r\) 的栈是一个空栈：\(S_r=\emptyset\)。我们要构造的概率空间 \(\Omega\) 就是这些栈 \(\{S_v\}\) 所有可能的状态组成的集合，这是一个无穷离散的概率空间，其上的测度 \(\mathbb{P}\) 为乘积测度。
此外我们规定每个栈的第 \(i\) 个元素 \(S_{v,i}\) 的颜色是 \(i\)。
在任何时刻，这些栈 \(\{S_v,v\ne r\}\) 的栈顶元素都定义了一个有向图 \(G_S\)，\(G_S\) 叫做栈顶图：\(G_S\) 的顶点集就是 \(G\) 的顶点集 \(V\)，\(G_S\) 中从 \(v\) 连一条指向 \(u\) 的有向边当且仅当 \(u\) 是 \(S_v\) 的栈顶元素。每个 \(v\ne r\) 的出度都恰好是 1，顶点 \(r\) 的出度是 0，于是若 \(G_S\) 不含回路的话它就是一个以 \(r\) 为根的生成树。
下面我们来玩一个“回路弹出” (cycle popping) 的游戏。这个游戏有点类似俄罗斯方块，目的是消除栈顶图中的所有回路：给定栈的一个状态 \(\omega\in\Omega\)，设 \(G_S\) 是 \(\omega\) 的栈顶图，若 \(G_S\) 不含回路的话则它已经是一个生成树，游戏结束；否则设 \(C\) 是 \(G_S\) 中的一个回路，我们可以将其“弹出”：对回路中的每个顶点 \(v\in C\)，弹出 \(S_v\) 的栈顶元素，于是若 \(S_v\) 的栈顶元素为 \(S_{v,i}\)，则弹出 \(S_{v,i}\) 以后栈顶元素变为 \(S_{v,i+1}\)。这样得到一个更新后的 \(G_S\)。玩家可以每次任选 \(G_S\) 中的一个回路并将其弹出，如果经过有限多次弹出操作后使得 \(G_S\) 中不含任何回路，则玩家获胜，这时得到的 \(G_S\) 是一个生成树。
你可以每次无脑选一个回路将其弹出，也可以将 \(G_S\) 的所有回路在某种顺序下排好，每次弹出最小的那个，这都是不同的游戏策略。Wilson 算法使用的是“跟着导航走”的策略：每次从一个不属于 \(T\) 的顶点出发，跟着栈顶图的路牌指示走，每当走出一个回路，就把这个回路弹掉。撞到 \(T\) 的话，那就说明当前路径上的顶点不会属于任何回路（因为栈顶图的每个顶点出度至多是 1），它们都是“安全”的。把当前路径加入 \(T\)，再从任意一个不属于 \(T\) 的顶点出发重复这个过程。
Wilson 的策略可行吗？它能保证以概率 1 得到一个生成树吗？会不会在某次循环时一直在擦圈，永远撞不到 \(T\)？答案是不会。由于 \(G\) 有限且连通，其上的简单随机游动是正常返的，每次循环时，随机游动以概率 1 在有限时间内撞到 \(T\)，所以算法确实以概率 1 在有限时间内结束。
映射 \(\phi\) 定义如下：对任何 \(\omega\in\Omega\)，若 \(\omega\) 的栈顶图 \(G_S\) 不含任何回路 （即已经是一个生成树，这里应理解为无向树），则令 \(\phi(\omega)=G_S\)。否则用擦圈的随机游动对其进行回路弹出操作，若经过有限次操作后得到的 \(G_S\) 不含任何回路，就令 \(\phi(\omega)=G_S\)，否则 \(\phi(\omega)\) 无定义。
这里有一个重要的问题：\(\phi\) 的定义是合理无歧义的吗？注意 Wilson 算法允许每次从任意一个不属于 \(T\) 的顶点出发作擦圈的随机游动，不同的选择会不会导致不同的 \(G_S\)？下面就来解决这个疑问。
我们假设有若干玩家分别玩这个游戏，每个人采取的游戏策略是不同的。我们想知道，对给定的初始栈状态 \(\omega\in\Omega\)，这些玩家都能获胜吗？他们最终得到的栈顶图 \(G_S\) （也就是最终的生成树） 一样吗？需要的操作次数相同吗？
答案是：不管这些玩家采取怎样的策略，只有两种可能的结果出现：
所有人都不能获胜。
所有人都能获胜，而且每个人使用的操作次数也相同，最终得到的栈顶图 \(G_S\) 也相同。不仅如此，每个人弹出的回路组成的集合 \(\{C_1,\ldots,C_n\}\) 也都是相同的。注意这里的回路 \(C_i\) 是带有颜色标记的，两个回路相同不仅要求对应顶点相同，也要求对应顶点的颜色相同。仅仅他们弹出这些 \(C_i\) 的顺序可能不同。
这个现象可以很容易用所谓的“钻石引理” (diamond lemma) 来解释。我在这里不打算展开介绍钻石引理，你可以参考 这篇文章，里面包含了钻石引理的几个有趣的应用。
我们只要证明如下的结论即可：
引理：对任一栈状态 \(\omega\in\Omega\)，若玩家 \(A\) 可以经过 \(n\) 次操作后获胜，其弹出的回路依次为 \(C_1,\ldots,C_n\)，则不论玩家 \(B\) 的策略如何，其必然也经过 \(n\) 次操作后获胜，其弹出的回路集合 \(\{D_1,\ldots,D_n\}\) 与 \(\{C_1,\ldots,C_n\}\) 是相同的，即适当重排 \(\{D_1,\ldots,D_n\}\) 后有 \(D_i=C_i\)。这里回路的相等要求对应的顶点和颜色均相同。
引理的证明：对玩家 \(A\) 的操作次数 \(n\) 归纳。\(n=0\) 时结论显然成立 （双方均无任何操作），下面设 \(n\geq1\) 且结论对所有小于 \(n\) 的情形成立。
设 \(B\) 第一次弹出的回路是 \(D_1\)，如果 \(C_1=D_1\) 则这一步操作后 \(A,B\) 到达了相同的状态，而 \(A\) 可以继续经过 \(n-1\) 次操作后获胜，于是根据归纳假设 \(B\) 也一定经过 \(n-1\) 次操作获胜且后续操作 \(\{D_2,\ldots,D_n\}=\{C_2,\ldots,C_n\}\)。
如果 \(C_1\ne D_1\)，我们断言 \(C_1\) 和 \(D_1\) 没有公共的顶点。否则若 \(v\in C_1\cap D_1\)，由于第一次操作时 \(C_1,D_1\) 属于同一个栈顶图中，以及 \(v\) 的出度是 1，所以 \(v\) 在 \(G_S\) 中的后继 \(v_1\) 也同时属于 \(C_1\) 和 \(D_1\)，进而 \(v_1\) 的后继 \(v_2\) 也是如此，这样一直下去回到 \(v\) 就会有 \(C_1=D_1\)，矛盾。
既然 \(C_1\) 和 \(D_1\) 没有相同顶点，那说明不论先弹 \(C_1\) 后弹\(D_1\)，或是先弹 \(D_1\) 后弹 \(C_1\)，得到的栈顶图是一样的。
接下来的论述是钻石引理的典型操作：我们引入两个新玩家 \(A'\) 和 \(B'\)，\(A'\) 的前两步操作是先弹出 \(C_1\) 后弹出 \(D_1\)，\(B'\) 的前两步操作是先弹出 \(D_1\) 后弹出 \(C_1\)。\(A\) 和 \(A'\) 第一步操作相同，因此由归纳假设 \(A'\) 必然继续经过 \(n-2\) 步后获胜；\(A'\) 和 \(B'\) 前两步操作后到达相同的状态，而 \(A'\) 可以在 \(n-2\) 步后获胜，所以由归纳假设 \(B'\) 必然在 \(n-2\) 步后获胜。最后由于第一步操作后 \(B'\) 和 \(B\) 到达相同的状态，而 \(B'\) 可以在 \(n-1\) 步后获胜，所以 \(B\) 也必然在 \(n\) 步后获胜。至于 \(A,B,A',B'\) 弹出的回路相同也是显然的。
至此我们就说明了 \(\phi\) 的定义是合理的，它是一个确定的映射。
对没有接触过菱形引理的读者，我这个论述比 Wilson 的原证明的论述要繁琐，但是从钻石引理的角度更本质地揭示了为什么游戏的结果不依赖于具体的策略。
设 \(T\) 是任一生成树，我们来说明 \(\phi^{-1}(T)\) 的测度是不依赖于 \(T\) 的常数。
设 \(\mathcal{C}=\{C_1,\ldots,C_n\}\) 是一组染色的回路，如果依次弹出 \(C_1,\ldots,C_n\) 以后可以得到一个生成树，我们就称 \(\mathcal{C}\) 是一组成功的回路。给定一组成功的回路 \(\mathcal{C}\) 和任一生成树 \(T\)，我们来计算弹出的回路集合恰好是 \(\mathcal{C}\) 并且最终得到的生成树恰好是 \(T\) 的概率。注意 \(\mathcal{C}\) 和 \(T\) 的顶点必然无缝隙地填满栈 \(\{S_v\}\) 的上面的部分，所以这个概率就是 \(\mathcal C\) 和 \(T\) 中的边各自指向正确位置的概率： \[\mathbb{P}(\mathcal{C},T)= \prod_{e\in\mathcal{C}\cup T} p_e=\Phi(T)\cdot \Phi(\mathcal{C}).\] 这里 \(\Phi(\bullet)\) 返回集合 \(\bullet\) 中所有边的概率的乘积。
设 \(\mathcal{C}_T\) 是所有可能得到 \(T\) 的那些 \(\mathcal{C}\) 组成的集合，在上式两边对 \(\mathcal{C}_T\) 求和，则 \[\mathbb{P}(T)=\left(\sum_{\mathcal{C}\in\mathcal{C}_T}\Phi(\mathcal C)\right)\cdot\Phi(T).\] 但是注意 \(\mathcal{C}_T\) 是一个与 \(T\) 无关的集合，这是因为在给定 \(\mathcal{C}\) 后，任何生成树 \(T\) 都有可能出现 （解释见后面），因此 \[\mathbb{P}(T) ={\rm const}\cdot \Phi(T).\] 而 \(\Phi(T) = \prod\limits_{v\ne r}(1/d_v)\) 是一个与 \(T\) 无关的量，从而 \(\mathbb{P}(T)\) 是常数，这就证明了 \(\phi\) 满足条件 (3)。
解释下为什么给定 \(\mathcal{C}\) 以后任何 \(T\) 都可能出现，打个比方，想象一个向弹夹里面压子弹的过程：把树 \(T\) 放在栈顶，然后依次用 \(C_n,\ldots,C_1\) 将 \(T\) 往下压，得到一个栈的状态 \(\{S_v\}\)，对这个状态执行回路弹出，显然依次弹出的就是 \(C_1,\ldots,C_n\)，最终得到的树是 \(T\)。这顺便也说明了 \(\phi\) 是满射的，即 \(\phi\) 满足条件 (2)。
至此我们证明了擦圈的随机游动给出的映射 \(\phi:\Omega\to\mathcal{T}\) 满足前面的三个条件，这就证明了 Wilson 算法的正确性。