随机选择可以简化算法,但概率保证必须说明覆盖哪些输入,以及哪些答案可能出错。复杂度类使用的是对输入的最坏情形保证,以及对算法自身随机比特的概率,而不是假设输入服从某个分布。
本单元有三个目标。第一,准确说明一个概率陈述所描述的是什么试验。第二,定义类 R P \mathrm{RP} RP 与 B P P \mathrm{BPP} BPP ,并说明其中的常数只是约定,因为独立重复可以把错误率降低。第三,区分哪些结论可以由第一性原理证明,哪些是引入的。下面证明了两种不同的放大论证,一种依赖所引用的集中不等式,另一种完全是初等的。若干反例说明了每个假设在何处是必要的。
动机与概率空间
确定性算法在每个输入上只有一条计算路径,其正确性是关于该路径的是非性质。随机算法在每个输入上有许多条路径,每一条对应它可能读取的一个随机比特序列。于是正确性变成了一个关于“好路径”集合有多大的问题。在陈述任何定理之前,我们必须精确说明样本空间是什么。
设 M M M 是一个随机算法,对长度为 n n n 的输入,无论随机比特如何选择,其运行时间至多为多项式 p ( n ) p(n) p ( n ) 。这样的算法读取的随机比特不会超过 p ( n ) p(n) p ( n ) 个。因此我们可以进行填充,并把随机输入看作均匀选取的字符串 ρ ∈ { 0 , 1 } p ( n ) \rho\in\{0,1\}^{p(n)} ρ ∈ { 0 , 1 } p ( n ) ,并用 M ( x , ρ ) M(x,\rho) M ( x , ρ ) 表示输入为 x x x 、随机串为 ρ \rho ρ 时的输出。对于固定的输入 x x x ,接受概率为
Pr ρ [ M ( x , ρ ) = 1 ] = ∣ { ρ ∈ { 0 , 1 } p ( n ) : M ( x , ρ ) = 1 } ∣ 2 p ( n ) . \Pr_\rho[M(x,\rho)=1]=\frac{\left|\{\rho\in\{0,1\}^{p(n)} : M(x,\rho)=1\}\right|}{2^{p(n)}}. ρ Pr [ M ( x , ρ ) = 1 ] = 2 p ( n ) { ρ ∈ { 0 , 1 } p ( n ) : M ( x , ρ ) = 1 } .
这是关于有限集合的计数陈述,因此不需要测度论。以下三个推论贯穿始终。
每个接受概率都是分母为 2 2 2 的幂的有理数。
概率依附于固定的输入 x x x 。不存在隐藏的输入分布,因此这些类中的保证是对每个输入分别成立的陈述。
独立重复对应于串联字符串 ρ 1 , … , ρ r \rho_1,\dots,\rho_r ρ 1 , … , ρ r ,其中每个都是均匀且相互独立地抽取的,因此联合样本空间是带有均匀测度的 { 0 , 1 } r p ( n ) \{0,1\}^{rp(n)} { 0 , 1 } r p ( n ) 。独立性就是这个空间的乘积结构,而不是额外叠加在其上的假设。
因此每个保证中都出现三个量词。全称量词遍历输入。概率遍历算法自身的比特。运行时间界遍历所有比特串,包括不走运的那些。去掉最后一项会改变模型,因为在极小比例的随机串上永远运行的算法,并不是本文所用意义下的多项式时间算法。
错误保证
若存在随机多项式时间算法,使得对不属于 L L L 的每个输入以概率 1 1 1 拒绝,对属于 L L L 的每个输入以至少 1 / 2 1/2 1/2 的概率接受,则称语言 L L L 属于 R P \mathrm{RP} RP 。若存在随机多项式时间算法,使得在每个输入上以至少 2 / 3 2/3 2/3 的概率返回正确答案,则称 L L L 属于 B P P \mathrm{BPP} BPP 。这些概率是对独立的无偏随机比特而言的;时间界对这些比特的每一种选择都成立。
这些常数只是约定:对于双边错误,任何严格大于 1 / 2 1/2 1/2 的固定成功概率都可以被放大。对于 RP,独立重复并在任一次运行接受时就接受,可以保持零假阳性,同时降低假阴性。因此 P ⊆ R P ⊆ B P P \mathrm P\subseteq\mathrm{RP}\subseteq\mathrm{BPP} P ⊆ RP ⊆ BPP :确定性过程只需忽略其随机比特,而 RP 算法可以先重复固定次数以达到 BPP 的成功阈值。
给这两种错误命名是有帮助的。假阳性是指接受了不属于 L L L 的输入,假阴性是指拒绝了属于 L L L 的输入。RP 算法只可能犯假阴性错误,并且对 L L L 中的每个成员,出错概率至多为 1 / 2 1/2 1/2 。因此它的答案“接受”总是可信的,而“拒绝”只是提示性的。BPP 算法可能犯任一种错误,但对每个输入,无论是否为成员,给出错误答案的概率至多为 1 / 3 1/3 1/3 。
设算法的每次独立运行在固定输入上正确的概率至少为 2 / 3 2/3 2/3 。对奇数 r r r ,r r r 次独立运行的多数结果的错误概率至多为 e − r / 18 e^{-r/18} e − r /18 。对于多项式次数的重复,运行时间仍为多项式。
令 X i X_i X i 表示第 i i i 次运行给出错误答案。这些独立变量取值于 [ 0 , 1 ] [0,1] [ 0 , 1 ] ,且 E [ ∑ X i ] ≤ r / 3 \mathbb E[\sum X_i]\le r/3 E [ ∑ X i ] ≤ r /3 。只有当 ∑ X i ≥ r / 2 \sum X_i\ge r/2 ∑ X i ≥ r /2 时多数结果才是错误的,这比期望至少高出 r / 6 r/6 r /6 。Hoeffding 不等式给出概率至多为 exp ( − 2 ( r / 6 ) 2 / r ) = e − r / 18 \exp(-2(r/6)^2/r)=e^{-r/18} exp ( − 2 ( r /6 ) 2 / r ) = e − r /18 。此处使用该集中不等式时未予证明。把多项式运行时间乘以多项式次数的重复,结果仍为多项式。
此论证中的每个假设都有其作用。固定输入之所以重要,是因为该界是对每个输入而言的陈述。各次运行的独立性使得可以使用 Hoeffding 不等式。r r r 为奇数排除了平局,从而使“多数”有明确定义。误差变量 X i X_i X i 不必具有相同的分布,因为只用到 E [ X i ] ≤ 1 / 3 \mathbb E[X_i]\le 1/3 E [ X i ] ≤ 1/3 。如果某些运行的出错概率更小,则期望和更小,差值 r / 2 − E [ ∑ X i ] r/2-\mathbb E[\sum X_i] r /2 − E [ ∑ X i ] 至少为 r / 6 r/6 r /6 ,所以该界只会更好。所用形式的 Hoeffding 不等式是说:对于独立的 X i ∈ [ 0 , 1 ] X_i\in[0,1] X i ∈ [ 0 , 1 ] ,令 S = ∑ i = 1 r X i S=\sum\limits_{i=1}^r X_i S = i = 1 ∑ r X i ,则对任意 t > 0 t>0 t > 0 ,Pr [ S − E [ S ] ≥ t ] ≤ exp ( − 2 t 2 / r ) \Pr[S-\mathbb E[S]\ge t]\le\exp(-2t^2/r) Pr [ S − E [ S ] ≥ t ] ≤ exp ( − 2 t 2 / r ) 。
界如何依赖于优势
常数 2 / 3 2/3 2/3 并不特殊。把单次运行的成功概率写成 1 / 2 + δ 1/2+\delta 1/2 + δ ,则 δ \delta δ 称为相对于随机猜测的优势。同样的证明给出下面更一般的陈述,它解释了为什么在 B P P \mathrm{BPP} BPP 的定义中,任何大于 1 / 2 1/2 1/2 的固定成功概率都可以代替 2 / 3 2/3 2/3 。
设 0 < δ ≤ 1 / 2 0<\delta\le 1/2 0 < δ ≤ 1/2 。假设 r r r 次独立运行(r r r 为奇数)中的每一次在固定输入上正确的概率至少为 1 / 2 + δ 1/2+\delta 1/2 + δ 。则多数答案错误的概率至多为 exp ( − 2 δ 2 r ) \exp(-2\delta^2 r) exp ( − 2 δ 2 r ) 。特别地,为使错误至多为 ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,只需取任一奇数 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge \ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 。
令 X i ∈ { 0 , 1 } X_i\in\{0,1\} X i ∈ { 0 , 1 } 表示第 i i i 次运行出错,则 E [ X i ] ≤ 1 / 2 − δ \mathbb E[X_i]\le 1/2-\delta E [ X i ] ≤ 1/2 − δ ,且 S = ∑ X i S=\sum X_i S = ∑ X i 满足 E [ S ] ≤ r ( 1 / 2 − δ ) \mathbb E[S]\le r(1/2-\delta) E [ S ] ≤ r ( 1/2 − δ ) 。只有当 S ≥ r / 2 S\ge r/2 S ≥ r /2 时多数结果才是错误的,这比均值至少高出 r / 2 − E [ S ] ≥ δ r r/2-\mathbb E[S]\ge \delta r r /2 − E [ S ] ≥ δ r 。Hoeffding 不等式(未予证明而使用)给出概率至多为 exp ( − 2 ( δ r ) 2 / r ) = exp ( − 2 δ 2 r ) \exp(-2(\delta r)^2/r)=\exp(-2\delta^2 r) exp ( − 2 ( δ r ) 2 / r ) = exp ( − 2 δ 2 r ) 。令 exp ( − 2 δ 2 r ) ≤ ε \exp(-2\delta^2 r)\le\varepsilon exp ( − 2 δ 2 r ) ≤ ε 并解出 r r r ,得 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge\ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 。取 δ = 1 / 6 \delta=1/6 δ = 1/6 即恢复前一命题的界 e − r / 18 e^{-r/18} e − r /18 。
反例模式
没有优势就无法放大 断言:对每个单次成功概率,多数表决都会使错误下降。设算法无视输入,输出它的第一个随机比特。对每个输入,它恰以概率 1 / 2 1/2 1/2 答对。取 r = 3 r=3 r = 3 次独立运行,三个比特中至少两个答对时多数才答对,概率为 ( 3 + 1 ) / 8 = 1 / 2 (3+1)/8=1/2 ( 3 + 1 ) /8 = 1/2 。由公平比特在 0 ↔ 1 0\leftrightarrow1 0 ↔ 1 下的对称性,任意奇数 r r r 次运行的多数同样恰以 1 / 2 1/2 1/2 答对,所以错误从不下降。这与优势界并不矛盾:此处 δ = 0 \delta=0 δ = 0 ,而 exp ( − 2 δ 2 r ) = 1 \exp(-2\delta^2r)=1 exp ( − 2 δ 2 r ) = 1 什么也没说。修正:要求固定的优势 δ > 0 \delta>0 δ > 0 ;这时 r ≥ ln ( 1 / ε ) / ( 2 δ 2 ) r\ge\ln(1/\varepsilon)/(2\delta^2) r ≥ ln ( 1/ ε ) / ( 2 δ 2 ) 次重复就足够。
对 δ \delta δ 的依赖体现在分母中的二次方。如果 δ \delta δ 是固定常数,甚至是输入长度的某个多项式的倒数,那么对任意多项式 q q q ,多项式次数的重复就足以使错误达到 2 − q ( n ) 2^{-q(n)} 2 − q ( n ) ,因为 ln ( 1 / ε ) = q ( n ) ln 2 \ln(1/\varepsilon)=q(n)\ln 2 ln ( 1/ ε ) = q ( n ) ln 2 是多项式。如果 δ \delta δ 是指数级小的,则所需的重复次数是指数级的,这个论证就没有任何用处。
数值解读该界
像 e − r / 18 e^{-r/18} e − r /18 这样的界,只有在被换算成具体的重复次数之后才有用。接下来的两个例子说明如何做到这一点,以及该界有多保守。
设某 BPP 算法在每个输入上正确的概率至少为 2 / 3 2/3 2/3 。我们希望得到一个多数表决算法,其在每个输入上的错误至多为 2 − 20 2^{-20} 2 − 20 。
由多数表决放大命题,只需 e − r / 18 ≤ 2 − 20 e^{-r/18}\le 2^{-20} e − r /18 ≤ 2 − 20 且 r r r 为奇数。取对数,r / 18 ≥ 20 ln 2 r/18\ge 20\ln 2 r /18 ≥ 20 ln 2 ,即 r ≥ 360 ln 2 r\ge 360\ln 2 r ≥ 360 ln 2 。由于 ln 2 ≈ 0.693147 \ln 2\approx 0.693147 ln 2 ≈ 0.693147 ,得 360 ln 2 ≈ 249.53 360\ln 2\approx 249.53 360 ln 2 ≈ 249.53 。整数 250 250 250 及更大的整数满足该不等式,但 250 250 250 是偶数,可能产生平局,所以最小的可行奇数值是 r = 251 r=251 r = 251 。作为检验,251 / 18 ≈ 13.944 251/18\approx 13.944 251/18 ≈ 13.944 ,而 20 ln 2 ≈ 13.863 20\ln 2\approx 13.863 20 ln 2 ≈ 13.863 ,因此 e − 251 / 18 < 2 − 20 e^{-251/18}\lt 2^{-20} e − 251/18 < 2 − 20 ,符合要求。相反,249 / 18 ≈ 13.833 < 13.863 249/18\approx 13.833\lt 13.863 249/18 ≈ 13.833 < 13.863 ,不满足该不等式。
该命题给出的是可能远离真实值的上界。下一个例子计算小规模多数表决的精确错误,并将其与所保证的界作比较。
例题 1.1.5
(小规模多数表决的精确错误与所保证的界)
设单次运行在固定输入上的错误概率恰为 1 / 4 1/4 1/4 。这符合有界公平比特模型:两个新的公平比特有四个等可能结果,错误事件可以是结果 00 00 00 。固定有限个公平比特不可能产生恰为 1 / 3 1/3 1/3 的概率;BPP 定义中的 1 / 3 1/3 1/3 是上界,不要求实际达到。对奇数 r r r ,独立重复后的精确多数错误概率为
∑ k = ( r + 1 ) / 2 r ( r k ) ( 1 4 ) k ( 3 4 ) r − k = 1 4 r ∑ k = ( r + 1 ) / 2 r ( r k ) 3 r − k . \sum_{k=(r+1)/2}^{r}\binom rk\left(\frac14\right)^k\left(\frac34\right)^{r-k}=\frac1{4^r}\sum_{k=(r+1)/2}^{r}\binom rk 3^{\,r-k}. k = ( r + 1 ) /2 ∑ r ( k r ) ( 4 1 ) k ( 4 3 ) r − k = 4 r 1 k = ( r + 1 ) /2 ∑ r ( k r ) 3 r − k .
当 r = 1 r=1 r = 1 时,错误为 1 / 4 = 0.25 1/4=0.25 1/4 = 0.25 。
当 r = 3 r=3 r = 3 时,分子为 3 ⋅ 3 + 1 = 10 3\cdot3+1=10 3 ⋅ 3 + 1 = 10 ,所以错误为 10 / 64 = 5 / 32 = 0.15625 10/64=5/32=0.15625 10/64 = 5/32 = 0.15625 ,小于一般界 e − 1 / 6 ≈ 0.846 e^{-1/6}\approx0.846 e − 1/6 ≈ 0.846 。
当 r = 5 r=5 r = 5 时,分子为 10 ⋅ 9 + 5 ⋅ 3 + 1 = 106 10\cdot9+5\cdot3+1=106 10 ⋅ 9 + 5 ⋅ 3 + 1 = 106 ,所以错误为 106 / 1024 = 53 / 512 ≈ 0.104 106/1024=53/512\approx0.104 106/1024 = 53/512 ≈ 0.104 ,小于 e − 5 / 18 ≈ 0.757 e^{-5/18}\approx0.757 e − 5/18 ≈ 0.757 。
当 r = 7 r=7 r = 7 时,分子为 35 ⋅ 27 + 21 ⋅ 9 + 7 ⋅ 3 + 1 = 1156 35\cdot27+21\cdot9+7\cdot3+1=1156 35 ⋅ 27 + 21 ⋅ 9 + 7 ⋅ 3 + 1 = 1156 ,所以错误为 1156 / 16384 = 289 / 4096 ≈ 0.071 1156/16384=289/4096\approx0.071 1156/16384 = 289/4096 ≈ 0.071 ,小于 e − 7 / 18 ≈ 0.678 e^{-7/18}\approx0.678 e − 7/18 ≈ 0.678 。
这四个取值的精确错误依次下降。由于 1 / 4 ≤ 1 / 3 1/4\le1/3 1/4 ≤ 1/3 ,所引上界仍然适用,但有意保留了较松的估计。它的价值在于:对任何奇数次重复,以及任意一组各自错误概率至多为 1 / 3 1/3 1/3 的独立运行,都给出简单的指数保证。精确的二项式计算要求各次概率相同,一般上界则不需要这一条件。
一个单边的例子
假设某 RP 算法每次运行以至少 1 / 2 1/2 1/2 的概率接受一个“是”输入。在 r r r 次独立运行中,只要有一次运行接受就接受,则漏掉该输入的概率至多为 ( 1 / 2 ) r (1/2)^r ( 1/2 ) r 。对于“否”输入,每次运行都以概率 1 1 1 拒绝,所以组合后的算法绝不会接受“否”输入。乘积界需要独立性;重复使用同一个随机种子未必能改进错误。
声称某算法在某个分布下对 99% 的输入是正确的,这是平均情形的断言。BPP 则要求其成功率界对每个输入分别成立,概率取自全新的内部随机比特。一个算法可以平均表现良好,却在某个特定输入上始终失败。
上面的具体计算并未用到常数 1 / 2 1/2 1/2 或某个特定算法的任何特殊性,因此可以一般性地陈述并证明。
设 M M M 是运行时间为 T ( n ) T(n) T ( n ) 的随机算法,使得不属于 L L L 的每个输入以概率 1 1 1 被拒绝,且属于 L L L 的每个输入以至少 1 − ε 1-\varepsilon 1 − ε 的概率被接受,其中 ε ∈ [ 0 , 1 ) \varepsilon\in[0,1) ε ∈ [ 0 , 1 ) 。令 M ( r ) M^{(r)} M ( r ) 在 r r r 个独立的随机串上运行 M M M ,且恰当至少有一次运行接受时才接受。则 M ( r ) M^{(r)} M ( r ) 以概率 1 1 1 拒绝不属于 L L L 的每个输入,并以至少 1 − ε r 1-\varepsilon^r 1 − ε r 的概率接受属于 L L L 的每个输入。其运行时间为 O ( r T ( n ) ) O(r\,T(n)) O ( r T ( n )) 加上簿记开销。
固定输入 x x x ,并令 ρ 1 , … , ρ r \rho_1,\dots,\rho_r ρ 1 , … , ρ r 为独立的随机串。若 x ∉ L x\notin L x ∈ / L ,则每次运行对每个串都拒绝,或者至少以概率 1 1 1 拒绝,所以全部 r r r 次运行以概率 1 1 1 都拒绝,组合后的算法拒绝。若 x ∈ L x\in L x ∈ L ,则组合后的算法恰在所有运行都拒绝时才拒绝。由独立性,这一事件的概率是各次拒绝概率的乘积,每个至多为 ε \varepsilon ε ,因此至多为 ε r \varepsilon^r ε r 。运行时间是 r r r 次运行时间之和,再加上每次运行用于记录是否发生接受的常数开销。
取 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 以及对某个多项式 q q q 取 r = q ( n ) r=q(n) r = q ( n ) ,则假阴性概率至多为 2 − q ( n ) 2^{-q(n)} 2 − q ( n ) 。此外 ε \varepsilon ε 不必为 1 / 2 1/2 1/2 :任何至多为 1 − 1 / p o l y ( n ) 1-1/\mathrm{poly}(n) 1 − 1/ poly ( n ) 的单边错误界,都可以通过多项式次数的重复被降低为指数级小的错误,因为当 p ≥ 1 p\ge1 p ≥ 1 时 ( 1 − 1 / p ) p q ≤ e − q (1-1/p)^{pq}\le e^{-q} ( 1 − 1/ p ) pq ≤ e − q ;下面的练习处理常数界 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 的情形。
P、RP 与 BPP 之间的包含关系
在讨论错误保证时陈述的包含关系现在予以证明,并附带证明与 N P \mathrm{NP} NP 的另一个关系。回忆:当存在多项式时间确定性验证者 V V V 和多项式 q q q ,使得 x ∈ L x\in L x ∈ L 当且仅当存在某个满足 ∣ w ∣ = q ( ∣ x ∣ ) |w|=q(|x|) ∣ w ∣ = q ( ∣ x ∣ ) 的证书 w w w 使 V ( x , w ) V(x,w) V ( x , w ) 接受时,L ∈ N P L\in\mathrm{NP} L ∈ NP 。
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 。
P ⊆ R P \mathrm P\subseteq\mathrm{RP} P ⊆ RP :对 L L L 的确定性多项式时间判定器,在忽略其随机比特的情况下运行,以概率 1 ≥ 1 / 2 1\ge 1/2 1 ≥ 1/2 接受每个成员,并以概率 1 1 1 拒绝每个非成员。
R P ⊆ B P P \mathrm{RP}\subseteq\mathrm{BPP} RP ⊆ BPP :设 M M M 见证 L ∈ R P L\in\mathrm{RP} L ∈ RP ,考虑这样的算法:在独立的串上运行 M M M 两次,若任一次运行接受则接受。由单边放大命题,取 ε = 1 / 2 \varepsilon=1/2 ε = 1/2 且 r = 2 r=2 r = 2 ,它以概率 1 1 1 拒绝每个非成员,并以至少 1 − 1 / 4 = 3 / 4 ≥ 2 / 3 1-1/4=3/4\ge 2/3 1 − 1/4 = 3/4 ≥ 2/3 的概率接受每个成员。所以它在每个输入上以至少 2 / 3 2/3 2/3 的概率给出正确答案,并且以多项式时间运行。
R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP :设 M M M 至多使用 p ( n ) p(n) p ( n ) 个随机比特。定义验证者 V ( x , w ) V(x,w) V ( x , w ) :它在 x x x 上模拟 M M M ,把证书 w ∈ { 0 , 1 } p ( ∣ x ∣ ) w\in\{0,1\}^{p(|x|)} w ∈ { 0 , 1 } p ( ∣ x ∣ ) 用作随机串,并恰在 M M M 接受时接受。这是一个多项式时间的确定性计算。若 x ∈ L x\in L x ∈ L ,则接受概率为正,所以有限多个随机串中至少有一个使 M M M 接受,因而存在好的证书。若 x ∉ L x\notin L x ∈ / L ,则没有任何串使 M M M 接受,所以没有证书被接受。
证明透视
每个包含关系用到什么 每个包含关系用到定义的不同部分。P ⊆ R P \mathrm P\subseteq\mathrm{RP} P ⊆ RP 只需要确定性算法可以忽略它的随机比特。R P ⊆ B P P \mathrm{RP}\subseteq\mathrm{BPP} RP ⊆ BPP 需要放大:单次运行的假阴性概率 1 / 2 1/2 1/2 对 BPP 的门槛太大,所以把两次独立运行用 OR 合并,得到 3 / 4 ≥ 2 / 3 3/4\ge2/3 3/4 ≥ 2/3 ,而非成员仍以概率 1 1 1 被拒绝。R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP 正是单边错误不可或缺之处:恰恰是零假阳性这一性质,把一个好的随机串变成了可验证的证书。练习会问对于 BPP 哪里行不通。
这些论证都没有表明任何一个包含关系是严格的。这些类是否重合的问题,并不能由本单元中的任何内容解决。
练习与解答
快速检查
(需要多少次独立的 RP 重复,才足以使假阴性概率至多为 1 / 32 1/32 1/32 ?)
解答 · 答案 五次重复就足够,因为 ( 1 / 2 ) 5 = 1 / 32 (1/2)^5=1/32 ( 1/2 ) 5 = 1/32 。
快速检查
(为什么如果所有重复都使用完全相同的随机比特,多数表决就不能保证降低错误?)
解答 · 答案 这时每次重复的输出可能完全相同。多数结果返回的答案与第一次运行相同,所以其错误概率可能不变;独立试验的界不适用。
快速检查
(某随机算法在固定输入上的出错概率恰为 1 / 4 1/4 1/4 。计算 3 3 3 次独立运行的多数结果的精确错误概率。)
解答 · 答案 当至少两次运行出错时,三次运行的多数结果是错误的。恰有两次错误的概率为 3 ⋅ ( 1 / 4 ) 2 ⋅ ( 3 / 4 ) = 9 / 64 3\cdot(1/4)^2\cdot(3/4)=9/64 3 ⋅ ( 1/4 ) 2 ⋅ ( 3/4 ) = 9/64 ,三次都错的概率为 ( 1 / 4 ) 3 = 1 / 64 (1/4)^3=1/64 ( 1/4 ) 3 = 1/64 。总和为 10 / 64 = 5 / 32 = 0.15625 10/64=5/32=0.15625 10/64 = 5/32 = 0.15625 ,它小于单次运行的错误 1 / 4 1/4 1/4 。
快速检查
(利用成功概率为 2 / 3 2/3 2/3 时的指数界,求一个保证错误至多为 10 − 6 10^{-6} 1 0 − 6 的奇数重复次数。)
解答 · 答案 我们需要 e − r / 18 ≤ 10 − 6 e^{-r/18}\le 10^{-6} e − r /18 ≤ 1 0 − 6 ,所以 r ≥ 18 ln ( 10 6 ) = 18 ⋅ 6 ln 10 ≈ 18 ⋅ 13.8155 ≈ 248.68 r\ge 18\ln(10^6)=18\cdot 6\ln 10\approx 18\cdot 13.8155\approx 248.68 r ≥ 18 ln ( 1 0 6 ) = 18 ⋅ 6 ln 10 ≈ 18 ⋅ 13.8155 ≈ 248.68 。不小于 248.68 248.68 248.68 的最小奇整数是 r = 249 r=249 r = 249 。作为检验,249 / 18 ≈ 13.833 ≥ 13.8155 249/18\approx 13.833\ge 13.8155 249/18 ≈ 13.833 ≥ 13.8155 ,所以 e − 249 / 18 ≤ 10 − 6 e^{-249/18}\le 10^{-6} e − 249/18 ≤ 1 0 − 6 。
快速检查
(某算法从不接受非成员,并以至少 1 / 3 1/3 1/3 的概率接受每个成员。多少次独立重复(只要任一次运行接受就接受)能保证假阴性概率至多为 1 / 100 1/100 1/100 ?)
取 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 。
解答 · 答案 应用单边放大,取 ε = 2 / 3 \varepsilon=2/3 ε = 2/3 :我们需要 ( 2 / 3 ) r ≤ 1 / 100 (2/3)^r\le 1/100 ( 2/3 ) r ≤ 1/100 。由于 ( 2 / 3 ) 11 = 2048 / 177147 ≈ 0.01156 > 0.01 (2/3)^{11}=2048/177147\approx 0.01156\gt 0.01 ( 2/3 ) 11 = 2048/177147 ≈ 0.01156 > 0.01 而 ( 2 / 3 ) 12 = 4096 / 531441 ≈ 0.00771 ≤ 0.01 (2/3)^{12}=4096/531441\approx 0.00771\le 0.01 ( 2/3 ) 12 = 4096/531441 ≈ 0.00771 ≤ 0.01 ,最小的充分次数是 r = 12 r=12 r = 12 。等价地,r ≥ ln 100 / ln ( 3 / 2 ) ≈ 4.605 / 0.4055 ≈ 11.36 r\ge\ln 100/\ln(3/2)\approx 4.605/0.4055\approx 11.36 r ≥ ln 100/ ln ( 3/2 ) ≈ 4.605/0.4055 ≈ 11.36 。
快速检查
(某次运行在固定输入上正确的概率至少为 0.6 0.6 0.6 。利用优势命题,求一个奇数次运行,使得多数结果正确的概率至少为 2 / 3 2/3 2/3 。)
解答 · 答案 这里 δ = 0.1 \delta=0.1 δ = 0.1 ,所以多数结果错误的概率至多为 exp ( − 2 ⋅ 0.01 ⋅ r ) = e − r / 50 \exp(-2\cdot 0.01\cdot r)=e^{-r/50} exp ( − 2 ⋅ 0.01 ⋅ r ) = e − r /50 。我们需要 e − r / 50 ≤ 1 / 3 e^{-r/50}\le 1/3 e − r /50 ≤ 1/3 ,即 r ≥ 50 ln 3 ≈ 50 ⋅ 1.0986 ≈ 54.93 r\ge 50\ln 3\approx 50\cdot 1.0986\approx 54.93 r ≥ 50 ln 3 ≈ 50 ⋅ 1.0986 ≈ 54.93 。不小于 54.93 54.93 54.93 的最小奇整数是 r = 55 r=55 r = 55 ,并且确实 e − 1.1 ≈ 0.3329 ≤ 1 / 3 e^{-1.1}\approx 0.3329\le 1/3 e − 1.1 ≈ 0.3329 ≤ 1/3 。这是由上界得到的充分次数,不一定是达到目标的最小次数。
快速检查
(R P ⊆ N P \mathrm{RP}\subseteq\mathrm{NP} RP ⊆ NP 的证明把随机串当作证书。解释为什么同样的想法不能证明 B P P ⊆ N P \mathrm{BPP}\subseteq\mathrm{NP} BPP ⊆ NP 。)
解答 · 答案 对于 BPP 语言,成员至少有 2 / 3 2/3 2/3 比例的接受随机串,所以存在接受串。但非成员仍可能有至多 1 / 3 1/3 1/3 比例的接受串,因为 BPP 允许假阳性。一个在模拟于证书上接受时就接受的验证者,因而会接受某些非成员,这违反了 NP 的要求,即对非成员没有任何证书被接受。RP 的零假阳性性质恰恰使该模拟成为一个可靠的验证者。
续篇《方差界与随机恒等检验》继续讨论方差论证与多项式恒等检验。