View source for 概率论与数理统计 (Spring 2023)/Two-point sampling

=  利用线性同余方程构造两两独立的随机变量 =
令<math>p</math>为一质数。考虑模<math>p</math>余数构成的集合<math>[p]=\{0,1,\ldots,p-1\}=\mathbb{Z}_p</math>。众所周知，当<math>p</math>为质数时，<math>\mathbb{Z}_p</math>为对模<math>p</math>加法和乘法运算闭合的'''有限域'''。

我们现在构造一系列值域为<math>[p]</math>的'''两两独立'''（'''pairwise Independent'''）且'''均匀分布'''（'''uniformly distributed'''）的随机变量<math>X_{0},X_{1},\ldots,X_{p-1}</math>。构造如下：
* 令<math>\boldsymbol{a},\boldsymbol{b}\in[p]</math>为一对相互独立的取值在<math>[p]</math>上均匀分布的随机变量；
* 对于每个<math>i\in[p]</math>，定义 <math>X_i=(\boldsymbol{a}\cdot i+\boldsymbol{b})\bmod p</math>。

我们证明如此构造的随机变量序列<math>X_{0},X_{1},\ldots,X_{p-1}</math>的确两两独立且在<math>[p]</math>上均匀分布。

{{Theorem
|定理一|
#（''均匀分布''）对于任何<math>i\in[p]</math>，任意取值<math>c\in[p]</math>，有
#::<math>\Pr(X_i=c)=\frac{1}{p}</math>
#（''两两独立性''）对于任何不同的<math>i,j\in[p]</math>，以及任意取值<math>c,d\in[p]</math>，有
#::<math>\Pr(X_i=c\cap X_j=d)=\frac{1}{p^2}</math>
}}
{{Proof| 首先验证每个<math>X_i</math>在其值域<math>[p]</math>上都是均匀分布的。根据全概率法则：
:<math>
\begin{align}
\Pr(X_i=c)
&=
\Pr\left((\boldsymbol{a}\cdot i+\boldsymbol{b})=c\pmod p\right)\\
&=
\sum_{a\in[p]}\frac{1}{p}\Pr\left(\boldsymbol{b}\equiv c-a\cdot i\pmod{p}\right)\\
&=
\frac{1}{p}.
\end{align}</math>
其中，最后一个等式成立是因为对于任意的<math>i,a,c\in[p]</math>，仅有唯一的取值<math>b\in[p]</math>满足同余关系<math>b\equiv c-a\cdot i\pmod{p}</math>，因此
<math>\Pr\left(\boldsymbol{b}\equiv c-a\cdot i\pmod{p}\right)=\frac{1}{p}</math>.

其次验证没对不同的<math>X_i,X_j</math>之间的两两独立性。注意到，对任意不同<math>i,j\in[p]</math>和任意取值<math>c,d\in[p]</math>，如下以<math>\boldsymbol{a}</math>和<math>\boldsymbol{b}</math>为未知量的线性同余方程组：
:<math>
\begin{cases}
(\boldsymbol{a}\cdot i+\boldsymbol{b})\equiv c\pmod{p}\\
(\boldsymbol{a}\cdot j+\boldsymbol{b})\equiv d\pmod{p}
\end{cases}
</math>
有唯一解<math>a,b\in[p]</math>。这是因为<math>\mathbb{Z}_p</math>为一合法的有限域。因此，
:<math>
\Pr(X_i=c\cap X_j=d)=\Pr(\boldsymbol{a}=a\cap \boldsymbol{b}=b)
=\frac{1}{p^2}
</math>
}}

=两点采样（Two-point sampling）=
令<math>f:\{0,1\}^*\to\{0,1\}</math>表示某个'''判定问题'''。令<math>\mathcal{A}</math>为解决该判定问题的某个有单侧错误的'''蒙特卡罗随机算法'''（Monte Carlo randomized algorithm with one-sided error）。令<math>0<\epsilon<1</math>表示误差界。
对于任意输入<math>x\in\{0,1\}^*</math>，令<math>r\in[p]</math>为均匀分布的'''随机种子'''，<math>p</math>为某足够大的质数，假设算法<math>\mathcal{A}</math>总可以在有限时间内终止，且满足：
* <math>f(x)=1\implies \Pr(\mathcal{A}(x,r)=1)\ge 1-\epsilon</math>;
* <math>f(x)=0\implies \Pr(\mathcal{A}(x,r)=0)=1</math>，即对于所有随机种子<math>r\in[p]</math>总是有<math>\mathcal{A}(x,r)=0</math>.

在上述计算模型中，我们假设随机种子均匀分布在某个有限域<math>[p]</math>上，该有限域的大小<math>p</math>为质数，且可以与输入<math>x</math>的长度相关；同时，我们假设算法<math>\mathcal{A}</math>的随机性'''完全'''来自于随机种子<math>r\in[p]</math>，即：当判定问题的输入<math>x</math>和随机种子<math>r\in[p]</math>的取值都被确定之后，算法<math>\mathcal{A}(x,r)</math>的执行过程是确定的。

通过上述定义，算法<math>\mathcal{A}</math>有单侧的'''假阴性'''（'''false negative'''）概率误差，至多为<math>\epsilon</math>。如需减小这一误差，一个常规的办法是在同一个输入<math>x</math>上多次运行随机算法<math>\mathcal{A}</math>。

给定自然数<math>k</math>。对于问题输入<math>x\in\{0,1\}^*</math>，随机种子<math>r_0,r_1,\ldots,r_{k-1}\in[p]</math>，定义新算法：
:<math>\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=\bigvee_{i=0}^{k-1}\mathcal{A}(x,r_i)</math>。
即，新算法<math>\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})</math>输出0当且仅当对于所有<math>i=0,1,\ldots,k-1</math>，算法<math>\mathcal{A}(x,r_i)</math>都输出0；除此之外新算法<math>\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})</math>输出1。

对于如此构造的算法<math>\mathcal{A}^k</math>，容易验证：无论我们如何选取随机种子<math>r_0,r_1,\ldots,r_{k-1}\in[p]</math>，始终有：
* <math>f(x)=0\implies \mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=0</math>，因为此时<math>\mathcal{A}(x,r_i)=0</math>总是成立。
因此新算法<math>\mathcal{A}^k</math>仍旧没有假阳性错误。我们仅需分析其假阴性错误的概率即可，即此后我们始终假设输入<math>x</math>满足<math>f(x)=1</math>，分析算法<math>\mathcal{A}^k</math>输出0的概率上界。

给定自然数<math>k\le p</math>。考虑如下的两种方案来产生上述新算法<math>\mathcal{A}^k</math>中使用的随机种子<math>r_0,r_1,\ldots,r_{k-1}\in[p]</math>。

;方案I（独立重试）：
* 令<math>r_0,r_1,\ldots,r_{k-1}\in[p]</math>为相互独立均匀分布的随机数。

对于该方案，显然有：
:<math>f(x)=1\implies \Pr\left(\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=0\right)=\Pr\left(\bigcap_{i=0}^{k-1}(\mathcal{A}(x,r_i)=0)\right)\le \epsilon^k</math>
因此，'''方案I'''将单侧概率误差<math>\epsilon</math>降为<math>\epsilon^k</math>，代价是使用<math>k</math>倍的时间复杂度和<math>k</math>个相互独立的随机种子。

;方案II（两点采样）：
* 令<math>\boldsymbol{a},\boldsymbol{b}\in[p]</math>为相互独立均匀分布的随机数；
* 对于<math>i=0,1,\ldots,k-1</math>，令<math>r_i=(\boldsymbol{a}\cdot i+\boldsymbol{b})\bmod p</math>。

根据前述'''定理一'''可知：'''方案II'''中构造的<math>r_0,r_1,\ldots,r_{k-1}\in[p]</math>为<math>[p]</math>上均匀分布的两两独立的随机数，然而事实上仅使用了<math>\boldsymbol{a},\boldsymbol{b}\in[p]</math>这两个随机种子。

在输入<math>x</math>满足<math>f(x)=1</math>的假设下，对于每个<math>0\le i\le k-1</math>都有<math>\Pr(\mathcal{A}(x,r_i)=1)\ge 1-\epsilon</math>（因为<math>r_i\in[p]</math>均匀分布）。我们将分析概率<math> \Pr(\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=0)</math>的上界。

对于每个<math>0\le i\le k-1</math>，定义伯努利随机变量<math>X_i\in\{0,1\}</math>为<math>X_i=\mathcal{A}(x,r_i)</math>，并且定义<math>X=\sum_{i=0}^{k-1}X_i</math>。
因此有：
:<math>
\Pr\left(\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=0\right)=\Pr\left(\bigcap_{i=0}^{k-1}(\mathcal{A}(x,r_i)=0)\right)
=\Pr(X=0)</math>
而根据'''切比雪夫不等式'''：
<math>
\Pr(X=0)= \Pr(\mathbb{E}[X]-X=\mathbb{E}[X])\le \Pr(|X-\mathbb{E}[X]|\ge\mathbb{E}[X])\le\frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2}</math>.
接下来，我们将具体计算<math>{\mathbf{Var}[X]}/{\mathbb{E}[X]^2}</math>的上界。

根据定义，<math>X_0,X_1,\ldots,X_{k-1}</math>是两两独立的伯努利变量，而且：
:<math>
\mathbb{E}[X_i]
=\Pr(\mathcal{A}(x,r_i)=1)\ge 1-\epsilon
</math>.
于是根据期望的线性：
:<math>
\mathbb{E}[X]
=\sum_{i=0}^{k-1}\mathbb{E}[X_i]\ge (1-\epsilon)k
</math>.
注意到作为伯努利变量<math>X_0,X_1,\ldots,X_{k-1}\in\{0,1\}</math>，有<math>X_i^2=X_i</math>；同时由于两两独立性：
:<math>
\mathbf{Var}[X]
=
\sum_{i=0}^{k-1}\mathbf{Var}[X_i]
=
\sum_{i=0}^{k-1}(\mathbb{E}[X_i^2]-\mathbb{E}[X_i]^2)
\le 
\sum_{i=0}^{k-1}\mathbb{E}[X_i^2]
=
\sum_{i=0}^{k-1}\mathbb{E}[X_i]
=
\mathbb{E}[X]
</math>.
综上，
:<math>
\Pr\left(\mathcal{A}^k(x,r_0,r_1,\ldots,r_{k-1})=0\right)=\Pr(X=0)\le 
\frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2}\le \frac{1}{\mathbb{E}[X]}\le\frac{1}{(1-\epsilon)k}
</math>.
因此，'''方案II'''仍旧花费<math>k</math>倍的计算时间代价，将单侧概率误差<math>\epsilon</math>降至<math>\frac{1}{(1-\epsilon)k}</math>。同'''方案I'''达到的几何衰减的<math>\epsilon^k</math>误差相比，这似乎并不划算，但是别忘了，与'''方案I'''中使用了<math>k</math>个相互独立的随机种子不同，采用“两点采样”的'''方案II'''仅使用了两个随机种子，在随机性的开销上更有效率。