本续篇以先前笔记中的 RP、BPP 和独立放大为基础。我们将方差界与先前的指数估计比较,再研究一个可以精确计算单侧错误的多项式检验。每个概率均针对固定输入。
利用 Chebyshev 不等式的放大
Hoeffding 论证依赖于一个被引用而未被证明的集中不等式。看到多项式级的错误降低已经可以由一个完全初等的工具得出,是很有启发的。代价是错误的衰减较弱,是多项式的而不是指数的。
设 r r r 次独立运行(r r r 为奇数)中的每一次在固定输入上正确的概率至少为 2 / 3 2/3 2/3 。则多数答案错误的概率至多为 8 / r 8/r 8/ r 。
令 X i ∈ { 0 , 1 } X_i\in\{0,1\} X i ∈ { 0 , 1 } 表示第 i i i 次运行出错,令 p i = Pr [ X i = 1 ] ≤ 1 / 3 p_i=\Pr[X_i=1]\le 1/3 p i = Pr [ X i = 1 ] ≤ 1/3 ,并令 S = ∑ i = 1 r X i S=\sum\limits_{i=1}^r X_i S = i = 1 ∑ r X i 。则 E [ S ] = ∑ p i ≤ r / 3 \mathbb E[S]=\sum p_i\le r/3 E [ S ] = ∑ p i ≤ r /3 。由于 X i X_i X i 相互独立,方差可加,所以 V a r ( S ) = ∑ p i ( 1 − p i ) \mathrm{Var}(S)=\sum p_i(1-p_i) Var ( S ) = ∑ p i ( 1 − p i ) 。函数 f ( p ) = p ( 1 − p ) f(p)=p(1-p) f ( p ) = p ( 1 − p ) 在 [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] 上递增,所以 p i ≤ 1 / 3 p_i\le 1/3 p i ≤ 1/3 给出 p i ( 1 − p i ) ≤ ( 1 / 3 ) ( 2 / 3 ) = 2 / 9 p_i(1-p_i)\le (1/3)(2/3)=2/9 p i ( 1 − p i ) ≤ ( 1/3 ) ( 2/3 ) = 2/9 ,因而 V a r ( S ) ≤ 2 r / 9 \mathrm{Var}(S)\le 2r/9 Var ( S ) ≤ 2 r /9 。
只有当 S ≥ r / 2 S\ge r/2 S ≥ r /2 时多数结果才是错误的。此时 S − E [ S ] ≥ r / 2 − r / 3 = r / 6 > 0 S-\mathbb E[S]\ge r/2-r/3=r/6\gt 0 S − E [ S ] ≥ r /2 − r /3 = r /6 > 0 ,所以 ∣ S − E [ S ] ∣ ≥ r / 6 |S-\mathbb E[S]|\ge r/6 ∣ S − E [ S ] ∣ ≥ r /6 。Chebyshev 不等式表明,对任意 t > 0 t\gt 0 t > 0 ,Pr [ ∣ S − E [ S ] ∣ ≥ t ] ≤ V a r ( S ) / t 2 \Pr[|S-\mathbb E[S]|\ge t]\le\mathrm{Var}(S)/t^2 Pr [ ∣ S − E [ S ] ∣ ≥ t ] ≤ Var ( S ) / t 2 。取 t = r / 6 t=r/6 t = r /6 ,得
Pr [ 多数表决出错 ] ≤ 2 r / 9 ( r / 6 ) 2 = 2 r 9 ⋅ 36 r 2 = 8 r . \Pr[\text{多数表决出错}]\le\frac{2r/9}{(r/6)^2}=\frac{2r}{9}\cdot\frac{36}{r^2}=\frac{8}{r}. Pr [ 多数表决出错 ] ≤ ( r /6 ) 2 2 r /9 = 9 2 r ⋅ r 2 36 = r 8 .
证明透视
方差界真正需要什么 唯一不显然的一步,是把“多数出错”这个事件转成 S S S 偏离其均值。我们只知道 E [ S ] ≤ r / 3 \mathbb E[S]\le r/3 E [ S ] ≤ r /3 ,所以差距 r / 2 − E [ S ] r/2-\mathbb E[S] r /2 − E [ S ] 在最坏情况下至少是 r / 6 r/6 r /6 ,均值更小只会使差距更大;因此单一的界 p i ≤ 1 / 3 p_i\le 1/3 p i ≤ 1/3 已经足够。p ( 1 − p ) p(1-p) p ( 1 − p ) 在 [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] 上的单调性只用了一次,用来把每个未知的 p i p_i p i 换成最坏情形。这个界之所以收得拢,是因为方差像 r r r 那样增长,而阈值的平方像 r 2 r^2 r 2 那样增长。若各次运行共用随机性,方差就不再可加:当 X 1 = ⋯ = X r X_1=\cdots=X_r X 1 = ⋯ = X r 时 V a r ( S ) = r 2 p ( 1 − p ) \mathrm{Var}(S)=r^2p(1-p) Var ( S ) = r 2 p ( 1 − p ) ,Chebyshev 不等式便什么也推不出。
这个证明有两点值得评论。第一,它只通过方差的可加性来使用独立性,而这在各次运行仅仅两两独立时就已成立。先前笔记中的 Hoeffding 论证不在此说明所涵盖的范围内,因为它使用的是完全独立性。第二,结论 8 / r 8/r 8/ r 可用于把错误降低到某个多项式的倒数。要使错误至多为 1 / q ( n ) 1/q(n) 1/ q ( n ) ,只需取不小于 8 q ( n ) 8q(n) 8 q ( n ) 的最小奇数 r r r ,它是多项式。这一估计本身不能给出指数级小的错误;先前的指数估计可以。
设某 BPP 算法在每个输入上正确的概率至少为 2 / 3 2/3 2/3 ,并设目标错误为 1 / 100 1/100 1/100 。
使用方差界,我们需要 8 / r ≤ 1 / 100 8/r\le 1/100 8/ r ≤ 1/100 ,即 r ≥ 800 r\ge 800 r ≥ 800 。由于 800 800 800 是偶数,取最小的奇数值 r = 801 r=801 r = 801 ,此时 8 / 801 ≈ 0.00999 < 0.01 8/801\approx 0.00999\lt 0.01 8/801 ≈ 0.00999 < 0.01 。
使用 Hoeffding 论证得到的指数界,需要 e − r / 18 ≤ 1 / 100 e^{-r/18}\le 1/100 e − r /18 ≤ 1/100 ,即 r ≥ 18 ln 100 ≈ 82.89 r\ge 18\ln 100\approx 82.89 r ≥ 18 ln 100 ≈ 82.89 ,故奇数值 r = 83 r=83 r = 83 就足够。因此在这个目标下,指数界的效率约高出十倍,并且目标错误越小,差距越大。对于目标错误 2 − 20 2^{-20} 2 − 20 ,方差界将要求 r ≥ 8 ⋅ 2 20 = 8,388,608 r\ge 8\cdot 2^{20}=8{,}388{,}608 r ≥ 8 ⋅ 2 20 = 8 , 388 , 608 次重复(奇数值为 8,388,609 8{,}388{,}609 8 , 388 , 609 ),而指数界只需 251 251 251 次。
这两个数都是由上界得到的充分次数,不一定是达到目标错误的最小值。这一比较表明,BPP 在多项式级错误降低下的封闭性这一定性结论是初等的,而这个直接方差估计不能给出指数级小的错误;上面的指数估计可以。
随机恒等检验
单边错误的一个经典用途是检验两个多项式是否为同一个函数。这里的输入是两个整系数多项式 p p p 和 q q q ,以显式系数列表的形式给出,次数均至多为 d ≥ 1 d\ge 1 d ≥ 1 。我们要判定作为多项式是否 p ≠ q p\ne q p = q ,等价地,判定差 D = p − q D=p-q D = p − q 是否不恒为零。
选取 k = ⌈ log 2 ( 2 d ) ⌉ k=\lceil\log_2(2d)\rceil k = ⌈ log 2 ( 2 d )⌉ 以及 S = { 0 , 1 , … , 2 k − 1 } S=\{0,1,\ldots,2^k-1\} S = { 0 , 1 , … , 2 k − 1 } 。算法使用 k k k 个公平比特从 S S S 中均匀选取 a a a 。它用 Horner 法则计算 p ( a ) p(a) p ( a ) 和 q ( a ) q(a) q ( a ) ,若 p ( a ) ≠ q ( a ) p(a)\ne q(a) p ( a ) = q ( a ) 则回答“不同”,否则回答“相同”。整数 a a a 有 O ( log d ) O(\log d) O ( log d ) 个比特,而 Horner 求值相对于显式输入长度只产生多项式数量的比特,所以每次运行用多项式时间。比较系数列表在这里本身就已经是确定性多项式时间的解法;这个例子说明的是概率论证,而不是加速。
正确性论证使用了一个标准的代数事实,将在下文证明:次数至多为 d d d 的非零整系数(或实系数)多项式至多有 d d d 个根。若 p = q p=q p = q ,则 D D D 恒为零,算法绝不会回答“不同”,因此对于不等对构成的语言没有假阳性。若 p ≠ q p\ne q p = q ,则 D D D 是次数至多为 d d d 的非零多项式,所以在 ∣ S ∣ ≥ 2 d |S|\ge 2d ∣ S ∣ ≥ 2 d 种 a a a 的选择中至多有 d d d 个满足 D ( a ) = 0 D(a)=0 D ( a ) = 0 ,于是算法以至少 1 − d / ∣ S ∣ ≥ 1 / 2 1-d/|S|\ge 1/2 1 − d /∣ S ∣ ≥ 1/2 的概率回答“不同”。这恰是 RP 的保证。
旁注 按下可固定此旁注,按 Escape 关闭。 旁注
先说明语言
阅读错误保证之前,先说明算法所识别的语言是什么。这里是不相等的多项式对所构成的集合,所以回答“不同”是确凿的,“相同”才可能出错。
关闭
例题 1.3.3
(一个紧致的实例与一个失效的样本集)
取 p ( x ) = x 2 p(x)=x^2 p ( x ) = x 2 和 q ( x ) = x q(x)=x q ( x ) = x ,于是 d = 2 d=2 d = 2 ,并选取 S = { 0 , 1 , 2 , 3 } S=\{0,1,2,3\} S = { 0 , 1 , 2 , 3 } ,其大小为 2 d = 4 2d=4 2 d = 4 。差为 D ( x ) = x 2 − x D(x)=x^2-x D ( x ) = x 2 − x ,且
D ( 0 ) = 0 , D ( 1 ) = 0 , D ( 2 ) = 2 , D ( 3 ) = 6. D(0)=0,\qquad D(1)=0,\qquad D(2)=2,\qquad D(3)=6. D ( 0 ) = 0 , D ( 1 ) = 0 , D ( 2 ) = 2 , D ( 3 ) = 6. 算法恰在 a ∈ { 2 , 3 } a\in\{2,3\} a ∈ { 2 , 3 } 时检测到差异,所以它以概率 2 / 4 = 1 / 2 2/4=1/2 2/4 = 1/2 回答“不同”,而出错概率恰为 1 / 2 1/2 1/2 。因此对这个实例,该保证是紧致的。取 r = 5 r=5 r = 5 个独立样本,只要有一个样本检测到就接受“不同”,则由单边放大,假阴性概率为 ( 1 / 2 ) 5 = 1 / 32 (1/2)^5=1/32 ( 1/2 ) 5 = 1/32 。
反之,如果这一对是 p ( x ) = ( x + 1 ) 2 p(x)=(x+1)^2 p ( x ) = ( x + 1 ) 2 和 q ( x ) = x 2 + 2 x + 1 q(x)=x^2+2x+1 q ( x ) = x 2 + 2 x + 1 ,则这两个多项式相等。例如在 a = 3 a=3 a = 3 处,p ( 3 ) = 16 p(3)=16 p ( 3 ) = 16 而 q ( 3 ) = 9 + 6 + 1 = 16 q(3)=9+6+1=16 q ( 3 ) = 9 + 6 + 1 = 16 。每个样本都给出相等,算法正确地绝不回答“不同”。
要求 ∣ S ∣ ≥ 2 d |S|\ge 2d ∣ S ∣ ≥ 2 d 不可去掉。对同样的 p p p 和 q q q ,若取较小的集合 S = { 0 , 1 } S=\{0,1\} S = { 0 , 1 } ,则两个元素都是 D D D 的根,所以在这对不相等的多项式上,算法以概率 1 1 1 回答“相同”。重复无济于事,因为每个样本都落在根上。根的个数界是关于坏选择的密度的陈述,样本集必须足够大,使这一密度至多为 1 / 2 1/2 1/2 。
多项式为何只有有限多个根
恒等检验依赖一个确定性的代数结论。其假设把非零多项式与恰好在若干采样点取零的多项式区分开来。根的个数是域上多项式的性质;它不要求随机选择样本集。
设 F F F 是域,h ∈ F [ x ] h\in F[x] h ∈ F [ x ] 非零且次数为 d ≥ 0 d\ge0 d ≥ 0 。则 h h h 在 F F F 中至多有 d d d 个互不相同的根。
非零常数没有根。假设低于 d d d 次的情形已成立,并设 a a a 是 d d d 次多项式 h h h 的根。多项式除法给出 h ( x ) = ( x − a ) g ( x ) h(x)=(x-a)g(x) h ( x ) = ( x − a ) g ( x ) ,因为余数为 h ( a ) = 0 h(a)=0 h ( a ) = 0 ,且 g g g 的次数为 d − 1 d-1 d − 1 。若 b ≠ a b\ne a b = a 是另一个根,则 0 = h ( b ) = ( b − a ) g ( b ) 0=h(b)=(b-a)g(b) 0 = h ( b ) = ( b − a ) g ( b ) 。域没有零因子且 b − a ≠ 0 b-a\ne0 b − a = 0 ,所以 g ( b ) = 0 g(b)=0 g ( b ) = 0 。由归纳假设,这样的其他根至多有 d − 1 d-1 d − 1 个,加上 a a a 至多有 d d d 个。若没有第一个根,结论立即成立。
证明计算的是不同的根,而不是重数。例如 ( x − 1 ) 3 (x-1)^3 ( x − 1 ) 3 的次数为三,但只有一个不同的根。它也依赖系数所在的结构是域:在含零因子的环中,不能从乘积为零推出某个因子为零。当样本点数超过次数时,至少有一个点能检测非零差,但预先选定的某个点未必能检测到。随机采样把可能出错的点数转化为针对固定输入的概率界。
概念视角 几何
两条图像可以在何处相交 样本 a a a 未能检测出差异,恰好是 p ( a ) = q ( a ) p(a)=q(a) p ( a ) = q ( a ) ,也就是 p p p 与 q q q 的图像在 x = a x=a x = a 处相交。根的上界说明:两个相异且次数至多为 d d d 的多项式,其图像至多相交于 d d d 点。所以只有随机样本恰好落在这些少数的交点横坐标上,检验才会出错。
令 h ( x ) = x ( x − 1 ) ( x − 2 ) h(x)=x(x-1)(x-2) h ( x ) = x ( x − 1 ) ( x − 2 ) ,S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } S=\{0,1,2,3,4,5,6,7\} S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } 。它的根只有 0 , 1 , 2 0,1,2 0 , 1 , 2 ,所以一次均匀采样漏检的概率为 3 / 8 3/8 3/8 。三次独立采样全部漏检的概率为 ( 3 / 8 ) 3 = 27 / 512 (3/8)^3=27/512 ( 3/8 ) 3 = 27/512 。精确计算与一次采样的一般界 d / ∣ S ∣ = 3 / 8 d/|S|=3/8 d /∣ S ∣ = 3/8 一致。正是三次采样选择的独立性使漏检概率可以相乘。
这一结论对相等的多项式同样有用:相等时差在每一点都为零,因此检验绝不会错误地报告不相等。对不相等的多项式则可能出现另一种错误,因为采样点可能恰是一个根。说明单边错误保证时必须把这两种情形分开。
反例模式
多于 d 个样本点并不足够 一个诱人的说法是:只要样本集满足 ∣ S ∣ > d |S|\gt d ∣ S ∣ > d ,单边错误就至多为 1 / 2 1/2 1/2 ,因为次数至多为 d d d 的非零差至多有 d d d 个根,不可能在整个 S S S 上都为零。取 p ( x ) = x 2 p(x)=x^2 p ( x ) = x 2 、q ( x ) = x q(x)=x q ( x ) = x 、d = 2 d=2 d = 2 以及 S = { 0 , 1 , 2 } S=\{0,1,2\} S = { 0 , 1 , 2 } ,故 ∣ S ∣ = 3 > d |S|=3\gt d ∣ S ∣ = 3 > d 。差 D ( x ) = x 2 − x D(x)=x^2-x D ( x ) = x 2 − x 有 D ( 0 ) = D ( 1 ) = 0 D(0)=D(1)=0 D ( 0 ) = D ( 1 ) = 0 及 D ( 2 ) = 2 D(2)=2 D ( 2 ) = 2 ,所以检验只在 a = 2 a=2 a = 2 时检测到差异。检测概率是 1 / 3 1/3 1/3 ,错误概率是 2 / 3 > 1 / 2 2/3\gt 1/2 2/3 > 1/2 ,恰等于一般界 d / ∣ S ∣ = 2 / 3 d/|S|=2/3 d /∣ S ∣ = 2/3 。根数界只把错误限制在 d / ∣ S ∣ d/|S| d /∣ S ∣ ,所以要得到 1 / 2 1/2 1/2 的保证,需要 ∣ S ∣ ≥ 2 d |S|\ge 2d ∣ S ∣ ≥ 2 d 。
放大的局限与反例
放大定理有其假设,而每个假设都可能以富有启发性的方式失效。
第一个假设是相对于猜测有严格的优势。考虑这样的算法:它忽略输入并输出一次公平硬币的抛掷结果。它在每个输入上正确的概率恰为 1 / 2 1/2 1/2 ,因为对于成员它以概率 1 / 2 1/2 1/2 接受,对于非成员它以概率 1 / 2 1/2 1/2 拒绝。对奇数 r r r ,接受运行的次数 K K K 服从参数为 r r r 和 1 / 2 1/2 1/2 的二项分布,而对称性 K ↔ r − K K\leftrightarrow r-K K ↔ r − K 表明 Pr [ K ≥ ( r + 1 ) / 2 ] = Pr [ K ≤ ( r − 1 ) / 2 ] \Pr[K\ge (r+1)/2]=\Pr[K\le (r-1)/2] Pr [ K ≥ ( r + 1 ) /2 ] = Pr [ K ≤ ( r − 1 ) /2 ] 。这两个事件划分了样本空间,所以每个的概率恰为 1 / 2 1/2 1/2 。对每个奇数 r r r ,多数结果正确的概率恰为 1 / 2 1/2 1/2 ,再多的重复也无法改进它。这就是 BPP 的定义要求概率远离 1 / 2 1/2 1/2 的原因。
成功概率严格大于 1 / 2 1/2 1/2 是不够的。如果它是 1 / 2 + 2 − n 1/2+2^{-n} 1/2 + 2 − n ,则取 δ = 2 − n \delta=2^{-n} δ = 2 − n ,优势命题给出的保证 exp ( − 2 δ 2 r ) \exp(-2\delta^2 r) exp ( − 2 δ 2 r ) 只有在 r ≥ ln 3 / ( 2 δ 2 ) = ( ln 3 / 2 ) 4 n r\ge \ln 3/(2\delta^2)=(\ln 3/2)\,4^{n} r ≥ ln 3/ ( 2 δ 2 ) = ( ln 3/2 ) 4 n 时才低于 1 / 3 1/3 1/3 。这对 n n n 是指数级的,所以此论证不给出多项式时间算法。因此 BPP 式的定义要求常数优势,或者至少是某个多项式的倒数,而该论证建立的是对这类常数变化的封闭性。
第二个假设是放大规则与错误类型相匹配。对于单边错误,在任一次运行接受时就接受是安全的。对于双边错误则不然。假设某算法在每次运行中以 1 / 4 1/4 1/4 的概率接受某个特定的“否”输入;例如,当两个新抽取的公平比特均为零时接受。如果只要 5 5 5 次独立运行中的任一次接受就接受,则假阳性概率变为 1 − ( 3 / 4 ) 5 = 1 − 243 / 1024 = 781 / 1024 ≈ 0.763 1-(3/4)^5=1-243/1024=781/1024\approx 0.763 1 − ( 3/4 ) 5 = 1 − 243/1024 = 781/1024 ≈ 0.763 。“任一次运行接受”的规则把适度的假阳性概率变成了很大的概率。双边错误需要的是多数表决,或者根据两种错误率校准的阈值。
第三个假设是新鲜比特的独立性。如果所有重复都复用同一个随机串,则输出相同,多数结果就等于第一次运行,下面关于复用同一样本点的练习对此作了精确说明。部分依赖则更微妙。方差论证只需要两两独立,但指数界假设的是更强的相互独立,单边情形下的乘积公式同样需要它。
令 L = { 0 k : k ≥ 0 } L=\{0^k:k\ge0\} L = { 0 k : k ≥ 0 } ,固定 n ≥ 1 n\ge1 n ≥ 1 ,并考虑这样的算法:对长度为 n n n 的输入 x x x ,若 x = 0 n x=0^n x = 0 n 则确定性地回答“否”,否则回答正确。在长度为 n n n 的输入上的均匀分布下,它正确的概率为 1 − 2 − n 1-2^{-n} 1 − 2 − n 。在输入 0 n 0^n 0 n 上它以概率 1 1 1 出错,所以独立运行的任何多数结果在那里都不可能是正确的;多数结果也以概率 1 1 1 出错。多数表决命题的假设,即在固定输入上成功概率至少为 2 / 3 2/3 2/3 ,恰恰在算法表现糟糕的输入上失效。因此高的平均准确率对于是否属于 BPP 什么也说明不了。
已证明的与被假定的
区分每个断言的逻辑地位是值得的。先前笔记与本续篇由定义和初等概率论证明以下内容:单边放大、包含关系 P ⊆ R P ⊆ B P P \mathrm P\subseteq\mathrm{RP}\subseteq\mathrm{BPP} P ⊆ RP ⊆ BPP 与 R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP ,以及借助 Chebyshev 不等式、界为 8 / r 8/r 8/ r 的双边错误的多项式级错误降低。
方差论证中使用了 Chebyshev 不等式而未予证明;先前笔记使用 Hoeffding 不等式得到指数界 e − r / 18 e^{-r/18} e − r /18 和 exp ( − 2 δ 2 r ) \exp(-2\delta^2 r) exp ( − 2 δ 2 r ) 。上文证明的根数界支撑着恒等检验。通过多项式时间验证者定义的 N P \mathrm{NP} NP 被用作标准定义。
最后,本单元并不判定 P = R P \mathrm P=\mathrm{RP} P = RP 、R P = B P P \mathrm{RP}=\mathrm{BPP} RP = BPP 或 R P = N P \mathrm{RP}=\mathrm{NP} RP = NP 是否成立,这里所证明的内容并未解决这些问题。这些论证只表明,所述的错误常数是约定,不会改变这些类。
练习与解答
快速检查
(对 p ( x ) = x 3 p(x)=x^3 p ( x ) = x 3 和 q ( x ) = x q(x)=x q ( x ) = x ,取 d = 3 d=3 d = 3 以及 S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } S=\{0,1,2,3,4,5,6,7\} S = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } ,运行恒等检验。一次运行检测到差异的概率是多少?三次独立运行之后的假阴性概率是多少?)
把 D = p − q D=p-q D = p − q 分解,数一数它在 S S S 内的根。
解答 · 答案 差为 D ( x ) = x 3 − x = x ( x − 1 ) ( x + 1 ) D(x)=x^3-x=x(x-1)(x+1) D ( x ) = x 3 − x = x ( x − 1 ) ( x + 1 ) 。它在 S S S 上的取值为 D ( 0 ) = 0 D(0)=0 D ( 0 ) = 0 ,D ( 1 ) = 0 D(1)=0 D ( 1 ) = 0 ,D ( 2 ) = 6 D(2)=6 D ( 2 ) = 6 ,D ( 3 ) = 24 D(3)=24 D ( 3 ) = 24 ,D ( 4 ) = 60 D(4)=60 D ( 4 ) = 60 ,D ( 5 ) = 120 D(5)=120 D ( 5 ) = 120 ,D ( 6 ) = 210 D(6)=210 D ( 6 ) = 210 以及 D ( 7 ) = 336 D(7)=336 D ( 7 ) = 336 。只有 a = 0 a=0 a = 0 和 a = 1 a=1 a = 1 未能检测到差异。一次运行以概率 6 / 8 = 3 / 4 6/8=3/4 6/8 = 3/4 检测到差异,以概率 1 / 4 1/4 1/4 漏掉。三次独立运行全部漏掉的概率为 ( 1 / 4 ) 3 = 1 / 64 (1/4)^3=1/64 ( 1/4 ) 3 = 1/64 。实际的漏检概率低于界 d / ∣ S ∣ = 3 / 8 d/|S|=3/8 d /∣ S ∣ = 3/8 ,因为根 − 1 -1 − 1 位于 S S S 之外。
快速检查
(在三个元素的域上,令 h ( x ) = x 2 + 1 h(x)=x^2+1 h ( x ) = x 2 + 1 。计算它在每个域元素处的值,根的个数与次数界相比如何?)
取元素 0 , 1 , 2 0,1,2 0 , 1 , 2 ,并按模 3 3 3 计算。
解答 · 答案 各值为 h ( 0 ) = 1 h(0)=1 h ( 0 ) = 1 、h ( 1 ) = 2 h(1)=2 h ( 1 ) = 2 和 h ( 2 ) = 5 = 2 h(2)=5=2 h ( 2 ) = 5 = 2 。该域中没有根,这与至多两个根的上界一致:根数界只是上界,不一定取得到。
快速检查
(对例题中的三次差多项式,若重复使用同一个均匀选取的样本点三次,三次检查全部漏检的概率是多少?)
解答 · 答案 三次结果相同,因此全部漏检恰当且仅当该样本点是三个根之一。概率为 3 / 8 3/8 3/8 ,而不是 27 / 512 27/512 27/512 ;后者需要独立选择。