朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

Wilson 一致生成树算法

2014-04-04


更新:在距离本文初稿完成若干年后,我终于实现了一个 Python 程序,可以制作演示 Wilson 算法的 gif 动图,见我的这篇文章。此外还用 Javascript + canvas 为本文写了一个动画演示,这也是我的第一个正式的 Javascript 程序 (其实就是把对应的 Python 程序修改下翻译了过来),你可以随时单击鼠标来重启动画。


考虑这样的问题:给定一个有限无向的连通图,怎样在它的所有生成树中等概率地任选一种?我们熟悉的 Prim 算法、Kruskal 算法得到的都不是完全随机的生成树,目前已知最快的算法是 Wilson 算法,它借助于擦圈的随机游动来实现。

Wilson 算法:设 \(G\) 是一个有限的、简单的、连通图。

  1. 任取一个顶点 \(r\),维护一个树 \(T\),初始时 \(T=\{r\}\)
  2. 任取一个不属于 \(T\) 的顶点 \(v\),从 \(v\) 出发作图上的随机游动,一边走一边随时擦掉路径中出现的圈 (此为 loop erased random walk),即每当走到一个以前访问过的顶点 \(x\),则两次访问 \(x\) 之间的路径都被擦掉,直到与 \(T\) 相遇为止,这样得到一条从 \(v\)\(T\) 的不含圈的路径 \(p\),把 \(p\) 加入到 \(T\) 中,\(T=T\cup p\)
  3. 重复此步骤直到 \(T\) 包含 \(G\) 的所有顶点,这时得到的 \(T\) 是一个服从一致分布的生成树。

注意连通性保证了算法会以概率 1 结束。

Wilson 算法的描述很简单,但是单从描述上完全看不出算法的正确性来。注意其中有两个任意:

  1. 初始时可以任选一个初始根节点 \(r\)
  2. 每次可以任选一个不属于 \(T\) 的顶点出发作随机游动。

Wilson 本人给出的证明相当有技巧性,而且有一些晦涩的部分,我是花了很久才真正理解,回过头来看其实也不复杂。本文就来介绍这个证明。

算法的证明

在进入正式的证明前我先简要说说大致的思路。

\(\mathcal{T}\)\(G\) 的所有生成树组成的集合,我们想把 \(G\) 上的所有可能的随机游动的实现都 "装在" 一个概率空间 \((\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\) 是一个确定的映射。

证明

  1. 对每个 \(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\)

    每个 \(\omega\in\Omega\) 对应 \(G\) 上随机游动的一种可能的实现。想象这些 \(\{S_{v,i}\}\) 构成了一个 "路牌指示系统",如果当前位置是顶点 \(u\),则根据 \(S_u\) 当前的栈顶元素 \(S_{u,i}\) 的指示到达下一个顶点 \(S_{u,i}\),同时弹出 \(S_u\) 的栈顶元素 \(S_{u,i}\),将 \(S_u\) 处的 "路牌" 更新为 \(S_{u,i+1}\)

    由于顶点 \(r\) 对应的栈 \(S_r\) 是空栈,所以随机游动一旦到达 \(r\) 就终止。

  2. 在任何时刻,这些栈 \(\{S_v,v\ne r\}\) 的栈顶元素都定义了一个有向图 \(G_S\)\(v\rightarrow u\) 当且仅当 \(u\)\(S_v\) 的栈顶元素。每个 \(v\ne r\) 的出度都恰好是 1,顶点 \(r\) 的出度是 0,于是若 \(G_S\) 不含回路的话它就是一个以 \(r\) 为根的生成树。

  3. 下面我们来玩一个 "回路弹出" (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\) 是一个生成树。

  4. 你可以每次无脑选一个回路将其弹出,也可以将 \(G_S\) 的所有回路在某种顺序下排好,每次弹出最小的那个,这都是不同的游戏策略。擦圈的随机游动对应的是这样的策略:每次从一个不属于 (当前维护的树) \(T\) 的顶点出发,跟着栈顶图的路牌指示走,遇到哪个回路弹哪个。撞到 \(T\) 的话就把当前路径加入 \(T\),再从任意一个不属于 \(T\) 的顶点出发重复这个过程。

  5. 映射 \(\phi\) 定义如下:对任何 \(\omega\in\Omega\),若 \(\omega\) 的栈顶图 \(G_S\) 不含任何回路 (即已经是一个生成树,这里应理解为无向树),则令 \(\phi(\omega)=G_S\)。否则用擦圈的随机游动对其进行回路弹出操作,若经过有限次操作后得到的 \(G_S\) 不含任何回路,就令 \(\phi(\omega)=G_S\),否则 \(\phi(\omega)\) 无定义。

    由于 Wilson 算法以概率 1 在有限时间内结束,所以 \(\phi(\omega)\) 以概率 1 是有定义的,即映射 \(\phi\) 满足条件 (1)。

    然而这里有一个重要的问题:\(\phi\) 的定义是合理无歧义的吗?注意 Wilson 算法允许每次从任意一个不属于 \(T\) 的顶点出发作擦圈的随机游动,不同的选择会不会导致不同的 \(G_S\)?下面就来解决这个疑问。

  6. 现在让若干玩家来玩这个游戏,而且每个人采取的游戏策略是不同的。问题来了:对给定的栈状态 \(\omega\in\Omega\),这些玩家得到的结果一样吗?会不会有的人能获胜,而有的人不能?或者会不会有两个获胜的玩家,他们最终得到的栈顶图 \(G_S\) (也就是最终的生成树) 是不同的?甚至会不会有两个获胜的玩家,虽然他俩最终得到的栈顶图是相同的,但是操作次数是不同的?

    答案都是否定的:不管这些玩家采取怎样的策略,只有两种可能的结果出现:

    1. 所有人都不能获胜。

    2. 所有人都能获胜,而且每个人使用的操作次数也相同,最终得到的栈顶图 \(G_S\) 也相同。不仅如此,每个人弹出的回路组成的集合 \(\{C_1,\ldots,C_n\}\) 也都是相同的。注意这里的回路 \(C_i\) 是带有颜色标记的,两个回路相同不仅要求对应顶点相同,也要求对应顶点的颜色相同。仅仅他们弹出这些 \(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\),则 \(v\)\(G_S\) 中的后继 \(v'\) 也同时属于 \(C_1\)\(D_1\) (注意这个论述需要 \(C_1\)\(D_1\) 在同一个栈顶图中,在第一步操作时这当然是成立的),\(v'\) 的后继 \(v''\) 也如此,这样一直下去回到 \(v\) 就会有 \(C_1=D_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 的原证明的论述要繁琐,但是从钻石引理的角度更本质地揭示了为什么游戏的结果不依赖于具体的策略。

  7. \(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\) 的顶点是 "无缝隙" 地填满栈 \(\{S_v\}\) 的上面部分的话,那么可能会给人这样的疑问:会不会依次弹出 \(\mathcal{C}\) 中回路得到 \(T\) 这个事件对其它没有被弹出的顶点施加了某种限制,从而导致上面的概率不是若干独立事件的概率之积?当然事实是不会的,那些顶点全都在 \(T\) 的下面,随便是什么都对 "弹出 \(\mathcal{C}\) 得到 \(T\)" 这个事件没有影响。

    \(\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}\) 组成的集合,这是因为在给定 \(\mathcal{C}\) 后,任何生成树 \(T\) 都有可能出现 (解释见后面),因此 \[\mathbb{P}(T) ={\rm const}\cdot \Phi(T).\]\(\Phi(T) = \prod\limits_{v\ne r}\frac{1}{d_v}\) 是一个与 \(T\) 无关的量,从而 \(\mathbb{P}(T)\) 是常数,这就证明了 \(\phi\) 满足条件 (3)。

  8. 解释下为什么给定 \(\mathcal{C}\) 以后任何 \(T\) 都可能出现,打个比方,想象一个向弹夹里面压子弹的过程:把树 \(T\) 放在栈顶,然后依次用 \(C_n,\ldots,C_1\)\(T\) 往下压,得到一个栈的状态 \(\{S_v\}\),对这个状态执行回路弹出,显然依次弹出的就是 \(C_1,\ldots,C_n\),最终得到的树是 \(T\)。这顺便也说明了 \(\phi\) 是满射的,即 \(\phi\) 满足条件 (2)。

  9. 至此我们证明了擦圈的随机游动给出的映射 \(\phi:\Omega\to\mathcal{T}\) 满足前面的三个条件,这就证明了 Wilson 算法的正确性。