本續篇以前一篇筆記中的 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 ) ,切比雪夫不等式便甚麼也推不出。
此證明有兩個特點值得一提。第一,它僅通過方差的可加性使用獨立性,而只要各次運行是兩兩獨立的,這一點就已成立。先前筆記中的 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 ,則優勢命題給出的保證 exp ( − 2 δ 2 r ) \exp(-2\delta^2 r) exp ( − 2 δ 2 r ) (其中 δ = 2 − n \delta=2^{-n} δ = 2 − n )要到 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 ,以及借助切比雪夫不等式、以界 8 / r 8/r 8/ r 對雙側錯誤作多項式級的錯誤降低。
方差論證中使用了切比雪夫不等式但未加證明;先前筆記使用 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 ;後者需要獨立選擇。