Выборочное пространство с малым смещением

В теоретической информатике пространство выборки с малым смещением (также известное как $\epsilon$ -предвзятое пространство выборки , $\epsilon$ -смещенный генератор , или вероятностное пространство с малым смещением ) — это распределение вероятностей , которое обманывает функции четности .Другими словами, ни одна функция четности не может отличить пространство выборок с малым смещением от равномерного распределения с высокой вероятностью, и, следовательно, пространства выборок с малым смещением естественным образом приводят к появлению псевдослучайных генераторов для функций четности.

Основное полезное свойство выборочных пространств с малым смещением заключается в том, что им требуется гораздо меньше действительно случайных битов, чем при равномерном распределении, чтобы обмануть четность. Эффективные конструкции выборочных пространств с малым смещением нашли множество применений в информатике, некоторые из которых — дерандомизация , коды, исправляющие ошибки , и вероятностно проверяемые доказательства .Связь с кодами, исправляющими ошибки, на самом деле очень сильна, поскольку $\epsilon$ выборочные пространства эквивалентны -смещенные $\epsilon$ -сбалансированные коды, исправляющие ошибки .

Определение

Предвзятость

Позволять $X$ быть распределением вероятностей по $\{0,1\}^{n}$ .Предвзятость $X$ относительно набора индексов $I\subseteq \{1,\dots ,n\}$ определяется как ^[1]

{\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|\,,

где сумма берется $\mathbb {F} _{2}$ , конечное поле с двумя элементами. Другими словами, сумма $\sum _{i\in I}x_{i}$ равно $0$ если число единиц в выборке $x\in \{0,1\}^{n}$ в положениях, определенных $I$ четно, в противном случае сумма равна $1$ .Для $I=\emptyset$ пустая сумма определяется как ноль, и, следовательно, ${\text{bias}}_{\emptyset }(X)=1$ .

ϵ-смещенное пространство выборки

Распределение вероятностей $X$ над $\{0,1\}^{n}$ называется $\epsilon$ -смещенное пространство выборки, если ${\text{bias}}_{I}(X)\leq \epsilon$ справедливо для всех непустых подмножеств $I\subseteq \{1,2,\ldots ,n\}$ .

ϵ-смещенный набор

Ан $\epsilon$ -предвзятое пространство выборки $X$ который генерируется путем выбора однородного элемента из мультимножества $X\subseteq \{0,1\}^{n}$ называется $\epsilon$ -предвзятый набор .Размер $s$ из $\epsilon$ -предвзятый набор $X$ — это размер мультимножества, генерирующего выборочное пространство.

ϵ-смещенный генератор

Ан $\epsilon$ -смещенный генератор $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ это функция, которая отображает строки длины $\ell$ на строки длины $n$ такое, что мультимножество $X_{G}=\{G(y)\;\vert \;y\in \{0,1\}^{\ell }\}$ это $\epsilon$ -предвзятый набор. Начальная длина генератора равна числу $\ell$ и связано с размером $\epsilon$ -предвзятый набор $X_{G}$ через уравнение $s=2^{\ell }$ .

Связь с эпсилон-сбалансированными кодами, исправляющими ошибки.

Существует тесная связь между $\epsilon$ -смещенные множества и $\epsilon$ -сбалансированные линейные коды, исправляющие ошибки .Линейный код $C:\{0,1\}^{n}\to \{0,1\}^{s}$ длины сообщения $n$ и длина блока $s$ является $\epsilon$ -сбалансировано , если вес Хэмминга каждого ненулевого кодового слова $C(x)$ находится между $({\frac {1}{2}}-\epsilon )s$ и $({\frac {1}{2}}+\epsilon )s$ .С $C$ является линейным кодом, его порождающая матрица представляет собой $(n\times s)$ -матрица $A$ над $\mathbb {F} _{2}$ с $C(x)=x\cdot A$ .

Тогда справедливо, что мультимножество $X\subset \{0,1\}^{n}$ является $\epsilon$ -смещенным тогда и только тогда, когда линейный код $C_{X}$ , столбцы которого являются в точности элементами $X$ , является $\epsilon$ -сбалансированный. ^[2]

Конструкции небольших множеств, смещенных эпсилоном.

Обычно цель состоит в том, чтобы найти $\epsilon$ -смещенные множества, имеющие небольшой размер $s$ относительно параметров $n$ и $\epsilon$ .Это потому, что меньший размер $s$ означает, что степень случайности, необходимая для выбора случайного элемента из набора, меньше, и поэтому набор можно использовать для обмана четности, используя несколько случайных битов.

Теоретические границы

Вероятностный метод дает неявную конструкцию, достигающую размера $s=O(n/\epsilon ^{2})$ . ^[2]Конструкция неявная в том смысле, что нахождение $\epsilon$ -предвзятый набор требует большого количества истинной случайности, что не способствует достижению цели уменьшения общей случайности.Однако эта неявная конструкция полезна, поскольку показывает, что такие эффективные коды существуют.С другой стороны, наиболее известная нижняя граница размера $\epsilon$ -смещенные множества - это $s=\Omega (n/(\epsilon ^{2}\log(1/\epsilon ))$ , то есть для того, чтобы набор был $\epsilon$ -предвзятый, он должен быть как минимум таким большим. ^[2]

Явные конструкции

Существует множество явных, т. е. детерминированных конструкций $\epsilon$ -смещенные наборы с различными настройками параметров:

Наор и Наор (1990) достигают $\displaystyle s={\frac {n}{{\text{poly}}(\epsilon )}}$ . В конструкции используются коды Юстесена (которые представляют собой конкатенацию кодов Рида-Соломона с ансамблем Возенкрафта ), а также расширенная выборка обхода .
Алон и др. (1992) достичь $\displaystyle s=O\left({\frac {n}{\epsilon \log(n/\epsilon )}}\right)^{2}$ . Одна из их конструкций — объединение кодов Рида–Соломона с кодом Адамара ; эта конкатенация оказывается $\epsilon$ -сбалансированный код, что приводит к $\epsilon$ -смещенное пространство выборки через упомянутую выше связь.
Объединение алгебраических геометрических кодов с кодом Адамара дает $\epsilon$ -сбалансированный код с $\displaystyle s=O\left({\frac {n}{\epsilon ^{3}\log(1/\epsilon )}}\right)$ . ^[2]
Бен-Аройя и Та-Шма (2009) достигают $\displaystyle s=O\left({\frac {n}{\epsilon ^{2}\log(1/\epsilon )}}\right)^{5/4}$ .
Та-Шма (2017) достигает $\displaystyle s=O\left({\frac {n}{\epsilon ^{2+o(1)}}}\right)$ что почти оптимально из-за нижней границы.

Эти границы несопоставимы. В частности, ни одна из этих конструкций не дает наименьшего $\epsilon$ -смещенные множества для всех настроек $\epsilon$ и $n$ .

Приложение: почти k-зависимая независимость.

Важным применением множеств с малым смещением является построение почти k-независимых выборочных пространств.

k-мудрое независимые пространства

Случайная величина $Y$ над $\{0,1\}^{n}$ является k-независимым пространством , если для всех наборов индексов $I\subseteq \{1,\dots ,n\}$ размера $k$ , предельное распределение $Y|_{I}$ в точности равно равномерному распределению по $\{0,1\}^{k}$ .То есть для всех таких $I$ и все строки $z\in \{0,1\}^{k}$ , распределение $Y$ удовлетворяет $\Pr _{Y}(Y|_{I}=z)=2^{-k}$ .

Конструкции и границы

k-образные независимые пространства достаточно хорошо изучены.

Простая конструкция Иоффе (1974) достигает размера $n^{k}$ .
Алон, Бабай и Итай (1986) строят независимое по k-му пространству размер которого равен $n^{k/2}$ .
Чор и др. (1985) доказывают, что никакое независимое по k-му пространству не может быть значительно меньше, чем $n^{k/2}$ .

конструкция Иоффе

Иоффе (1974) строит $k$ -мудрое независимое пространство $Y$ над конечным полем с некоторым простым числом $n>k$ элементов, т.е. $Y$ это распределение по $\mathbb {F} _{n}^{n}$ . Начальный $k$ Маргинальные границы распределения рисуются независимо и равномерно случайным образом:

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

.

Для каждого $i$ с $k\leq i<n$ , предельное распределение $Y_{i}$ затем определяется как

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

где расчет производится в $\mathbb {F} _{n}$ . Иоффе (1974) доказывает, что распределение $Y$ построенный таким образом, $k$ -мудро независимым как распределение по $\mathbb {F} _{n}^{n}$ .Распределение $Y$ однородна на своем носителе, а значит, и на носителе $Y$ образует $k$ -мудрое независимое множество .Он содержит все $n^{k}$ струны в $\mathbb {F} _{n}^{k}$ которые были расширены до строк длиной $n$ используя детерминированное правило, приведенное выше.

Почти k-мудрое независимые пространства

Случайная величина $Y$ над $\{0,1\}^{n}$ это $\delta$ -почти k-независимое пространство , если для всех наборов индексов $I\subseteq \{1,\dots ,n\}$ размера $k$ , ограниченное распространение $Y|_{I}$ и равномерное распределение $U_{k}$ на $\{0,1\}^{k}$ являются $\delta$ -близко по 1-норме , т.е. ${\Big \|}Y|_{I}-U_{k}{\Big \|}_{1}\leq \delta$ .

Конструкции

Наор и Наор (1990) дают общую основу для объединения малых k-независимых пространств с небольшими $\epsilon$ -смещенные пространства для получения $\delta$ -почти k-независимые пространства еще меньшего размера.В частности, пусть $G_{1}:\{0,1\}^{h}\to \{0,1\}^{n}$ — линейное отображение , порождающее k-независимое пространство, и пусть $G_{2}:\{0,1\}^{\ell }\to \{0,1\}^{h}$ быть генератором $\epsilon$ - предвзятый набор $\{0,1\}^{h}$ .То есть, при наличии равномерно случайного входного сигнала, выход $G_{1}$ является k-независимым пространством, а результат $G_{2}$ является $\epsilon$ -пристрастный.Затем $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ с $G(x)=G_{1}(G_{2}(x))$ является генератором $\delta$ -почти $k$ -мудрое независимое пространство, где $\delta =2^{k/2}\epsilon$ . ^[3]

Как упоминалось выше, Алон, Бабай и Итай (1986) построили генератор. $G_{1}$ с $h={\tfrac {k}{2}}\log n$ и Наор и Наор (1990) строят генератор $G_{2}$ с $\ell =\log s=\log h+O(\log(\epsilon ^{-1}))$ .Следовательно, конкатенация $G$ из $G_{1}$ и $G_{2}$ имеет длину семени $\ell =\log k+\log \log n+O(\log(\epsilon ^{-1}))$ .Для того, чтобы $G$ чтобы дать $\delta$ -почти k-независимое пространство, нам нужно положить $\epsilon =\delta 2^{-k/2}$ , что приводит к длине семени $\ell =\log \log n+O(k+\log(\delta ^{-1}))$ и выборочное пространство общего размера $2^{\ell }\leq \log n\cdot {\text{poly}}(2^{k}\cdot \delta ^{-1})$ .

Примечания

^ ср., например, Goldreich (2001).
^ Jump up to: ^а ^б ^с ^д ср., например, стр. 2 Бен-Аройя и Та-Шма (2009)
^ Раздел 4 в Наор и Наор (1990)

Ссылки

Алон, Нога; Бабай, Ласло; Итай, Алон (1986), «Быстрый и простой рандомизированный параллельный алгоритм для задачи максимального независимого множества» (PDF) , Journal of Algorithms , 7 (4): 567–583, doi : 10.1016/0196-6774(86)90019 -2
Алон, Нога; Гольдрейх, Одед; Хостад, Йохан; Перальта, Рене (1992), «Простые конструкции почти k-независимых случайных величин» (PDF) , Случайные структуры и алгоритмы , 3 (3): 289–304, CiteSeerX 10.1.1.106.6442 , doi : 10.1002/rsa. 3240030308
Бен-Аройя, Авраам; Та-Шма, Амнон (2009). «Построение множеств малого смещения из алгебро-геометрических кодов». 50-й ежегодный симпозиум IEEE по основам информатики, 2009 г. (PDF) . стр. 191–197. CiteSeerX 10.1.1.149.9273 . дои : 10.1109/FOCS.2009.44 . ISBN 978-1-4244-5116-6 .
Чор, Бенни ; Гольдрейх, Одед; Хостад, Йохан; Фрейдманн, Джоэл; Рудич, Стивен; Смоленский, Роман (1985). «Проблема извлечения битов или t-устойчивые функции». 26-й ежегодный симпозиум по основам информатики (SFCS, 1985) . стр. 396–407. CiteSeerX 10.1.1.39.6768 . дои : 10.1109/SFCS.1985.55 . ISBN 978-0-8186-0644-1 . S2CID 6968065 .
Гольдрайх, Одед (2001), Лекция 7: Выборочные пространства с малым смещением
Иоффе, Анатоль (1974), «О множестве почти детерминированных k-независимых случайных величин», Annals of Probability , 2 (1): 161–162, doi : 10.1214/aop/1176996762
Наор, Джозеф; Наор, Мони (1990), «Вероятностные пространства с малым смещением: эффективные конструкции и приложения», Труды двадцать второго ежегодного симпозиума ACM по теории вычислений - STOC '90 , стр. 213–223, CiteSeerX 10.1.1.421.2784 , doi : 10.1145/100216.100244 , ISBN 978-0897913614 , S2CID 14031194
Та-Шма, Амнон (2017), «Явные, почти оптимальные, эпсилон-сбалансированные коды», Труды 49-го ежегодного симпозиума ACM SIGACT по теории вычислений , стр. 238–251, doi : 10.1145/3055399.3055408 , ISBN 9781450345286 , S2CID 5648543

[1] ср., например, Goldreich (2001).

[BA-TS-09-2] Jump up to: ^а ^б ^с ^д ср., например, стр. 2 Бен-Аройя и Та-Шма (2009)

[3] Раздел 4 в Наор и Наор (1990)

[1]

[2]

[3]