Wilson 均匀生成树算法
问题： 给定一个有限、无向的连通图 \(G= ( V,E )\)，设 \(\mathcal{T}\) 是 \(G\) 的所有生成树组成的集合，怎样在 \(\mathcal{T}\) 中按照均匀分布进行采样？即设计一个算法，能够随机地给出 \(G\) 的一个生成树，并且 \(\mathcal{T}\) 中每个生成树被取到的概率是相等的。
常见的生成树算法如 DFS/BFS 算法、Prim 算法、Kruskal 算法等给出的生成树都不是完全随机的。例如，取 \(G\) 为 \(\mathbb{Z}^2\) 中 \(m\times n\) 的网格图，\(G\) 的任何生成树都是一个迷宫，把背景平面涂黑，把生成树的边涂白，就可以清楚地看到迷宫的结构。迷宫的任何两个房间 ( 即顶点 ) 可以通过生成树中唯一的路径相连，这样的迷宫叫做完美迷宫。
DFS 算法 ( 每次将新顶点的顺序打乱再入栈 ) 倾向于尽可能深地探索整个图，因此得到的迷宫往往包含长且蜿蜒的路径，死角 ( 即叶节点 ) 是很少的：
与之相反，Prim 算法由于每次是在当前树上随机添加一个叶节点，因此得到的迷宫往往包含很多死角：
总之从直观上就可以看出这两个算法得到的生成树都不是完全随机的。
目前最快的生成均匀生成树的算法是 Wilson 算法，它借助于擦圈的随机游动来实现。
Wilson 算法. 设 \(G\) 是一个有限简单连通图。
- 任取一个顶点 \(r\)，维护一个树 \(T\)，初始时 \(T=\{r\}\)。
- 任取一个不属于 \(T\) 的顶点 \(v\)，从 \(v\) 出发作图上的随机游动，一边走一边随时擦掉路径中出现的圈 ( 此谓之 loop erased random walk ) ，即每当走到一个以前访问过的顶点 \(x\)，则两次访问 \(x\) 之间的路径都被擦掉。按此规则持续行走直到与 \(T\) 相遇为止，这时得到一条从 \(v\) 到 \(T\) 的不含圈的路径 \(p\)，把 \(p\) 加入到 \(T\) 中，将 \(T\) 更新为 \(T=T\cup p\)。
- 重复步骤 2 直到 \(T\) 包含 \(G\) 的所有顶点，这时 \(T\) 是一个服从均匀分布的生成树。
下面是 Wilson 算法的 Javascript 演示，你可以随时单击鼠标来重启动画。
注意 Wilson 算法的描述中有两个任意：
- 初始时可以任选一个初始根节点 \(r\)。
- 每次可以任选一个不属于 \(T\) 的顶点出发作随机游动。
Wilson 在他本人的 论文 中给出的证明相当有技巧性，而且有一些晦涩的部分，我是花了很久才真正理解。本文就来介绍这个证明。
证明思路
先不管均匀分布的事情，我们来说明 Wilson 算法以概率 1 会在有限时间内结束。
命题 1.1. Wilson 算法以概率 1 在有限时间内返回一个生成树。
证明：由于 \(G\) 有限且连通，所以其上的随机游动是常返的，在算法第 2 步中，每次从一个新顶点 \(v\) 出发的随机游动以概率 1 在有限时间内撞到 \(T\)。这样的循环只能执行有限多次 ( 次数以 \(|V|\) 为上界 ) ，所以算法以概率 1 在有限时间内结束。\(\blacksquare\)
所以真正有挑战性的地方在于论证得到的生成树服从均匀分布。
证明的大致想法是这样的：我们构造概率空间 \(( \Omega,\mathbb{P} )\) 和映射 \(\phi: \Omega\to\mathcal{T}\)，使得它们满足如下的条件：
- \(\phi\) 对几乎处处的 \(\omega\in\Omega\) 有定义 ( 不是所有的 \(\omega\) 都对应一个生成树，但这种例外发生的概率是 0 ) 。
- \(\phi\) 是满射。 ( 不能漏掉任何树 )
- 对任何树 \(T\in\mathcal{T}\)，其在 \(\Omega\) 中的原像 \(\phi^{-1} ( T )\) 的测度是一个与 \(T\) 无关的常数。
一旦找到了这样的概率空间 \(( \Omega,\mathbb{P} )\) 和映射 \(\phi\)，则 \(\phi ( \omega )\) 以概率 1 是一个生成树，且服从 \(\mathcal{T}\) 上的均匀分布。
为了启发 \(( \Omega,\mathbb{P} )\) 和 \(\phi\) 的构造，我们来看看著名的 Tetris 游戏（俄罗斯方块），它和 Wilson 算法有许多类似之处。这可能听起来有点偏离主题，但是你要知道 Wilson 算法是一个相当巧妙的算法，它的证明并不直观，通过一个类比应该可以帮助大家更好的理解证明思路。
经典的 Tetris 游戏是这样的，系统每次会随机从屏幕顶端落下 \(\{I,L,J,O,S,T,Z\}\) 七种四方块 ( tetromino ) 中的一个。玩家可以在方块下落的过程中左右移动或者旋转它，尽可能地形成完整的水平行。每当出现完整的水平行时，这些行会被立刻消掉，同时玩家获得一定的分数。玩家的目的是获得尽可能高的分数。
显然 Tetris 游戏的结果由两个因素决定：系统的随机性和玩家的操作。这里系统的随机性是指每次落下的方块的随机性。
系统的随机性可以用一个概率空间 \(( \Omega,\mathbb{P} )\) 来描述：任何样本点 \(\omega\in\Omega\) 是一个无穷序列 \(\omega=\{X_i\}_{i=1}^\infty\)，其中 \(X_i\) 表示第 \(i\) 个落下的方块的类型，它来自对集合 \(\{I,L,J,O,S,T,Z\}\) 的独立且服从均匀分布的采样。\(\Omega\) 上的概率测度 \(\mathbb{P}\) 是无穷乘积测度。
例如，一个样本点 \(\omega\) 可能是这样的 \[\omega=\{J, S, I, O, J, I, T, T, S, Z, Z, Z,\ldots\}.\] 即第一个落下的方块是 \(J\)，第二个是 \(S\)，第三个是 \(I\)，等等。
一旦给定了 \(\omega\)，游戏的结果将只依赖于玩家的操作。
现在我要告诉你，Wilson 算法背后是一个类似 Tetris 的游戏，但又和 Tetris 游戏有一个关键不同：Wilson 算法的结果只依赖于系统的随机性，不依赖于玩家的操作。换句话说：对给定的 \(\omega\)，要么玩家的任何操作都会得到同一个生成树；要么任何操作都不能。即 \(T\) 是由 \(\omega\) 完全决定的。于是我们有一个确定的映射 \(\phi ( \omega ) =T\)！并且根据 命题 1.1, Wilson 算法以概率 1 成功得到一个生成树，所以 \(\phi\) 对几乎处处的 \(\omega\) 是有定义的！
下面来具体介绍这个游戏。
Wilson 算法作为游戏策略
我们来玩一个叫做回路弹出 ( cycle popping ) 的游戏。我先介绍这个游戏背后的系统随机性 \(( \Omega,\mathbb{P} )\)。
概率空间 \(( \Omega,\mathbb{P} )\) 的构造.
- 首先由玩家任意指定一个顶点 \(r\)。
- 对每个 \(v\ne r\)，定义一个栈结构 \(S_v=\{S_{v,1},S_{v,2},\ldots\}\)，这里 \(S_v\) 的长度是无穷，每个元素 \(S_{v,i}\) 都是随机变量，其取值为 \(v\) 的邻居。所有栈元素都是独立的。顶点 \(r\) 的栈是一个空栈：\(S_r=\emptyset\)。
- 概率空间 \(\Omega\) 是所有栈 \(\{S_v\mid v\ne r\}\) 的所有可能的状态组成的集合。这是一个无穷离散的概率空间，其上的测度 \(\mathbb{P}\) 为乘积测度。
为了方便，我们称栈的第 \(i\) 个元素 \(S_{v,i}\) 的颜色是 \(i\)。
在任何时刻，这些栈 \(\{S_v,v\ne r\}\) 的栈顶元素都定义了一个有向图 \(\overrightarrow{G}_S\)：在 \(\overrightarrow{G}_S\) 中 \(v\rightarrow u\) 当且仅当 \(u\) 是 \(S_v\) 的栈顶元素。每个 \(v\ne r\) 的出度都恰好是 1，顶点 \(r\) 的出度是 0。于是若 \(\overrightarrow{G}_S\) 不含回路的话它就是一个以 \(r\) 为根的生成树。
回路弹出游戏. 给定栈的一个状态 \(\omega\in\Omega\)，\(\overrightarrow{G}_S\) 是 \(\omega\) 对应的栈顶图，若 \(\overrightarrow{G}_S\) 不含回路的话则它已经是一个生成树，游戏结束；否则设 \(C\) 是 \(\overrightarrow{G}_S\) 中的一个回路，我们可以将其「弹出」：对每个 \(v\in C\)，弹出 \(S_v\) 的栈顶元素 ( 于是若当前 \(S_v\) 的栈顶元素为 \(S_{v,i}\)，则弹出 \(S_{v,i}\) 以后栈顶元素变为 \(S_{v,i+1}\) ) ，这样得到一个更新的 \(\overrightarrow{G}_S\)。玩家每次可以任选 \(\overrightarrow{G}_S\) 中的一个回路并将其弹出。如果玩家能够经过有限多次弹出操作后使得 \(\overrightarrow{G}_S\) 中不含任何回路，即 \(\overrightarrow{G}_S\) 是一个生成树，则玩家获胜。
有两点需要注意：
- 在回路弹出游戏中，每次弹出一个回路以后，可能会有新的回路产生，「源源不绝」，所以这个游戏并不是一定会在有限次操作后结束。
- 在游戏开始之前，\(\overrightarrow{G}_S\) 中所有顶点的颜色都是 1；但是随着游戏的进行，\(\overrightarrow{G}_S\) 会变得「五颜六色」。同一个回路中可以包含不同颜色的顶点。
在回路弹出游戏中，玩家能做的就是每次选择一个需要弹出的回路，别的什么也做不了。不同的选择可能导致不同的结果（实际上并不是）。
Wilson 算法作为游戏策略. 这个策略可以形容为「跟着导航走」：每次任选一个不属于 \(T\) 的顶点 \(v\)，从 \(v\) 出发按照 \(\overrightarrow{G}_S\) 的边的指引来搜索下一个要弹出的回路。
树 \(T\) 的作用是什么？注意 \(T\subset\overrightarrow{G}_S\) 始终是一个以 \(r\) 为根节点的有向树，于是从 \(T\) 中的任何顶点出发沿着 \(\overrightarrow{G}_S\) 的有向边都会走到根节点 \(r\)。由于 \(r\) 是个死胡同 ( \(r\) 的出度是 0 ) ，所以 \(T\) 中的顶点不可能属于任何回路。即 \(T\) 维护的是那些已经完全确定下来、必然属于最终生成树的那些边。
我们前面剧透过，回路弹出游戏的结果不依赖于玩家的操作。我们把这个事实的证明放在后面，先承认它是正确的，于是我们可以定义映射 \(\phi\)：
\(\phi\) 的构造. 设使用 Wilson 算法对 \(\omega\) 执行操作以后得到的生成树为 \(T\)，定义 \(\phi ( \omega ) =T\)。
定理 2.1. \(T\) 服从所有生成树组成的集合 \(\mathcal{T}\) 上的均匀分布。
这个结论解释了为什么 Wilson 算法中的 两个任意 对最终结果是没有影响的。
证明：我们来计算如下事件的概率：依次弹出回路 \(\mathcal{C}= ( C_1,\ldots,C_n )\) 后得到的生成树是 \(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\) 满足前面提到的全部 三个条件 ，这就证明了 Wilson 算法的正确性。
游戏结果与策略无关
最后我们证明最关键的部分：Wilson 算法的结果与每次选择弹出的回路无关。
假设有若干玩家分别玩回路弹出的游戏，每个人采取的策略是不同的。我们想知道，对给定的系统随机性 \(\omega\)，这些玩家都能获胜吗？他们最终得到的生成树一样吗？需要的操作次数相同吗？
答案是：不管这些玩家采取怎样的策略，只有两种可能的结果出现：
- 所有人都不能获胜。
- 所有人都能获胜，而且每个人使用的操作次数也相同，最终得到的栈顶图 \(\overrightarrow{G}_S\) 也相同。不仅如此，每个人弹出的回路组成的集合 \(\{C_1,\ldots,C_n\}\) 也都是相同的。注意这里的回路 \(C_i\) 是带有颜色标记的，两个回路相同不仅要求包含的顶点相同，也要求对应顶点的颜色相同。仅仅弹出的顺序可能不同。
我们只要证明如下的结论即可：
引理. 对任一栈状态 \(\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\)，得到的栈顶图是一样的。
接下来的论述是钻石引理 ( diamond lemma ) 的典型操作：我们引入两个新玩家 \(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-1\) 步后获胜。
\(A,B,A',B'\) 弹出的回路集合相同是显然的。
至此我们就说明了 \(\phi\) 的定义是合理的，它是一个确定的映射。
对没有接触过钻石引理的读者，我这个论述比 Wilson 的原证明的论述要繁琐，但是这个角度更本质地揭示了为什么游戏的结果不依赖于具体的策略。