Espacio de muestra con sesgo pequeño

Dejar${\displaystyle X}$sea ​​una distribución de probabilidad sobre${\displaystyle \{0,1\}^{n}}$. El sesgo de${\displaystyle X}$con respecto a un conjunto de índices${\displaystyle I\subseteq \{1,\dots ,n\}}$se define como ^{[ 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|\,,}$

donde la suma se toma sobre${\displaystyle \mathbb {F} _{2}}$, el campo finito con dos elementos. En otras palabras, la suma${\displaystyle \sum _{i\in I}x_{i}}$igual${\displaystyle 0}$si el número de unos en la muestra${\displaystyle x\in \{0,1\}^{n}}$en las posiciones definidas por${\displaystyle I}$es par, y en caso contrario, la suma es igual${\displaystyle 1}$. Para${\displaystyle I=\emptyset }$, la suma vacía se define como cero, y por lo tanto${\displaystyle {\text{sesgo}}_{\emptyset }(X)=1}$.

Una distribución de probabilidad${\displaystyle X}$encima${\displaystyle \{0,1\}^{n}}$se llama un${\displaystyle \epsilon }$-espacio muestral sesgado si ${\displaystyle {\text{sesgo}}_{I}(X)\leq \epsilon }$ Se cumple para todos los subconjuntos no vacíos.${\displaystyle I\subseteq \{1,2,\ldots ,n\}}$.

Un${\displaystyle \epsilon }$espacio muestral sesgado${\displaystyle X}$que se genera seleccionando un elemento uniforme de un multiconjunto${\displaystyle X\subseteq \{0,1\}^{n}}$se llama${\displaystyle \epsilon }$-conjunto sesgado . El tamaño${\displaystyle s}$de un${\displaystyle \epsilon }$-conjunto sesgado${\displaystyle X}$es el tamaño del multiconjunto que genera el espacio muestral.

Un${\displaystyle \epsilon }$generador con polarización${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$es una función que mapea cadenas de longitud${\displaystyle \ell }$a cadenas de longitud${\displaystyle n}$de tal manera que el multiconjunto${\displaystyle X_{G}=\{G(y)\;\vert \;y\in \{0,1\}^{\ell }\}}$es un${\displaystyle \epsilon }$Conjunto sesgado. La longitud de la semilla del generador es el número${\displaystyle \ell }$y está relacionado con el tamaño de la${\displaystyle \epsilon }$-conjunto sesgado${\displaystyle X_{G}}$mediante la ecuación${\displaystyle s=2^{\ell }}$.

El método probabilístico proporciona una construcción no explícita que alcanza el tamaño${\displaystyle s=O(n/\epsilon ^{2})}$. ^{[ 2 ]} La construcción no es explícita en el sentido de que encontrar el${\displaystyle \epsilon }$El conjunto sesgado requiere mucha aleatoriedad verdadera, lo que no ayuda al objetivo de reducir la aleatoriedad general. Sin embargo, esta construcción no explícita es útil porque muestra que existen estos códigos eficientes. Por otro lado, el límite inferior más conocido para el tamaño de${\displaystyle \epsilon }$-conjuntos sesgados es${\displaystyle s=\Omega (n/(\epsilon ^{2}\log(1/\epsilon ))}$, es decir, para que un conjunto sea${\displaystyle \epsilon }$-sesgado, debe ser al menos así de grande. ^{[ 2 ]}

Hay muchas construcciones explícitas, es decir, deterministas de${\displaystyle \epsilon }$-conjuntos sesgados con diversas configuraciones de parámetros:

• Naor y Naor (1990) logran${\displaystyle \displaystyle s={\frac {n}{{\text{poly}}(\epsilon )}}}$La construcción utiliza códigos de Justesen (que es una concatenación de códigos de Reed-Solomon con el conjunto de Wozencraft ) así como muestreo de recorrido de expansor .
• Alon et al. (1992) logran${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon \log(n/\epsilon )}}\right)^{2}}$. Una de sus construcciones es la concatenación de códigos Reed-Solomon con el código Hadamard ; esta concatenación resulta ser una${\displaystyle \epsilon }$-código equilibrado, que da lugar a un${\displaystyle \epsilon }$-espacio muestral sesgado a través de la conexión mencionada anteriormente.
• La concatenación de códigos geométricos algebraicos con el código de Hadamard da como resultado un${\displaystyle \epsilon }$-código equilibrado con${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{3}\log(1/\epsilon )}}\right)}$. ^{[ 2 ]}
• Ben-Aroya y Ta-Shma (2009) logran${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{2}\log(1/\epsilon )}}\right)^{5/4}}$.
• Ta-Shma (2017) logra${\displaystyle \displaystyle s=O\left({\frac {n}{\epsilon ^{2+o(1)}}}\right)}$lo cual es casi óptimo debido al límite inferior.

Estos límites son mutuamente incomparables. En particular, ninguna de estas construcciones produce el más pequeño.${\displaystyle \epsilon }$-conjuntos sesgados para todas las configuraciones de${\displaystyle \epsilon }$y${\displaystyle n}$.

Una variable aleatoria${\displaystyle Y}$encima${\displaystyle \{0,1\}^{n}}$es un espacio independiente k-ésimo si, para todos los conjuntos de índices${\displaystyle I\subseteq \{1,\dots ,n\}}$de tamaño${\displaystyle k}$la distribución marginal${\displaystyle Y|_{I}}$es exactamente igual a la distribución uniforme sobre${\displaystyle \{0,1\}^{k}}$. Es decir, para todos los tales${\displaystyle I}$y todas las cadenas${\displaystyle z\in \{0,1\}^{k}}$la distribución${\displaystyle Y}$Satisface${\displaystyle \Pr _{Y}(Y|_{I}=z)=2^{-k}}$.

Una variable aleatoria${\displaystyle Y}$encima${\displaystyle \{0,1\}^{n}}$es un${\displaystyle \delta }$-espacio casi k-ésimo independiente si, para todos los conjuntos de índices${\displaystyle I\subseteq \{1,\dots ,n\}}$de tamaño${\displaystyle k}$la distribución restringida${\displaystyle Y|_{I}}$y la distribución uniforme${\displaystyle U_{k}}$en${\displaystyle \{0,1\}^{k}}$son${\displaystyle \delta }$-cerrado en norma 1 , es decir,${\displaystyle {\Big \|}Y|_{I}-U_{k}{\Big \|}_{1}\leq \delta }$.