Små-bias provutrymme

Inom teoretisk datavetenskap är ett sampelutrymme med liten bias (även känd som $\epsilon$ -biased sample space , $\epsilon$ -biased generator eller small-bias probability space ) en sannolikhetsfördelning som narrar paritetsfunktioner . Med andra ord kan ingen paritetsfunktion skilja mellan ett sampelutrymme med liten bias och den enhetliga fördelningen med hög sannolikhet, och följaktligen ger små bias sampelutrymmen naturligtvis upphov till pseudoslumpgeneratorer för paritetsfunktioner.

Den viktigaste användbara egenskapen hos sampelutrymmen med liten bias är att de behöver mycket färre verkligt slumpmässiga bitar än den enhetliga fördelningen för att lura pariteter. Effektiva konstruktioner av provutrymmen med liten bias har hittat många tillämpningar inom datavetenskap, av vilka några är derandomisering , felkorrigerande koder och sannolikhetskontrollerbara bevis . Sambandet med felkorrigerande koder är i själva verket mycket starkt eftersom $\epsilon$ -biased sample spaces motsvarar $\epsilon$ -balanserade felkorrigerande koder .

Definition

Partiskhet

Låt $X$ vara en sannolikhetsfördelning över $\{0,1\}^{n}$ . Biasen för ${\displaystyle X} med$$I\subseteq \{1,\dots ,n\}$ på en uppsättning index } definieras som

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

där summan tas över $\mathbb {F} _{2}$ , det finita fältet med två element. Med andra ord, summan $\sum _{i\in I}x_{i}$ är lika med $0$ om antalet ettor i provet $x\in \{0,1\}^{n}$ vid positionerna definierade av $I$ är jämn, och annars är summan $1$ . För $I=\emptyset$ definieras den tomma summan till noll, och därför ${\text{bias}}_{\emptyset }(X)= 1$ .

ϵ-förspänt sampelutrymme

En sannolikhetsfördelning $X$ över $\{0,1\}^{n}$ kallas ett $\epsilon$ -biased sample space if ${\text{bias}}_{I}(X)\leq \epsilon$ gäller för alla icke-tomma delmängder $I\subseteq \{ 1,2,\ldots ,n\}$ .

ϵ-förspänd uppsättning

Ett $\epsilon$ -biased sample space $X$ som genereras genom att välja ett enhetligt element från en multiset $X\subseteq \{0,1\$ kallas $\epsilon$ -biased set . Storleken s $s$ för en $\epsilon$ -förspänd uppsättning $\displaystyle X}$ är storleken på den multiset som genererar sampelutrymmet.

ϵ-förspänd generator

En $\epsilon$ -biased generator $G:\{0,1\}^{\ell }\to \{0,1\} ^{n}$ är en funktion som mappar strängar med längden $\ell$ till strängar med längden $n$ så att multiuppsättningen ${\displaystyle X_{G}=\{G(y)\;\vert \;y\in \{0,1\}^{\ell }\}} är$ en ${ \displaystyle \epsilon }$ -biased set. Generatorns frölängd är talet ℓ $\displaystyle \ell }$ och är relaterad till storleken på $\epsilon$ -förspänd mängd $X_{G}$ via ekvationen $s=2^{\ell }$ .

Anslutning med epsilon-balanserade felkorrigeringskoder

Det finns ett nära samband mellan $\epsilon$ -biased sets och $\epsilon$ -balanserade linjära felkorrigerande koder . En linjär kod $C:\{0,1\}^{n}\to \{0,1\}^{s}$ av meddelandelängd $n$ och blocklängd $s$ är $\epsilon$ -balanserad om Hamming-vikten för varje kodord som inte är noll $C(x)$ är mellan $({\frac {1}{2}}-\epsilon )s$ och $({\frac {1}{2}}+\epsilon )s$ . Eftersom $C$ är en linjär kod är dess generatormatris en $(n\times s)$ -matris $A$ över $\mathbb {F } _{2}$ med $C(x)=x\cdot A$ .

Då gäller att en multimängd $X\subset \{0,1\}^{n}$ är $\epsilon$ -förspänd om och endast om den linjära koden $C_{X}$ , vars kolumner är exakt element av $X$ , är $\epsilon$ -balanserad.

Konstruktioner av små epsilon-biased set

Vanligtvis är målet att hitta $\epsilon$ -biased set som har en liten storlek $s$ i förhållande till parametrarna $n$ och $\epsilon$ . Detta beror på att en mindre storlek $s$ betyder att mängden slumpmässighet som behövs för att välja ett slumpmässigt element från mängden är mindre, och så kan mängden användas för att lura pariteter med några slumpmässiga bitar.

Teoretiska gränser

Den probabilistiska metoden ger en icke-explicit konstruktion som uppnår storlek $s=O(n/\epsilon ^{2})$ . Konstruktionen är icke-explicit i den meningen att hitta den $\epsilon$ -biased uppsättningen kräver mycket sann slumpmässighet, vilket inte hjälper mot målet att minska den övergripande slumpen. Denna icke-explicita konstruktion är dock användbar eftersom den visar att dessa effektiva koder existerar. Å andra sidan är den mest kända nedre gränsen för storleken på $\epsilon$ -biased set ${\displaystyle s=\Omega ( n/(\epsilon ^{2}\log(1/\epsilon ))} ,$ det vill säga, för att en uppsättning ska vara $\epsilon$ -biased, måste den vara minst så stor.

Explicita konstruktioner

Det finns många explicita, dvs deterministiska konstruktioner av $\epsilon$ -förspända uppsättningar med olika parameterinställningar:

• Naor & Naor (1990) uppnår $\displaystyle s={\frac {n}{{\text{poly}}(\epsilon )}}$ . Konstruktionen använder sig av Justesen-koder (som är en sammanlänkning av Reed–Solomon-koder med Wozencraft-ensemblen ) såväl som expanderpromenadsampling .
• Alon et al. (1992) uppnå $\displaystyle s=O\left({\frac {n}{\epsilon \log(n/\epsilon )}}\ höger)^{2}$ . En av deras konstruktioner är sammanlänkningen av Reed–Solomon-koder med Hadamard-koden ; denna sammanlänkning visar sig vara en $\epsilon$ -balanserad kod, vilket ger upphov till ett $\epsilon$ -förspänt sampelutrymme via ovan nämnda koppling.
• Att sammanfoga algebraiska geometriska koder med Hadamard-koden ger en $\epsilon$ -balanserad kod med $\displaystyle s=O\left({\frac {n}{\epsilon ^{3}\log(1/\epsilon )}}\right)$ .
• Ben-Aroya & Ta-Shma (2009) uppnår $\displaystyle s=O\left({\frac {n}{\epsilon ^ {2}\log(1/\epsilon )}}\right)^{5/4}$ .
• Ta-Shma (2017) uppnår $\displaystyle s=O\left({\frac {n}{ \epsilon ^{2+o(1)}}}\right)$ vilket är nästan optimalt på grund av den nedre gränsen.

Dessa gränser är ömsesidigt ojämförliga. I synnerhet ger ingen av dessa konstruktioner de minsta $\epsilon$ -förspända uppsättningarna för alla inställningar av $\epsilon$ och $n$ .

Användning: nästan k-mässigt oberoende

En viktig tillämpning av små-bias-uppsättningar ligger i konstruktionen av nästan k-mässigt oberoende sampelutrymmen.

k-mässigt oberoende utrymmen

En slumpvariabel $Y$ över $\{0,1\}^{n}$ är ett k-mässigt oberoende mellanslag om, för alla indexuppsättningar $I\subseteq \{1,\dots ,n\}$ av storleken $k$ , marginalfördelningen $Y|_{I}$ är exakt lika med den enhetliga fördelningen över $\{0,1\}^{k}$ . Det vill säga, för alla sådana $I$ och alla strängar $z\in \{0,1\}^{k}$ uppfyller fördelningen $Y$$\Pr _{Y}(Y|_{I}=z)=2^{-k}$ .

Konstruktioner och gränser

k-mässigt oberoende utrymmen är ganska väl förstådda.

• En enkel konstruktion av Joffe (1974) uppnår storlek $n^{k}$ .
• Alon, Babai & Itai (1986) konstruerar ett k-mässigt oberoende utrymme vars storlek är $n^{k/2}$ .
• Chor et al. (1985) bevisar att inget k-mässigt oberoende utrymme kan vara betydligt mindre än $n^{k/2}$ .

Joffes konstruktion

Joffe (1974) konstruerar ett $k$ -vis oberoende utrymme $Y$ över det finita fältet med något primtal $n>k$ av element, dvs $Y$ är en fördelning över $\mathbb {F} _{n}^{n}$ . De initiala $k$ -marginalerna för fördelningen ritas oberoende och enhetligt slumpmässigt:

$(Y_{0},\dots ,Y_{k-1})\sim \mathbb {F} _{n}^{k}$ .

För varje $i$ med ${\displaystyle k\leq i<n} ,$ definieras då marginalfördelningen av ${\displaystyle Y_{i}} som$

$Y_{i}=Y_{0}+Y_{1}\cdot i+Y_ {2}\cdot i^{2}+\dots +Y_{k-1}\cdot i^{k-1}\,,$

där beräkningen görs i $\mathbb {F} _{n}$ . Joffe (1974) bevisar att fördelningen $Y$ konstruerad på detta sätt är $k$ -vis oberoende som en fördelning över $\mathbb {F} _{n}^{n }$ . Fördelningen ${\displaystyle Y} är enhetlig på sitt stöd, och följaktligen$ bildar stödet för ${\displaystyle Y} en$$k$ -vis oberoende uppsättning . Den innehåller alla $n^{k}$ strängar i $\mathbb {F} _{n}^{k}$ som har utökats till strängar med längden $n$ med den deterministiska regeln ovan.

Nästan k-mässigt oberoende utrymmen

En slumpvariabel $Y$ över $\{0,1\}^{n}$ är ett $\delta$ -nästan k-mässigt oberoende mellanslag om, för alla indexuppsättningar $I\subseteq \{1,\dots ,n\}$ av storleken $k$ , den begränsade fördelningen $Y|_{I}$ och den enhetliga fördelningen $U_{k}$ på $\{0,1\}^{k}$ är ${\ displaystyle \delta }$ -close i 1-norm , dvs ${\Big \|}Y|_{I}-U_{k}{\Big \|}_{1}\leq \delta$ .

Konstruktioner

Naor & Naor (1990) ger ett allmänt ramverk för att kombinera små k-vis oberoende utrymmen med små $\epsilon$ -biased spaces för att erhålla $\delta$ -nästan k-vis oberoende utrymmen av ännu mindre storlek . Låt särskilt $G_{1}:\{0,1\}^{h}\to \{0,1\}^{n}$ vara en linjär mappning som genererar ett k-vis oberoende utrymme och låt $G_{2}:\{0,1\}^{\ell }\ att \{0,1\}^{h}$ vara en generator av en $\epsilon$ -förspänd uppsättning över $\{0,1\}^{h}$ . Det vill säga, när den ges en likformigt slumpmässig ingång, är utsignalen från $G_{1}$ ett k-vis oberoende mellanslag, och utsignalen från $G_{2}$ är $\epsilon$ -partisk. Sedan $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ med $G(x)=G_{1}(G_{2}(x))$ är en generator av en $\delta$ -nästan $k$ -vis oberoende utrymme, där $\delta =2^{k/2}\epsilon$ .

Som nämnts ovan konstruerar Alon, Babai & Itai (1986) en generator $G_{1}$ med $h={\tfrac {k}{2}}\log n$ och Naor & Naor (1990) konstruerar en generator $G_{2}$ med $\ell = \log s=\log h+O(\log(\epsilon ^{-1}))$ . Följaktligen har sammanlänkningen $G$ av $G_{1}$ och $G_{2}$ frölängd $\ell =\log k+\log \log n+O(\log(\epsilon ^{-1}))$ . För att $G$ ska ge ett $\delta$ -nästan k-mässigt oberoende utrymme måste vi sätta $\epsilon =\delta 2^{ -k/2}$ , vilket leder till en frölängd på $\ell =\log \log n+O(k+\ log(\delta ^{-1}))$ och ett sampelutrymme med total storlek $2^{\ell }\leq \log n\ cdot {\text{poly}}(2^{k}\cdot \delta ^{-1})$ .

Anteckningar

• Alon, Noga; Babai, László; Itai, Alon (1986), "En snabb och enkel randomiserad parallell algoritm för det maximala oberoende uppsättningsproblemet" ( PDF) , Journal of Algorithms , 7 (4): 567–583, doi : 10.1016/0196-6774(86)90019 -2
•   Alon, Noga; Goldreich, Oded; Håstad, Johan; Peralta, René (1992), "Simple Constructions of Almost k-wise Independent Random Variables" (PDF) , Random Structures & Algorithms , 3 (3): 289–304, CiteSeerX 10.1.1.106.6442 , doi : 2/rsa.10. 3240030308
•    Ben-Aroya, Avraham; Ta-Shma, Amnon (2009), "Constructing Small-Bias Sets from Algebraic-Geometric Codes" (PDF) , Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 : 191–197, CiteSeerX 10.1.97 . , doi : 10.1109/FOCS.2009.44 , ISBN 978-1-4244-5116-6
•     Chor, Benny; Goldreich, Oded; Håstad, Johan; Freidmann, Joel; Rudich, Steven; Smolensky, Roman (1985), "The bit extraction problem or t-resilient functions", Proceedings of the 26th Annual Symposium on Foundations of Computer Science, FOCS 1985 : 396–407, CiteSeerX 10.1.1.39.6768 , doi : 9010 .1985.55 , ISBN 978-0-8186-0644-1 , S2CID 6968065
• Goldreich, Oded (2001), Föreläsning 7: Small bias sample spaces
• Joffe, Anatole (1974), "On a Set of Almost Deterministic k-Independent Random Variables", Annals of Probability , 2 (1): 161–162, doi : 10.1214/aop/1176996762
•     Naor, Joseph; Naor, Moni (1990), " Small-bias Probability Spaces: efficient constructions and Applications" , Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC 1990 : 213–223, CiteSeerX 10.1.1.421,017 ,017 ,017 , 017 . 100216.100244 , ISBN 978-0897913614 , S2CID 14031194
•    " Explicit, Almost Optimal, Epsilon-balanced Codes", Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing : 238–251, doi : 10.1145/3055340.375 5253409.375,455340.375 , 525 340.375 S2CID 5648543