バイアスの小さいサンプル空間

させて${\displaystyle X}$確率分布​${\displaystyle \{0,1\}^{n}}$バイアス​​${\displaystyle X}$一連のインデックスに関して${\displaystyle I\subseteq \{1,\dots ,n\}}$^{[ 1 ]}と定義される

${\displaystyle {\text{bias}}_{I}(X)=\left|\Pr _{x\sim X}\left(\sum _{i\in I}x_{i}=0\right)-\Pr _{x\sim X}\left(\sum _{i\in I}x_{i}=1\right)\right|=\left|2\cdot \Pr _{x\sim X}\left(\sum _{i\in I}x_{i}=0\right)-1\right|\,,}$

合計が取られる$\displaystyle \mathbb {F} _{2}}$2 つの要素を持つ有限体。言い換えれば、和$\displaystyle \sum _{i\in I}x_{i}}$等しい${\displaystyle 0}$サンプル中の1の数が${\displaystyle x\in \{0,1\}^{n}}$定義された位置で${\displaystyle I}$偶数の場合は合計が等しくなり、それ以外の場合は合計が等しくなります。${\displaystyle 1}$。 のために${\displaystyle I=\emptyset }$空和はゼロと定義され、したがって$バイアス(X)=1$。

確率分布${\displaystyle X}$以上${\displaystyle \{0,1\}^{n}}$と呼ばれる${\displaystyle \epsilon }$-偏った標本空間の場合 $\displaystyle \text{bias}}_{I}(X)\leq \epsilon }$ 空でないすべての部分集合に対して成り立つ${\displaystyle I\subseteq \{1,2,\ldots ,n\}}$。

1${\displaystyle \epsilon }$偏りのあるサンプル空間${\displaystyle X}$これは、マルチセットから均一な要素を選択することによって生成されます。${\displaystyle X\subseteq \{0,1\}^{n}}$と呼ばれる${\displaystyle \epsilon }$偏りのある集合。サイズ${\displaystyle s}$の${\displaystyle \epsilon }$偏りのある集合${\displaystyle X}$これは、サンプル空間を生成するマルチセットのサイズです。

1${\displaystyle \epsilon }$バイアスジェネレーター${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$は長さの文字列をマッピングする関数です${\displaystyle \ell }$長さの弦へ${\displaystyle n}$多重集合${\displaystyle X_{G}=\{G(y)\;\vert \;y\in \{0,1\}^{\ell }\}}$は${\displaystyle \epsilon }$-偏りのあるセット。ジェネレーターのシード長は、${\displaystyle \ell }$そして、その大きさに関係している${\displaystyle \epsilon }$偏りのある集合${\displaystyle X_{G}}$方程式を通して$s=2^{\ell}}$。

確率的手法は、サイズを達成する非明示的な構成を提供する${\displaystyle s=O(n/\epsilon ^{2})}$[ ^{2 ]} この構成は^、${\displaystyle \epsilon }$-バイアスセットは多くの真のランダム性を必要とするが、これは全体的なランダム性を減らすという目標には役立たない。しかし、この非明示的な構成は、これらの効率的なコードが存在することを示すため有用である。一方、サイズの最もよく知られている下限は${\displaystyle \epsilon }$-偏った集合は${\displaystyle s=\Omega (n/(\epsilon ^{2}\log(1/\epsilon ))}$つまり、集合が${\displaystyle \epsilon }$偏りがあるとしても、少なくともそのくらいの大きさでなければならない。^{[ 2 ]}

明示的、つまり決定論的な構成が多数存在する${\displaystyle \epsilon }$-さまざまなパラメータ設定によるバイアスセット:

• Naor & Naor (1990)は${\displaystyle \displaystyle s={\frac {n}{{\text{poly}}(\epsilon )}}}$この構築では、ジャステセン符号（リード・ソロモン符号とウォゼンクラフト・アンサンブルの連結）とエキスパンダー・ウォーク・サンプリングが利用されます。
• アロンら（1992）は${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon \log(n/\epsilon )}}\right)^{2}}$彼らの構成の 1 つは、リード・ソロモン符号とアダマール符号の連結です。この連結は、${\displaystyle \epsilon }$-バランスの取れたコード、${\displaystyle \epsilon }$上記のつながりによって、偏りのある標本空間が生じる。
• 代数幾何符号とアダマール符号を連結すると、${\displaystyle \epsilon }$-バランスの取れたコード${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{3}\log(1/\epsilon )}}\right)}$[ ^{2 ]​}
• Ben-Aroya & Ta-Shma (2009)は達成しました${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{2}\log(1/\epsilon )}}\right)^{5/4}}$。
• タ・シュマ（2017）は${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{2+o(1)}}}\right)}$下限値があるため、これはほぼ最適と言える。

これらの境界は互いに比較できない。特に、これらの構成のいずれも最小値を与えない。${\displaystyle \epsilon }$-すべての設定に対して偏ったセット${\displaystyle \epsilon }$そして${\displaystyle n}$。

確率変数${\displaystyle Y}$以上${\displaystyle \{0,1\}^{n}}$すべてのインデックス集合に対して、k 個の独立空間である。${\displaystyle I\subseteq \{1,\dots ,n\}}$サイズの${\displaystyle k}$周辺分布${\displaystyle Y|_{I}}$は、一様分布と完全に等しい。${\displaystyle \{0,1\}^{k}}$つまり、そのようなすべての場合${\displaystyle I}$そしてすべての弦${\displaystyle z\in \{0,1\}^{k}}$分布${\displaystyle Y}$満たす${\displaystyle \Pr _{Y}(Y|_{I}=z)=2^{-k}}$。

確率変数${\displaystyle Y}$以上${\displaystyle \{0,1\}^{n}}$は${\displaystyle \delta }$すべてのインデックス集合に対して、ほぼ k 個の独立した空間${\displaystyle I\subseteq \{1,\dots ,n\}}$サイズの${\displaystyle k}$制限された分布${\displaystyle Y|_{I}}$および一様分布${\displaystyle U_{k}}$の上${\displaystyle \{0,1\}^{k}}$は${\displaystyle \delta }$-1ノルムで近い、つまり、${\displaystyle {\Big \|}Y|_{I}-U_{k}{\Big \|}_{1}\leq \delta }$。