Sloučení náhodnosti - Randomness merger

v extraktor teorie, a náhodné sloučení je funkce, která extrahuje náhodnost ze sady náhodných proměnných za předpokladu, že alespoň jedna z nich je rovnoměrně náhodná. Jeho název vychází ze skutečnosti, že jej lze považovat za postup, který „spojuje“ všechny proměnné do jedné a zachovává alespoň část entropie obsažené v rovnoměrně náhodné proměnné. Fúze se aktuálně používají, aby se explicitně vytvořily extraktory náhodnosti.

Intuice a definice

Zvažte sadu ${ displaystyle k}$ náhodné proměnné, ${ displaystyle X_ {1}, ldots, X_ {k}}$, každý distribuován přes ${ displaystyle {0,1 } ^ {n}}$ alespoň jeden z nich je rovnoměrně náhodný; ale není známo, který z nich. Kromě toho mohou proměnné libovolně korelovat: mohou to být vzájemné funkce, mohou být konstantní atd. Jelikož je však alespoň jeden z nich jednotný, obsahuje jej jako celek minimálně ${ displaystyle n}$ kousky entropie.

Úkolem fúze je vydat novou náhodnou proměnnou, také distribuovanou přes ${ displaystyle {0,1 } ^ {n}}$, která si zachovává co nejvíce z této entropie, jak je to možné. V ideálním případě, pokud by bylo známo, která z proměnných je jednotná, mohla by být použita jako výstup, ale tato informace není známa. Myšlenkou fúzí je, že použitím malého dalšího náhodného semene je možné dosáhnout dobrého výsledku i bez znalosti toho, která z nich je jednotná proměnná.

Definice (fúze):

Funkce ${ displaystyle M: ​​( {0,1 } ^ {n}) ^ {k} krát {0,1 } ^ {d} pravá šipka {0,1 } ^ {n}}$ se nazývá ${ displaystyle (m, varepsilon)}$-merger if pro každou sadu náhodných proměnných ${ displaystyle (X_ {1}, ldots, X_ {k})}$ distribuováno přes ${ displaystyle {0,1 } ^ {n}}$, z nichž alespoň jedna je uniformní, distribuce ${ displaystyle Z = M (X_ {1}, ldots, X_ {k}, U_ {d})}$ má hladkou minimální entropii ${ displaystyle H _ { infty} ^ { varepsilon} (Z) geq m}$. Proměnná ${ displaystyle U_ {d}}$ označuje rovnoměrné rozdělení přes ${ displaystyle d}$ bitů a představuje skutečně náhodné semeno.

Jinými slovy, pomocí malého jednotného semene délky ${ displaystyle d}$, fúze vrátí řetězec, který je ${ displaystyle varepsilon}$- blízko k mít alespoň ${ displaystyle m}$ min. entropie; to znamená, že jeho statistická vzdálenost z řetězce s ${ displaystyle m}$ min-entropie není větší než ${ displaystyle varepsilon}$.

Připomínka: Existuje několik pojmů měření náhodnosti distribuce; min-entropie náhodné proměnné ${ displaystyle Z}$ je definována jako největší ${ displaystyle k}$ taková, že nejpravděpodobnější hodnota ${ displaystyle Z}$ nastane s pravděpodobností ne více než ${ displaystyle 2 ^ {- k}}$. Min-entropie řetězce je horní hranice množství náhodnosti, které z ní lze získat. ^[1]

Parametry

Při vytváření fúzí je třeba optimalizovat tři parametry:

1. Min-entropie výstupu ${ displaystyle m}$ by měla být tak vysoká, jak je to možné, protože z ní lze extrahovat více bitů.
2. ${ displaystyle varepsilon}$ by měl být co nejmenší, protože poté po použití extraktoru na výstup fúze bude výsledek blíže uniformnímu.
3. Délka osiva ${ displaystyle d}$ by měl být co nejmenší, protože potom sloučení vyžaduje méně počátečních skutečně náhodných bitů, aby fungovalo.

Explicitní konstrukce pro fúze jsou známy s relativně dobrými parametry. Například Dvir a Wigdersonova konstrukce dává:^[2]Pro každého ${ displaystyle alpha> 0}$ a celé číslo ${ displaystyle n}$, pokud ${ displaystyle k leq 2 ^ {o (n)}}$, existuje explicitní ${ displaystyle (m, varepsilon)}$-fúze ${ displaystyle M: ​​( {0,1 } ^ {n}) ^ {k} krát {0,1 } ^ {d} pravá šipka {0,1 } ^ {n}}$ takové, že:

1. ${ displaystyle m = (1- alfa) n,}$
2. ${ displaystyle d = O ( log (n) + log (k)),}$
3. ${ displaystyle varepsilon = O left ({ frac {1} {n cdot k}} right).}$

Důkaz je konstruktivní a umožňuje sestavení takové fúze v polynomiálním čase v daných parametrech.

Používání

Je možné použít fúze za účelem výroby náhodných extraktorů s dobrými parametry. Připomeňme, že extraktor je funkce, která bere náhodnou proměnnou, která má vysokou min-entropii, a vrací menší náhodnou proměnnou, která je však blízká uniformě. Libovolný extraktor min-entropie lze získat pomocí následujícího schématu spojování:^[2][3]

• Vzhledem k tomu, že je zdrojem vysoké minentropie, rozdělte jej na bloky. Podle známého výsledku^[4] alespoň jeden z těchto oddílů bude mít také vysokou min-entropii jako zdroj bloku.
• Použijte a blokový extraktor samostatně na všechny bloky. Jedná se o slabší druh extraktoru a jsou známy dobré konstrukce.^[2] Protože alespoň jeden z bloků má vysokou min-entropii, alespoň jeden z výstupů je velmi blízký uniformám.
• Pomocí fúze zkombinujte všechny předchozí výstupy do jednoho řetězce. Pokud se použije dobrá fúze, výsledný řetězec bude mít ve srovnání s jeho délkou velmi vysokou min-entropii.
• K extrakci náhodnosti použijte známý extraktor, který funguje pouze pro velmi vysoké zdroje min-entropie.

Podstatou výše uvedeného schématu je použití fúze k transformaci řetězce s libovolnou min-entropií na menší řetězec, aniž by při tom přišlo o mnoho min-entropie. Tento nový řetězec má ve srovnání s jeho délkou velmi vysokou minimální entropii a poté je možné použít starší známé extraktory, které fungují pouze pro tyto typy řetězců.

Viz také

• Extaktor náhodnosti

Reference