动机
重复的独立采样可能代价高昂,因为每抽取一个新的随机顶点都需要大量随机比特。随机游走则重用当前顶点:每一步从其邻点中选取一个。这样能否得到近似均匀的样本,取决于图本身。一个图可以是连通的却混合缓慢,而连通的二部图则可能永远在其两侧之间交替。特征值为区分这些行为提供了定量的方法。本单元证明一个混合估计;若要把随机游走用于完整的节省随机性的放大,还需要联合事件的界,此处并不作这样的断言。
定义
定义 5.2.1
(转移矩阵与第二大绝对特征值)
设 是有限无向 -正则图,有 个顶点且 。转移矩阵为 ,其中 是邻接矩阵。采用列概率向量:。因为 是对称的且每一列之和为一,所以均匀分布 是平稳分布。实谱定理给出一组标准正交特征基。把特征值写作 ,并为 选取归一化的常值向量,再令 。
定义 5.2.2
(全变差距离)
对概率向量 ,它们的全变差距离为 。它等于在所有顶点集 上 的最大值。为说明这一点,令 为满足 的顶点集;由于各坐标之差的总和为零,正的部分之和恰为绝对值之和的一半,而其他任何集合给出的绝对差都不会更大。
定理
定理 5.2.3
(谱混合界)
对每个初始分布 及每个整数 ,
特别地,从任意单个顶点出发,有 。若 ,则游走从每个初始分布出发都收敛到均匀分布。
定理 5.2.4
(特征值与周期性判据)
的每个特征值都落在 内。若 连通,则特征值 的重数为一。若 连通且非二部图,则 不是特征值。因此,对连通的非二部图有 。
证明思路或证明
证明
(偏离均匀分布的收缩)
向量 与常值向量正交,因为它的各坐标之和为零。把它按标准正交特征基展开为 。于是
由柯西–施瓦茨(Cauchy–Schwarz)不等式,。把它应用于 ,即证得第一个不等式。若 是点质量,则它到 的距离平方为 ,由此得到第二个不等式。
证明
(特征值、连通性与二部性)
对于特征值判据,设 是属于特征值 的实特征向量,并选取使 最大的顶点 。由于 是邻点坐标的平均值,故 ,从而 。若 ,平均值中等号成立迫使 的每个邻点的取值都等于 ;连通性把这一等式传播到整个图。因此每个 -特征向量都是常值向量。
若 ,等号成立迫使 的每个邻点的取值都等于 。在连通图中传播下去,沿每条路径的取值都正负交替。奇圈会迫使一个非零值等于它的相反数,这是矛盾。因此连通的非二部图没有特征值 。由于图只有有限多个特征值,且所有非常值特征值都严格介于 与 之间,它们的绝对值的最大值严格小于一。
证明透视
为什么偏差从第二个特征向量开始
证明把 拆成平稳部分 与偏差 ,一切都建立在偏差与常值向量正交之上:它的各坐标之和为零。正因如此,展开可以从 开始,因子 不会出现,衰减只由 控制。 的对称性用来取得标准正交特征基,所以平方范数就是 ,没有交叉项。
中需要绝对值,因为 ,对 的衰减并不比 更快;接近 的特征值会一边交替变号,一边使收缩停滞。最后一步 是 唯一出现之处:欧氏范数的收缩要付出这个因子,才变成全变差距离的界。
例题详解
例题 5.2.5
(三角形上的游走)
对三个顶点的无自环完全图,。常值向量的特征值为 ,而与之正交的每个向量的特征值为 。因此 。从点质量出发,定理给出全变差距离至多为 。负特征值带来交替变号的修正项,但其模长按几何级数衰减。
例题 5.2.6
(周期性的二部图游走)
在四圈上,若从二部划分的某一侧出发,则游走在偶数时刻位于同一侧,在奇数时刻位于另一侧。均匀分布给两侧各分配概率 ,而游走在相应奇偶性的时刻把概率一全部分配给其中一侧。因此全变差距离在每个时刻都至少为 。该图是连通的,但 是特征值,游走并不收敛到均匀分布。
例题 5.2.7
(足够的步数)
若一个图有 且 ,则从任意顶点出发, 步之后的全变差距离至多为 。当 时,它小于 。这只是充分性的界;实际距离可能更小。该估计使用的是假定的谱界,对所选定的图,这个谱界必须另行证明。
常见错误
反例模式
平稳性并不蕴含收敛
即使对四圈,均匀分布也是平稳的,但点质量并不收敛到它。平稳性说的是从均匀分布出发的游走始终保持均匀;收敛说的是其他初始分布会趋近于均匀分布。这是两个不同的论断。
常见错误
(正则图不一定连通)
正则图可以是不连通的;此时游走无法离开其所在的连通分支,特征值 还有额外的特征向量。于是对适当选取的特征基, 等于一。
常见错误
(近似均匀的边缘分布不等于独立样本)
对每个单一时刻分布的界并不会使相继的位置相互独立。特别地,仅凭边缘分布近似均匀,并不能证明游走以指数小的概率避开某个固定的坏集。
以等待消除周期性
一种标准的修改是懒惰游走:每一步以概率 停留在当前顶点,否则执行原游走的一步。它的矩阵为 。它是对称的,并保持均匀分布不变。若 ,则 ,所以它的特征值由 的特征值经这一变换得到。特征值 变为零。在连通图上, 的每个非常值特征值都严格小于一,因此 的每个非常值特征值都落在 内。于是同样的谱证明给出:懒惰游走在每个连通正则图(包括二部图)上都收敛。
这一修改改变了实验本身。证明了懒惰游走的界之后,不能悄悄地把它归属于原来的非懒惰游走。懒惰的一步可以停留在同一顶点,而无自环图上的原游走不可能这样。例如在四圈上,从某个顶点出发,懒惰的一步以概率 停在该顶点,并以概率 移到各个邻点。这种重复消除了原游走确定性的奇偶交替。
例题 5.2.8
(懒惰四圈)
非懒惰四圈的转移矩阵特征值为 。在 下,它们变为 。因此 。从任意顶点出发,经 个懒惰步之后,到均匀分布的全变差距离至多为 。该界证明了收敛性,尽管它并不是每个时刻的精确距离。
从全变差距离到事件概率
若分布 与均匀分布的全变差距离不超过 ,则对每个顶点集 ,
这由定义中的事件刻画得到。例如,若某个集合含有百分之十的顶点,且全变差距离至多为 ,则它在该时刻的概率介于 与 之间。针对某个特定顶点的逐点论断也是一个事件论断,但 的全变差界可能远大于均匀质量 ;对于一个非常稀少的顶点,它未必给出有用的相对估计。
概念视角组合
数长度为 t 的游走
设 为由 到 、长度为 的游走的条数。于是 ,所以均匀性表示:从 出发的 条等可能游走,其终点分布得很均匀。由于 ,其算子范数为 ,所以每个元素都满足
每一对顶点之间的游走条数,都几乎恰好等于均匀分配的条数。
该陈述针对的是单个时刻。即使从平稳分布出发的游走,各个位置之间也是相依的:每一步的下一个顶点都必须是当前顶点的邻点。对于无自环图,在一步中停留在同一顶点的概率为零,而两个独立的均匀顶点重合的概率为 。因此,精确均匀的边缘分布并不蕴含独立性。要证明许多次访问全都落在某个坏集中,需要对相关性另加控制,而不仅仅是对每次访问应用单一时刻的混合界。
若确实需要独立的近似均匀样本,一种直接的构造是:对每个样本使用独立的随机比特分别运行游走,每次都从固定顶点出发并走足够多的步数。由于所得输出依赖于互不相交的随机种子,它们是相互独立的。这种简单做法无法获得单条相关游走所节省的随机比特。后者可以借助更强的扩展性或谱论证来分析,但这些界需要各自的证明与假设。
割与必要的瓶颈检验
对顶点集 ,记 为一端在 内、另一端在 外的无向边之集。若初始顶点在非空集 上均匀分布,则一步之内离开 的概率恰为
事实上, 个起始顶点等可能,每个顶点的 条关联边各以概率 被选中,而每条边界边恰从其位于 内的端点被计数一次。这个比值度量了该初始分布所对应的瓶颈。如果它很小,则下一步时大部分概率仍留在 内,即使整个图上的均匀分布分配给 的质量要小得多。
更精确地说,若 ,则从 上的均匀分布出发的一步分布给 分配的概率为 ,而均匀分布分配的是 。因此,只要这两个概率之差为正,它们的全变差距离就至少等于这个差。边界很小是不能快速一步混合的证据。这一初等观察并不是一般的谱扩展定理的证明:要把每个割的比值与特征值以及之后所有时刻联系起来,还需要额外的论证和适当的常数。
正则性使这里的均匀分布成为平稳分布。对于非正则的无向图,简单随机游走的平稳分布通常与度数成正比,而不是均匀的。对称矩阵与范数的论证可以通过改变内积来适应,但上面给出的均匀分布结论不能原样照搬。类似地,有向图未必有对称的转移矩阵,也未必有标准正交的实特征基;上文所用的谱定理是该方法的一个实质性假设,而不是装饰性的步骤。
谱估计的解读
量 常被称为绝对谱隙。该估计直接说明了它为何重要:当 接近一时,可能需要很多步才能使 变小。当 时,为使点质量的界至多为 ,只需
其中要求分子为正;否则对这个特定的界而言,零步就已满足。将所得的数向上取整为整数。若 ,则谱表达式表明一步即精确到达均匀分布。这些都是由该不等式导出的充分条件,未必是最优的混合时间。
如果当顶点数增长时存在公共的界 ,则称这个图族对快速混合是有用的。对固定的期望全变差误差,所给估计只需要与顶点数的对数成正比的步数。但每一步的代价仍须考虑。如果每个顶点有 个可显式寻址的邻点,且 是 的幂,则可用 个均匀随机比特选定一步。对于其他度数,精确的均匀选取需要适当的抽样方法;简单地把均匀选取的比特串对 取模可能引入偏差。
谱定理给出的是对所有起始顶点一致的界,但对特定的起点或时刻它可能比较松。它把每个非常值特征值的模长都替换为单一的最坏值 ,并应用了柯西–施瓦茨不等式。给定起始向量的某些系数可能为零,而一范数与二范数之间的不等式也未必取到等号。因此,计算得到的精确分布可能比这一证书所预测的混合得更快,而这并不与它矛盾。
总结
对称性使随机游走的转移矩阵成为可正交对角化的算子。非常值特征值控制着偏离均匀分布的部分在欧氏范数下收缩的速度;柯西–施瓦茨不等式把这一点转化为全变差保证。连通性消除了额外的平稳方向,非二部性则消除了交替的方向。
练习
快速检查
(计算无自环完全图 上游走的非常值特征值,并给出 。)
写出 的 ,并利用 在常值向量的正交补上为零。
解答 · 答案
此时 。矩阵 在与常值向量正交的向量上为零,所以非常值特征值为 ,且 。
快速检查
(对 且 ,证明 足以使从点质量出发的界达到 。)
把 、、 代入点质量的界。
解答 · 答案
该界为 。
快速检查
(为什么仅凭连通性不能保证收敛到均匀分布?)
考虑连通的二部图,例如四圈。
解答 · 答案
连通的二部图会在其两侧之间交替。四圈的例子中,从某个顶点出发时,到均匀分布的全变差距离始终至少为 。
快速检查
(若 ,则在每个时刻到均匀分布的全变差距离是多少?)
是平稳分布吗?
解答 · 答案
它为零,因为 ,因而对每个 都有 。