Ukázkový prostor s malým zkreslením - Small-bias sample space

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červen 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teoretická informatika, a malý zkreslený ukázkový prostor (také známý jako ${displaystyle epsilon}$objektivní ukázkový prostor, ${displaystyle epsilon}$-objektivní generátornebo pravděpodobnostní prostor s malou odchylkou) je rozdělení pravděpodobnosti to blázni paritní funkce Jinými slovy, žádná paritní funkce nedokáže rozlišit mezi malým vzorovým prostorem s rovnoměrným rozložením s vysokou pravděpodobností, a proto vzorové prostory s malým předpětím přirozeně vedou k pseudonáhodné generátory pro paritní funkce.

Hlavní užitečnou vlastností vzorových prostorů s malým zkreslením je to, že potřebují mnohem méně skutečně náhodných bitů než rovnoměrné rozdělení k oklamání parit. Efektivní konstrukce vzorových prostorů s malou odchylkou našly v počítačové vědě mnoho aplikací, z nichž některé jsou derandomizace, kódy opravující chyby, a pravděpodobnostně ověřitelné důkazy Spojení s kódy opravující chyby je ve skutečnosti velmi silný, protože ${displaystyle epsilon}$objektivní ukázkové prostory jsou ekvivalent na ${displaystyle epsilon}$-vyvážené kódy opravující chyby.

Definice

Zaujatost

Nechat ${displaystyle X}$ být rozdělení pravděpodobnosti přes ${displaystyle {0,1} ^ {n}}$.v zaujatost z ${displaystyle X}$ s ohledem na soubor indexů ${displaystyle Isubseteq {1, tečky, n}}$ je definován jako^[1]

${displaystyle {ext {bias}} _ {I} (X) = left | Pr _ {xsim X} left (sum _ {iin I} x_ {i} = 0ight) -Pr _ {xsim X} left (sum _ {iin I} x_ {i} = 1ight) ight | = left | 2cdot Pr _ {xsim X} left (sum _ {iin I} x_ {i} = 0ight) -1ight | ,,}$

kde je součet převzat ${displaystyle mathbb {F} _ {2}}$, konečné pole se dvěma prvky. Jinými slovy, součet ${displaystyle sum _ {iin I} x_ {i}}$ rovná se ${displaystyle 0}$ pokud je počet ve vzorku ${displaystyle xin {0,1} ^ {n}}$ na pozicích definovaných ${displaystyle I}$ je sudé a jinak se součet rovná ${displaystyle 1}$.Pro ${displaystyle I = emptyset}$, prázdný součet je definován jako nula, a tedy ${displaystyle {ext {bias}} _ {emptyset} (X) = 1}$.

sample-zaujatý prostor vzorku

Rozdělení pravděpodobnosti ${displaystyle X}$ přes ${displaystyle {0,1} ^ {n}}$ se nazývá ${displaystyle epsilon}$objektivní ukázkový prostor -li${displaystyle {ext {bias}} _ {I} (X) leq epsilon}$platí pro všechny neprázdné podmnožiny ${displaystyle Isubseteq {1,2, ldots, n}}$.

Sada s předpětím ϵ

An ${displaystyle epsilon}$objektivní ukázkový prostor ${displaystyle X}$ který je generován výběrem jednotného prvku z a multiset ${displaystyle Xsubseteq {0,1} ^ {n}}$ je nazýván ${displaystyle epsilon}$objektivní sada.v velikost ${displaystyle s}$ z ${displaystyle epsilon}$objektivní sada ${displaystyle X}$ je velikost multisetu, který generuje ukázkový prostor.

Generátor s předpětím ϵ

An ${displaystyle epsilon}$-objektivní generátor ${displaystyle G: {0,1} ^ {ell} o {0,1} ^ {n}}$ je funkce, která mapuje řetězce délky ${displaystyle ell}$ na řetězce délky ${displaystyle n}$ takové, že multiset ${displaystyle X_ {G} = {G (y); vert; yin {0,1} ^ {ell}}}$ je ${displaystyle epsilon}$objektivní sada. The délka semen generátoru je číslo ${displaystyle ell}$ a souvisí s velikostí souboru ${displaystyle epsilon}$objektivní sada ${displaystyle X_ {G}}$ pomocí rovnice ${displaystyle s = 2 ^ {ell}}$.

Spojení s epsilon vyváženými kódy pro opravu chyb

Existuje úzké spojení mezi nimi ${displaystyle epsilon}$-objektivní sady a ${displaystyle epsilon}$-vyrovnaný lineární kódy opravující chyby Lineární kód ${displaystyle C: {0,1} ^ {n} o {0,1} ^ {s}}$ z délka zprávy ${displaystyle n}$ a délka bloku ${displaystyle s}$ je${displaystyle epsilon}$-vyrovnaný pokud Hammingova hmotnost každého nenulového kódového slova ${displaystyle C (x)}$ je mezi ${displaystyle ({frac {1} {2}} - epsilon) s}$ a ${displaystyle ({frac {1} {2}} + epsilon) s}$.Od té doby ${displaystyle C}$ je lineární kód matice generátoru je ${displaystyle (n imes s)}$-matice ${displaystyle A}$ přes ${displaystyle mathbb {F} _ {2}}$ s ${displaystyle C (x) = xcdot A}$.

Pak to platí jako multiset ${displaystyle Xsubset {0,1} ^ {n}}$ je ${displaystyle epsilon}$-objektivní, právě když lineární kód ${displaystyle C_ {X}}$, jehož sloupce jsou přesně prvky ${displaystyle X}$, je ${displaystyle epsilon}$-vyrovnaný.^[2]

Konstrukce malých předpjatých sad epsilon

Cílem je obvykle najít ${displaystyle epsilon}$objektivní sady, které mají malou velikost ${displaystyle s}$ vzhledem k parametrům ${displaystyle n}$ a ${displaystyle epsilon}$Je to proto, že menší velikost ${displaystyle s}$ znamená, že množství náhodnosti potřebné k výběru náhodného prvku ze sady je menší, a proto lze sadu použít k oklamání parit pomocí několika náhodných bitů.

Teoretické hranice

Pravděpodobnostní metoda dává nevýslovnou konstrukci, která dosahuje velikosti ${displaystyle s = O (n / epsilon ^ {2})}$.^[2]Konstrukce není explicitní v tom smyslu, že hledání ${displaystyle epsilon}$-objektivní sada vyžaduje hodně skutečné náhodnosti, což nepomůže k cíli snížení celkové náhodnosti. Tato nevýslovná konstrukce je však užitečná, protože ukazuje, že tyto účinné kódy existují. Na druhou stranu nejznámější nižší vázáno na velikost ${displaystyle epsilon}$objektivní sady je ${displaystyle s = Omega (n / (epsilon ^ {2} log (1 / epsilon))}$, to znamená, aby byla sada ${displaystyle epsilon}$- objektivní, musí být alespoň tak velký.^[2]

Explicitní konstrukce

Existuje mnoho explicitních, tj. Deterministických konstrukcí ${displaystyle epsilon}$objektivní sady s různými nastaveními parametrů:

• Naor a Naor (1990) dosáhnout ${displaystyle displaystyle s = {frac {n} {{ext {poly}} (epsilon)}}}$. Konstrukce využívá Justesenovy kódy (což je zřetězení Reed-Solomon kódy s Soubor Wozencraft ) stejně jako vzorkování chůze expandérem.
• Alon a kol. (1992) dosáhnout ${displaystyle displaystyle s = Oleft ({frac {n} {epsilon log (n / epsilon)}} ight) ^ {2}}$. Jednou z jejich konstrukcí je zřetězení Reed-Solomon kódy s Hadamardův kód; toto zřetězení se ukázalo být ${displaystyle epsilon}$-vyvážený kód, který vede k ${displaystyle epsilon}$objektivní ukázkový prostor prostřednictvím výše uvedeného připojení.
• Zřetězení Algebraické geometrické kódy s Hadamardův kód dává ${displaystyle epsilon}$-vyvážený kód s ${displaystyle displaystyle s = Oleft ({frac {n} {epsilon ^ {3} log (1 / epsilon)}} v pořádku)}$.^[2]
• Ben-Aroya & Ta-Shma (2009) dosahuje ${displaystyle displaystyle s = Oleft ({frac {n} {epsilon ^ {2} log (1 / epsilon)}} v pořádku) ^ {5/4}}$.
• Ta-Shma (2017) chyba harvtxt: žádný cíl: CITEREFTa-Shma2017 (Pomoc) dosahuje ${displaystyle displaystyle s = Oleft ({frac {n} {epsilon ^ {2 + o (1)}}} vpravo)}$ což je téměř optimální z důvodu dolní meze.

Tyto hranice jsou vzájemně nesrovnatelné. Zejména žádná z těchto konstrukcí nepřináší nejmenší ${displaystyle epsilon}$-objektivní sady pro všechna nastavení ${displaystyle epsilon}$ a ${displaystyle n}$.

Aplikace: téměř nezávislost

Důležité použití sad s malým předpětím spočívá v konstrukci téměř k-nezávislých nezávislých prostorů vzorků.

k-moudrý nezávislý prostor

Náhodná proměnná ${displaystyle Y}$ přes ${displaystyle {0,1} ^ {n}}$ je k-moudrý nezávislý prostor pokud pro všechny sady indexů ${displaystyle Isubseteq {1, tečky, n}}$ velikosti ${displaystyle k}$, mezní rozdělení ${displaystyle Y | _ {I}}$ se přesně rovná rovnoměrné rozdělení přes ${displaystyle {0,1} ^ {k}}$To znamená, pro všechny takové ${displaystyle I}$ a všechny řetězce ${displaystyle zin {0,1} ^ {k}}$, distribuce ${displaystyle Y}$ splňuje ${displaystyle Pr _ {Y} (Y | _ {I} = z) = 2 ^ {- k}}$.

Stavby a hranice

nezávislé prostory k jsou docela dobře pochopeny.

• Jednoduchá konstrukce Joffe (1974) dosahuje velikosti ${displaystyle n ^ {k}}$.
• Alon, Babai a Itai (1986) postavte k-moudrý nezávislý prostor, jehož velikost je ${displaystyle n ^ {k / 2}}$.
• Chor a kol. (1985) dokázat, že žádný k-moudrý nezávislý prostor nemůže být výrazně menší než ${displaystyle n ^ {k / 2}}$.

Joffeova konstrukce

Joffe (1974) konstrukty a ${displaystyle k}$nezávislý prostor ${displaystyle Y}$ přes konečné pole s nějakým prvočíslem ${displaystyle n> k}$ prvků, tj. ${displaystyle Y}$ je distribuce přes ${displaystyle mathbb {F} _ {n} ^ {n}}$. Počáteční ${displaystyle k}$ okraje distribuce jsou kresleny nezávisle a rovnoměrně náhodně:

${displaystyle (Y_ {0}, tečky, Y_ {k-1}) sim mathbb {F} _ {n} ^ {k}}$.

Pro každého ${displaystyle i}$ s ${displaystyle kleq i$, mezní rozdělení ${displaystyle Y_ {i}}$ je pak definována jako

${displaystyle Y_ {i} = Y_ {0} + Y_ {1} cdot i + Y_ {2} cdot i ^ {2} + tečky + Y_ {k-1} cdot i ^ {k-1} ,,}$

kde se výpočet provádí v ${displaystyle mathbb {F} _ {n}}$.Joffe (1974) dokazuje, že distribuce ${displaystyle Y}$ takto konstruované je ${displaystyle k}$-wise nezávislé jako distribuce přes ${displaystyle mathbb {F} _ {n} ^ {n}}$.Distribuce ${displaystyle Y}$ je jednotná ve své podpoře, a tedy i podpoře ${displaystyle Y}$ tvoří a ${displaystyle k}$nezávislá množinaObsahuje vše ${displaystyle n ^ {k}}$ struny dovnitř ${displaystyle mathbb {F} _ {n} ^ {k}}$ které byly rozšířeny na řetězce délky ${displaystyle n}$ pomocí výše uvedeného deterministického pravidla.

Téměř k-nezávislé nezávislé prostory

Náhodná proměnná ${displaystyle Y}$ přes ${displaystyle {0,1} ^ {n}}$ je ${displaystyle delta}$- téměř nezávislý prostor pokud pro všechny sady indexů ${displaystyle Isubseteq {1, tečky, n}}$ velikosti ${displaystyle k}$, omezená distribuce ${displaystyle Y | _ {I}}$ a rovnoměrné rozdělení ${displaystyle U_ {k}}$ na ${displaystyle {0,1} ^ {k}}$ jsou ${displaystyle delta}$-zavřít v 1-norma, tj., ${displaystyle {Big |} Y | _ {I} -U_ {k} {Big |} _ {1} leq delta}$.

Stavby

Naor a Naor (1990) poskytnout obecný rámec pro kombinaci malých k-moudrých nezávislých prostorů s malými ${displaystyle epsilon}$-objektivní prostory k získání ${displaystyle delta}$- téměř k-nezávislé nezávislé prostory ještě menší velikosti ${displaystyle G_ {1}: {0,1} ^ {h} o {0,1} ^ {n}}$ být lineární mapování který generuje k-moudrý nezávislý prostor a let ${displaystyle G_ {2}: {0,1} ^ {ell} o {0,1} ^ {h}}$ být generátorem ${displaystyle epsilon}$- objektivní nastavení ${displaystyle {0,1} ^ {h}}$To znamená, že když je dán rovnoměrně náhodný vstup, výstup z ${displaystyle G_ {1}}$ je k-moudrý nezávislý prostor a výstup ${displaystyle G_ {2}}$ je ${displaystyle epsilon}$objektivně ${displaystyle G: {0,1} ^ {ell} o {0,1} ^ {n}}$ s ${displaystyle G (x) = G_ {1} (G_ {2} (x))}$ je generátor ${displaystyle delta}$-téměř ${displaystyle k}$nezávislý prostor, kde ${displaystyle delta = 2 ^ {k / 2} epsilon}$.^[3]

Jak je zmíněno výše, Alon, Babai a Itai (1986) postavit generátor ${displaystyle G_ {1}}$ s ${displaystyle h = {frac {k} {2}} přihlásit se}$, a Naor a Naor (1990) postavit generátor ${displaystyle G_ {2}}$ s ${displaystyle ell = log s = log h + O (log (epsilon ^ {- 1}))}}$Proto tedy zřetězení ${displaystyle G}$ z ${displaystyle G_ {1}}$ a ${displaystyle G_ {2}}$ má délku semen ${displaystyle ell = log k + log log n + O (log (epsilon ^ {- 1}))}}$.K tomu, aby ${displaystyle G}$ výtěžek a ${displaystyle delta}$- téměř nezávislý prostor, musíme nastavit ${displaystyle epsilon = delta 2 ^ {- k / 2}}$, což vede k délce semen ${displaystyle ell = log log n + O (k + log (delta ^ {- 1}))}$ a ukázkový prostor o celkové velikosti ${displaystyle 2 ^ {ell} leq log ncdot {ext {poly}} (2 ^ {k} cdot delta ^ {- 1})}$.

Poznámky

Reference

• Alon, Noga; Babai, László; Itai, Alon (1986), "Rychlý a jednoduchý randomizovaný paralelní algoritmus pro maximální problém nezávislé množiny" (PDF), Journal of Algorithms, 7 (4): 567–583, doi:10.1016/0196-6774(86)90019-2CS1 maint: ref = harv (odkaz)
• Alon, Noga; Goldreich, Oded; Håstad, Johan; Peralta, René (1992), "Jednoduché konstrukce téměř k-moudrých nezávislých náhodných proměnných" (PDF), Náhodné struktury a algoritmy, 3 (3): 289–304, CiteSeerX  10.1.1.106.6442, doi:10.1002 / rsa.3240030308CS1 maint: ref = harv (odkaz)
• Ben-Aroya, Avraham; Ta-Shma, Amnon (2009), „Konstrukce sad malých odchylek z algebraicko-geometrických kódů“ (PDF), Sborník z 50. výročního symposia o základech informatiky, FOCS 2009: 191–197, CiteSeerX  10.1.1.149.9273, doi:10.1109 / FOCS.2009.44, ISBN  978-1-4244-5116-6CS1 maint: ref = harv (odkaz)
• Chor, Benny; Goldreich, Oded; Håstad, Johan; Freidmann, Joel; Rudich, Steven; Smolensky, Roman (1985), „Problém s extrakcí bitů nebo t-odolné funkce“, Proceedings of the 26.th Symposium on Foundations of Computer Science, FOCS 1985: 396–407, CiteSeerX  10.1.1.39.6768, doi:10.1109 / SFCS.1985.55, ISBN  978-0-8186-0644-1CS1 maint: ref = harv (odkaz)
• Goldreich, Oded (2001), Přednáška 7: Malé zkreslení ukázkových prostorůCS1 maint: ref = harv (odkaz)
• Joffe, Anatole (1974), „Na množině téměř deterministických náhodných proměnných nezávislých na k“ Annals of Probability, 2 (1): 161–162, doi:10.1214 / aop / 1176996762CS1 maint: ref = harv (odkaz)
• Naor, Joseph; Naor, Moni (1990), „Pravděpodobnostní prostory s malou odchylkou: efektivní konstrukce a aplikace“, Proceedings of the 22. Annual ACM Symposium on Theory of Computing, STOC 1990: 213–223, CiteSeerX  10.1.1.421.2784, doi:10.1145/100216.100244, ISBN  978-0897913614CS1 maint: ref = harv (odkaz)
• Amnon, Ta-Shma (2017), „Explicit, Almost Optimal, Epsilon-balanced Codes“, Sborník z 49. výročního sympozia ACM SIGACT o teorii práce s počítačem: 238–251, doi:10.1145/3055399.3055408, ISBN  9781450345286CS1 maint: ref = harv (odkaz)