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

利用线性同余方程构造两两独立的随机变量

令[math]\displaystyle{ p }[/math]为一质数。考虑模[math]\displaystyle{ p }[/math]余数构成的集合[math]\displaystyle{ [p]=\{0,1,\ldots,p-1\}=\mathbb{Z}_p }[/math]。众所周知，当[math]\displaystyle{ p }[/math]为质数时，[math]\displaystyle{ \mathbb{Z}_p }[/math]为对模[math]\displaystyle{ p }[/math]加法和乘法运算闭合的有限域。

我们现在构造一系列值域为[math]\displaystyle{ [p] }[/math]的两两独立（pairwise Independent）且均匀分布（uniformly distributed）的随机变量[math]\displaystyle{ X_{0},X_{1},\ldots,X_{p-1} }[/math]。构造如下：

• 令[math]\displaystyle{ \boldsymbol{a},\boldsymbol{b}\in[p] }[/math]为一对相互独立的取值在[math]\displaystyle{ [p] }[/math]上均匀分布的随机变量；
• 对于每个[math]\displaystyle{ i\in[p] }[/math]，定义 [math]\displaystyle{ X_i=(\boldsymbol{a}\cdot i+\boldsymbol{b})\bmod p }[/math]。

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

定理一

（均匀分布）对于任何[math]\displaystyle{ i\in[p] }[/math]，任意取值[math]\displaystyle{ c\in[p] }[/math]，有 [math]\displaystyle{ \Pr(X_i=c)=\frac{1}{p} }[/math] （两两独立性）对于任何不同的[math]\displaystyle{ i,j\in[p] }[/math]，以及任意取值[math]\displaystyle{ c,d\in[p] }[/math]，有 [math]\displaystyle{ \Pr(X_i=c\cap X_j=d)=\frac{1}{p^2} }[/math]

Proof. 首先验证每个[math]\displaystyle{ X_i }[/math]在其值域[math]\displaystyle{ [p] }[/math]上都是均匀分布的。根据全概率法则： [math]\displaystyle{ \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]\displaystyle{ i,a,c\in[p] }[/math]，仅有唯一的取值[math]\displaystyle{ b\in[p] }[/math]满足同余关系[math]\displaystyle{ b\equiv c-a\cdot i\pmod{p} }[/math]，因此 [math]\displaystyle{ \Pr\left(\boldsymbol{b}\equiv c-a\cdot i\pmod{p}\right)=\frac{1}{p} }[/math]. 其次验证没对不同的[math]\displaystyle{ X_i,X_j }[/math]之间的两两独立性。注意到，对任意不同[math]\displaystyle{ i,j\in[p] }[/math]和任意取值[math]\displaystyle{ c,d\in[p] }[/math]，如下以[math]\displaystyle{ \boldsymbol{a} }[/math]和[math]\displaystyle{ \boldsymbol{b} }[/math]为未知量的线性同余方程组： [math]\displaystyle{ \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]\displaystyle{ a,b\in[p] }[/math]。这是因为[math]\displaystyle{ \mathbb{Z}_p }[/math]为一合法的有限域。因此， [math]\displaystyle{ \Pr(X_i=c\cap X_j=d)=\Pr(\boldsymbol{a}=a\cap \boldsymbol{b}=b) =\frac{1}{p^2} }[/math] [math]\displaystyle{ \square }[/math]