Кездейсоқтықтың бірігуі - Randomness merger

Жылы экстрактор теория, а кездейсоқтықтың бірігуі кездейсоқ шамалардың жиынтығынан кездейсоқтықты шығаратын функция, егер олардың кем дегенде біреуі біркелкі кездейсоқ болса. Оның атауы оны біртекті кездейсоқ шаманың құрамындағы энтропияның ең болмағанда бір бөлігін сақтай отырып, барлық айнымалыларды «біріктіретін» процедура ретінде қарастыруға болатындығынан туындайды. Біріктіру қазіргі кезде кездейсоқтық экстракторларын нақты құру үшін қолданылады.

Түйсік және анықтама

Жиынтығын қарастырайық ${ displaystyle k}$ кездейсоқ шамалар, ${ displaystyle X_ {1}, ldots, X_ {k}}$ , әрқайсысы таратылды ${ displaystyle {0,1 } ^ {n}}$ олардың кем дегенде біреуі біркелкі кездейсоқ; бірақ қайсысы екені белгісіз. Сонымен қатар, айнымалылар ерікті түрде өзара байланысты болуы мүмкін: олар бір-бірінің функциялары болуы мүмкін, олар тұрақты және т.б. Алайда, олардың ең болмағанда біреуі біркелкі болғандықтан, жиынтықта кем дегенде болады ${ displaystyle n}$ энтропия биттері.

Біріктірудің міндеті - жаңа кездейсоқ шаманы шығару, сонымен бірге бөлінеді ${ displaystyle {0,1 } ^ {n}}$ , бұл энтропияның мүмкіндігінше көбірек сақтайды. Ең дұрысы, егер айнымалылардың қайсысының біркелкі екендігі белгілі болса, оны нәтиже ретінде пайдалануға болады, бірақ бұл ақпарат белгісіз. Біріктіру идеясы - шағын қосымша кездейсоқ тұқымды қолдану арқылы қайсысының бірыңғай айнымалы екенін білмей-ақ жақсы нәтижеге қол жеткізуге болады.

Анықтама (бірігу):

Функция ${ displaystyle M: ( {0,1 } ^ {n}) ^ {k} times {0,1 } ^ {d} rightarrow {0,1 } ^ {n}}$ деп аталады ${ displaystyle (m, varepsilon)}$ - кездейсоқ шамалардың әрбір жиынтығына арналған ${ displaystyle (X_ {1}, ldots, X_ {k})}$ таратылды ${ displaystyle {0,1 } ^ {n}}$ , олардың кем дегенде біреуі біркелкі, таралуы ${ displaystyle Z = M (X_ {1}, ldots, X_ {k}, U_ {d})}$ тегіс мин-энтропияға ие ${ displaystyle H _ { infty} ^ { varepsilon} (Z) geq m}$ . Айнымалы ${ displaystyle U_ {d}}$ біркелкі үлестіруді білдіреді ${ displaystyle d}$ биттер және шынымен кездейсоқ тұқымды білдіреді.

Басқаша айтқанда, ұзындықтың кішкентай біркелкі тұқымын қолдану арқылы ${ displaystyle d}$ , бірігу жолды қайтарады ${ displaystyle varepsilon}$ - ең болмағанда жақын болыңыз ${ displaystyle m}$ мин-энтропия; бұл оның статистикалық қашықтық жіптен ${ displaystyle m}$ мин-энтропия үлкен емес ${ displaystyle varepsilon}$ .

Еске салу: Таралудың кездейсоқтығын өлшейтін бірнеше түсініктер бар; кездейсоқ шаманың мин-энтропиясы ${ displaystyle Z}$ ең үлкені ретінде анықталады ${ displaystyle k}$ сияқты ең ықтимал мәні ${ displaystyle Z}$ -дан аспайтын ықтималдықпен жүреді ${ displaystyle 2 ^ {- k}}$ . Жолдың мин-энтропиясы - одан алынатын кездейсоқтық мөлшерінің жоғарғы шегі. ^[1]

Параметрлер

Біріктіру кезінде оңтайландырудың үш параметрі бар:

Шығу мин-энтропиясы ${ displaystyle m}$ мүмкіндігінше жоғары болуы керек, өйткені одан одан көп бит алуға болады.
${ displaystyle varepsilon}$ мүмкіндігінше аз болуы керек, өйткені экстракторды біріктіру нәтижесіне қолданғаннан кейін нәтиже біркелкі болады.
Тұқым ұзындығы ${ displaystyle d}$ мүмкіндігінше аз болуы керек, сондықтан біріктіру жұмыс жасау үшін бастапқы шынымен кездейсоқ биттерді азырақ қажет етеді.

Біріктіруге арналған айқын конструкциялар салыстырмалы түрде жақсы параметрлермен белгілі. Мысалы, Dvir және Уигдерсондікі құрылыс береді:^[2]Әрқайсысы үшін ${ displaystyle alpha> 0}$ және бүтін ${ displaystyle n}$ , егер ${ displaystyle k leq 2 ^ {o (n)}}$ , нақты бар ${ displaystyle (m, varepsilon)}$ -мергер ${ displaystyle M: ( {0,1 } ^ {n}) ^ {k} times {0,1 } ^ {d} rightarrow {0,1 } ^ {n}}$ осылай:

${ displaystyle m = (1- альфа) n,}$
${ displaystyle d = O ( log (n) + log (k)),}$
${ displaystyle varepsilon = O сол ({ frac {1} {n cdot k}} оң).}$

Дәлелдеме конструктивті және берілген параметрлер бойынша полиномдық уақытта осындай бірігуді құруға мүмкіндік береді.

Пайдалану

Жақсы параметрлері бар кездейсоқ экстракторларды шығару үшін біріктіруді қолдануға болады. Естеріңізге сала кетейік экстрактор - бұл мин-энтропиясы жоғары кездейсоқ шаманы қабылдайтын және кішігірім кездейсоқ шаманы қайтаратын, бірақ біркелкіге жақын функция. Ерікті мин-энтропия экстракторын келесі бірігу негізіндегі схема арқылы алуға болады:^[2]^[3]

Мин-энтропияның жоғары көзін ескере отырып, оны блоктарға бөліңіз. Белгілі нәтиже бойынша,^[4] бұл бөлімдердің кем дегенде біреуінде блок-көзі ретінде мин-энтропия жоғары болады.
Қолдану а блок сорғыш барлық блоктарға бөлек. Бұл экстрактордың әлсіз түрі және оған арналған жақсы құрылымдар белгілі.^[2] Блоктардың ең болмағанда біреуі мин-энтропияға ие болғандықтан, ең болмағанда біреуі формаға өте жақын.
Біріктіруді пайдаланып, барлық алдыңғы нәтижелерді бір жолға біріктіріңіз. Егер жақсы бірігу қолданылса, онда нәтижелік жолдың ұзындығымен салыстырғанда мин-энтропиясы өте жоғары болады.
Кездейсоқтықты шығару үшін тек минт-энтропияның өте жоғары көздері үшін жұмыс істейтін белгілі экстракторды қолданыңыз.

Жоғарыда келтірілген схеманың мәні ерікті мин-энтропиясы бар жолды кіші жолға айналдыру үшін біріктіруді қолдану болып табылады, сонымен қатар процесте мин-энтропияны көп жоғалтпайды. Бұл жаңа жолдың ұзындығымен салыстырғанда мин-энтропиясы өте жоғары, содан кейін тек осы тізбектер үшін жұмыс істейтін, ескі, белгілі экстракторларды қолдануға болады.

Сондай-ақ қараңыз

Кездейсоқтық шығарғыш

Әдебиеттер тізімі

^ Де, Портманн, Видик және Реннер (2009). «Кванттық жанама ақпарат болған кезде Тревизанның экстракторы». Есептеу бойынша SIAM журналы. 41 (4): 915–940. arXiv:0912.5514. дои:10.1137/100813683.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме) 2.2 бөлім.
^ ^а ^б ^c Зеев Двир және Ави Уигдерсон. «Какея жиынтықтары, жаңа қосылыстар және ескі сорғыштар» (PDF).
^ Ноам Ниссан және Амнон Та-Шма. «Кездейсоқтықты алу: зерттеу және жаңа құрылыстар» (PDF). 4.3 бөлім.
^ Амнон Та-Шма. «Кездейсоқтықты жақсарту». PhD докторы Диссертация.

[1] Де, Портманн, Видик және Реннер (2009). «Кванттық жанама ақпарат болған кезде Тревизанның экстракторы». Есептеу бойынша SIAM журналы. 41 (4): 915–940. arXiv:0912.5514. дои:10.1137/100813683.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме) 2.2 бөлім.

[dvir-wigderson-2] а ^б ^c Зеев Двир және Ави Уигдерсон. «Какея жиынтықтары, жаңа қосылыстар және ескі сорғыштар» (PDF).

[3] Ноам Ниссан және Амнон Та-Шма. «Кездейсоқтықты алу: зерттеу және жаңа құрылыстар» (PDF). 4.3 бөлім.

[4] Амнон Та-Шма. «Кездейсоқтықты жақсарту». PhD докторы Диссертация.

[1]

[2]

[3]

[4]