Случайное слияние

В экстракторов теории слияние случайностей — это функция, которая извлекает случайность из набора случайных величин при условии, что хотя бы одна из них является равномерно случайной. Его название связано с тем, что его можно рассматривать как процедуру, которая «объединяет» все переменные в одну, сохраняя по крайней мере часть энтропии, содержащейся в равномерно случайной величине. В настоящее время слияния используются для явного создания экстракторов случайности.

Интуиция и определение

Рассмотрим набор $k$ случайные величины , $X_{1},\ldots ,X_{k}$, каждый из которых распределен по $\{0,1\}^{n}$ по крайней мере один из которых является равномерно случайным; но неизвестно какой. Более того, переменные могут быть произвольно коррелированы: они могут быть функциями друг друга, могут быть постоянными и так далее. Однако, поскольку хотя бы один из них однороден, множество в целом содержит не менее $n$ кусочки энтропии.

Задача слияния — вывести новую случайную величину, также распределенную по $\{0,1\}^{n}$, который сохраняет как можно большую часть этой энтропии. В идеале, если бы было известно, какая из переменных является однородной, ее можно было бы использовать в качестве выходных данных, но эта информация неизвестна. Идея слияний заключается в том, что, используя небольшое дополнительное случайное начальное число, можно получить хороший результат, даже не зная, какая из них является универсальной переменной.

Наивной идеей было бы выполнить операцию xor всех переменных. Если одна из них распределена равномерно и не зависит от других переменных, то результат будет однородным. Однако, если предположить $X_{1}=X_{2}$, и оба они распределены равномерно, то метод не будет работать.

Определение (слияние):

Функция $M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}$ называется $(m,\varepsilon )$-merger if для каждого набора случайных величин $(X_{1},\ldots ,X_{k})$ распределено по $\{0,1\}^{n}$, хотя бы один из которых является равномерным, распределение $Z=M(X_{1},\ldots ,X_{k},U_{d})$ имеет гладкую минимальную энтропию $H_{\infty }^{\varepsilon }(Z)\geq m$. Переменная $U_{d}$ обозначает равномерное распределение по $d$ бит и представляет собой действительно случайное начальное число.

Другими словами, используя небольшое однородное семя длиной $d$, слияние возвращает строку, которая $\varepsilon$- близко к тому, чтобы иметь по крайней мере $m$ мин-энтропия ; это означает, что его статистическое расстояние от строки с $m$ мин-энтропия не больше, чем $\varepsilon$.

Напоминание : существует несколько понятий измерения случайности распределения; минимальная энтропия случайной величины $Z$ определяется как самый крупный $k$ такая, что наиболее вероятное значение $Z$ происходит с вероятностью не более $2^{-k}$. Минимальная энтропия строки — это верхняя граница количества случайности, которую можно извлечь из нее.

Параметры

Есть три параметра, которые следует оптимизировать при построении слияний:

1. Минимальная энтропия вывода $m$ должно быть как можно выше, так как тогда из него можно будет извлечь больше битов.
2. $\varepsilon$ должно быть как можно меньше, так как тогда после применения экстрактора к выходу слияния результат будет ближе к равномерному.
3. Длина семени $d$ должно быть как можно меньше, поскольку тогда для работы слияния потребуется меньше начальных действительно случайных битов.

Известны явные конструкции слияний с относительно хорошими параметрами. Например, конструкция Двира и Вигдерсона дает: Для каждого $\alpha >0$ и целое число $n$, если $k\leq 2^{o(n)}$, существует явное $(m,\varepsilon )$-слияние $M:(\{0,1\}^{n})^{k}\times \{0,1\}^{d}\rightarrow \{0,1\}^{n}$ такой, что:

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

Доказательство конструктивно и позволяет построить такое слияние за полиномиальное время по заданным параметрам.

Использование

Можно использовать слияния для создания экстракторов случайности с хорошими параметрами. Напомним, что экстрактор — это функция, которая принимает случайную величину с высокой минимальной энтропией и возвращает случайную величину меньшего размера, но близкую к однородной. Произвольный экстрактор минимальной энтропии можно получить, используя следующую схему, основанную на слиянии:

• Учитывая источник высокой минимальной энтропии, разделите его на блоки. По известному результату по крайней мере один из этих разделов также будет иметь высокую минимальную энтропию в качестве источника блока.
• Примените экстрактор блоков отдельно ко всем блокам. Это более слабый тип экстрактора, и хорошие конструкции для него известны. Поскольку хотя бы один из блоков имеет высокую минимальную энтропию, по крайней мере один из выходных данных очень близок к равномерному.
• Используйте слияние, чтобы объединить все предыдущие результаты в одну строку. Если используется хорошее слияние, то результирующая строка будет иметь очень высокую минимальную энтропию по сравнению с ее длиной.
• Используйте известный экстрактор, который работает только для источников с очень высокой минимальной энтропией, чтобы извлечь случайность.

Суть приведенной выше схемы заключается в использовании слияния для преобразования строки с произвольной минимальной энтропией в меньшую строку, при этом не теряя при этом много минимальной энтропии. Эта новая строка имеет очень высокую минимальную энтропию по сравнению с ее длиной, и тогда можно использовать старые, известные экстракторы, которые работают только для строк этого типа.

См. также

• Экстрактор случайности