动机
为了降低所有试验都失败的概率,可以为重复运行选取相互独立的随机种子。在很大的种子空间上,这可能需要大量随机比特。在正则图上的游走只使用一个随机初始顶点,此后每一步随机选取一个邻点。游走经过的各顶点相互关联,因此不能用独立性来论证乘积界。然而,谱方法仍然可以界定“所访问的每个顶点都落在某个固定坏集合中”的概率。
本单元明确陈述所需的图假设。它既不构造扩展图族,也不证明存在具有特定度数和谱的扩展图。随机比特的节省取决于是否有一个合适的图,并且其邻点可以被高效计算。
定义
定义 5.1.1
(正则图的绝对谱界)
设 为有 个顶点的有限无向 -正则图,,其对称转移矩阵为 。均匀概率向量为 。令 ,并假设 在与 正交的子空间上的每个特征值的绝对值至多为 。等价地,记 ,则对称算子 的范数至多为 。
定义 5.1.2
(坏集合与游走样本)
固定一个坏顶点集合 ,其相对大小为 。令 为对角矩阵,当 时 ,其余为零。游走从均匀随机选取的顶点 出发,并通过相互独立的均匀邻点步骤依次到达 。尽管每个边缘分布都是均匀的,各位置之间一般是相依的。定义 。
定理
定理 5.1.3
(对固定坏集合的重复访问)
对每个整数 ,
特别地,若 ,则 ,且该界限随 呈指数下降。
定理 5.1.4
(单边放大)
设某确定性验证器在获得一个均匀随机的种子顶点后运行。对每个固定的正例输入,其坏种子集合 固定,相对大小至多为 ,其中 ;并且对任何种子,它都不会接受负例输入。把它依次作用于游走的 个顶点,只要有一次运行接受就接受。则对固定的正例输入,拒绝的概率至多为
而负例输入仍然永远不会被接受。记 为此统一上界的因子。
证明思路或证明
证明
(掩码算子的二次型界)
对任何支撑在 上的向量 ,由柯西–施瓦茨(Cauchy–Schwarz)不等式得
由于 ,谱假设给出
这里较精细的中间不等式用到 在 上为零,以及它在正交分量上的范数界。对任意向量 ,取 ,得 。矩阵 是对称的,因此由实谱定理得 。
全部落在坏集合中这一事件的概率等于
当 时等式同样成立,此时把零次幂理解为单位矩阵。应用柯西–施瓦茨不等式和算子范数界。由于 ,结果至多为 。这直接控制了一个联合事件,并没有断言游走各位置相互独立。
证明
(从并集界到放大)
关于放大:先固定输入。拒绝意味着所用的每个种子都属于其坏集合。第一个定理适用于这个固定集合,而右端在 上关于 不减,所以由 得到所示的界限。对负例输入,验证器每次运行对每个种子都拒绝,因此组合后的过程不可能接受。该保证是针对每个固定输入的;它并不要求同一条游走对所有输入同时有效。
证明透视
两个假设、一个掩码、每步一个因子
证明有两个步骤。第一,对支撑在 上的 ,界 结合了两个假设: 很小,由柯西–施瓦茨不等式把沿 的分量限制在 以内;谱假设则使正交分量以 收缩。单靠任何一个假设都得不到 。
第二,对角掩码把联合事件变成矩阵乘积 ,其中每次转移都带有范数至多为 的因子 ,而第一个掩码通过 贡献 。 的对称性使二次型的界升级为算子范数的界。证明从不使用独立性;对相对大小为 的每个 ,无论其内部有什么边,界都相同,所以它可能偏松,本单元稍后的三角形小例子就说明了这一点。
例题详解
例题 5.1.5
(失败概率的数值保证)
若 ,,,则 ,全部为坏的概率至多为 。这五个种子并不相互独立;该数值来自联合事件定理。
例题 5.1.6
(只访问一次的情形)
当 时,均匀初始化给出 恰好成立。定理给出 。这种情形不需要任何转移,谱界在其中不起作用。
例题 5.1.7
(完全混合的理想情形)
若 ,则 ,且每个下一顶点都是均匀的,并与前一顶点独立。此时界限变为 ,即熟知的独立抽样概率。稀疏图一般有正的 ,界限较弱,但换来了更便宜的邻点选取。
常见错误
反例模式
均匀的边缘分布不能直接相乘
在无自环的正则图上,平稳游走在每个时刻都是均匀的,但它不可能一步之内停留在同一个顶点。因此相邻位置并不独立。边缘概率的乘积需要另行论证;带掩码算子的计算给出的是另一种并集界。具体地,在只有一个坏顶点 的三角形中,,但 ,而不是 。
常见错误
(坏集合必须在抽样之前固定)
集合 必须在对游走抽样之前就已针对该输入固定。若在看到每个顶点之后自适应地选取不同的坏集合,则本定理并不适用。
常见错误
(去掉绝对值会漏掉负特征值)
不带绝对值的特征值界限也无法控制接近 的负特征值;所述的算子范数假设同时包含了正负两种符号。
为什么带掩码的矩阵是压缩的
证明把向量分解为常数部分和正交部分。 并不压缩常数部分,这正是仅有关于非常数特征值的界限不能断言每个向量都会缩小的原因。但支撑在真子集上的向量不可能主要是常数:柯西–施瓦茨估计把它的常数分量的平方限制在至多 乘以其范数平方。其余分量位于适用绝对特征值界限的子空间中。要得到 ,既需要坏集合较小,也需要真正的谱隙。
为了更明确地计算,写 ,其中 。则 ,且 。谱假设蕴含 。由于 且 ,可得
负特征值已包含在二次型的绝对界之内。对称性在下一步中很重要:对实对称矩阵,其算子范数等于最大的绝对特征值,也就是绝对瑞利(Rayleigh)商的最大值。没有对称性时,仅有二次型的界限未必能以同样的方式控制算子范数。
掩码是一个投影: 且 。乘以 并不会重新归一化概率分布,而是舍弃位于 之外的顶点上的质量。剩余的总质量就是相应的一系列成员检验均已成功的概率。因此,矩阵公式追踪的是无条件概率;若在每一步之后插入归一化,计算就会改变,并需要另外追踪归一化因子。
概念视角组合
数留在坏集合内的游走
每条含 个顶点的游走的概率都是 ,所以全部落在坏集合的概率,等于 个顶点都在 内的游走条数除以 。因此定理的意思是:这样的游走至多有 条,而平凡的计数是 。因子 是 内平均分支数的限制:游走只能通过 内顶点通向 内另一顶点的少数边留在 内。
访问次数的选取
令 。若 且 ,则使失败概率至多为 的一个充分条件是
其中要求对数的分子为正;结果向上取整为整数。若 ,则对这个界限而言一次访问已经足够。若 ,则没有坏种子,失败概率为零。这些条件是充分的,并不表示对特定的图和坏集合该不等式是紧的。
例如,取 且 ,则 。要使界限至多为 ,只需选取 使 。计算结果为取整后 :。这个数可以直接验算,而不必依赖四舍五入的对数。实际失败概率可能更小,因为算子估计把所有支撑在坏集合上的向量都当作达到了最坏的压缩率。
例题 5.1.8
(完整的失败界计算)
设某输入至多有四分之一的坏种子,且图满足所要求的绝对特征值界限 。对八个游走顶点,所有验证器运行都失败的概率至多为 。因此只要有一次运行成功就接受,则对该固定正例输入,成功概率至少为 。该定理并不保证精确的成功概率等于这个值。
随机性与算法成本
若 且 ,则初始顶点可用 个公平随机比特抽取,此后每个均匀选取的邻点用 个新的公平随机比特,总共 个比特。相互独立的均匀种子顶点则需要 个比特。当 远小于 时,这一比较才有意义。对于大小不是 2 的幂的情形,精确的均匀抽样需要明确指定的方法,并且必须分析其比特成本;简单的取模约化可能产生偏差。
种子图还必须能被算法实际使用。证明某个图具有较小的非常数特征值,本身并不等于有一个高效的邻点计算过程。具体的实现需要:顶点的表示、计算每个带编号邻点的方法、经过验证的度数与谱保证,以及把每个顶点映射为验证器种子的方法。验证器的执行次数仍然是 ,所以随机性的节省并不会自动减少运行时间。这些是对应用的条件,而不是谱不等式的额外结论。
均匀初始化是定理的一部分。若从某个固定顶点出发,且该顶点为坏顶点,则第一次访问时全部为坏的概率就可能为一。预热期可以使分布接近均匀,但其近似误差必须纳入新的分析;所示表达式并不会悄悄地涵盖它。类似地,坏种子的集合可以依赖于所固定的输入,但证明是在考虑随机游走之前先固定该输入的。
单边错误的解释
验证器的单边保证包含两个部分。在正例输入上,至多有指定比例的种子是坏的,因此重复访问可以降低错过所有好种子的概率。在负例输入上,每个种子都必须拒绝。后一性质保证无论存在何种相关性,只要有一次运行接受就接受并不会引入假阳性。若负例输入具有非零的假阳性率,则只要有一次运行接受就接受可能会放大该错误;此时需要单独的分析和聚合规则。
该陈述在以下意义上对输入是一致的:同一个数值界限适用于满足假设的每个固定输入。它并不自动蕴含一条随机生成的游走同时对所有可能的输入都成功。要对有限的输入族推出同时成立的陈述,可以对该族应用并集界,代价是乘以该族的大小。对于无穷或非常大的输入族,还需要更多结构。区分这些量词可以避免夸大逐输入的保证。
小图中的直接验证
考虑一个三角形,坏集合由单个顶点构成。这里 ,,简单随机游走的两个非常数特征值均为 ,所以 且 。定理把两次连续访问坏顶点的概率界定为 。事实上其概率为零:访问了唯一的坏顶点之后,无自环的游走必须移动到另一个顶点。这个例子既说明了该界限的正确性,也说明了它可能的宽松程度。一般的估计不能假定每个坏集合都具有这种特殊形状。
当 时,事件概率恰好等于集合的相对大小,与图无关。对于之后的步骤, 内部的边的数目与排布会产生影响。谱假设把这些与具体图有关的细节压缩为一个对给定大小的每个集合都有效的单一界限。两个顶点数相同的坏集合可以有不同的内部边和不同的实际全坏概率,尽管同一个上界对两者都适用。
这些假设也解释了失效的情形。若图不连通,则某个非常数特征向量可以具有特征值一;从小连通分量出发的游走会永远留在其中。若连通图是二部图,则特征值负一会使绝对谱界无法小于一。懒惰化的修改可以消除周期性,但必须为修改后的游走重新计算其特征值和比特成本。配套的谱混合单元对正则图证明了这些事实;本单元则把由此得到的绝对界限作为假设使用。
总结
支撑在小集合上的向量,其均匀分量受该集合大小的限制。非均匀分量则按绝对谱界压缩。这两个事实合起来界定了带掩码的转移算子,进而界定了整条游走始终留在坏集合中的概率。
练习
快速检查
(取 ,,,计算该界限。)
先计算 。
解答 · 答案
这里 ,所以界限为 。
快速检查
(为什么 且 蕴含 ?)
分解 。
解答 · 答案
由于 ,故 。
快速检查
(当 为空集时,该定理给出什么?)
空集的 是多少?
解答 · 答案
此时 ,对每个 ,概率和界限都为零。
快速检查
(仅有各顶点边缘分布的界限能否建立全坏界?请说明。)
回想只有一个坏顶点的三角形。
解答 · 答案
不能。相继的位置是相关的。证明所采用的是界定带掩码转移算子乘积的范数。