Имитация вероятности 1 из 2 ^ N с менее чем N случайными битами

Скажем, мне нужно смоделировать следующее дискретное распределение:

P (X = k) = {\begin{cases} \frac{1}{2^{N}}, & if k = 1 \\ 1 - \frac{1}{2^{N}}, & if k = 0 \end{cases}

$P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases}$

Наиболее очевидный способ - нарисовать случайных битов и проверить, все ли они равны (или ). Тем не менее, теория информации говорит $N$ $0$ $1$

\begin{aligned} S & = - \sum_{i} P_{i} \log P_{i} \\ = - \frac{1}{2^{N}} \log \frac{1}{2^{N}} - (1 - \frac{1}{2^{N}}) \log (1 - \frac{1}{2^{N}}) \\ = \frac{1}{2^{N}} \log 2^{N} + (1 - \frac{1}{2^{N}}) \log \frac{2^{N}}{2^{N} - 1} \\ \to 0 \end{aligned}

$\begin{align} S & = - \sum_{i} P_i \log{P_i} \\ & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\ & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\ & \rightarrow 0 \end{align}$

Таким образом, минимальное количество битов , требуемых случайных фактически уменьшается , как $N$ идет большой. Как это возможно?

Пожалуйста, предположим, что мы работаем на компьютере, где биты - ваш единственный источник случайности, поэтому вы не можете просто подбросить необъективную монету.

algorithms information-theory randomness pseudo-random-generators entropy nalzok
источник

Это тесно связано с теорией кодирования и сложностью Колмогорова, если вы ищете ключевые слова, чтобы копать глубже. Техника подсчета повторяющихся серий одного и того же бита, о которой упоминает Д. У., встречается очень часто

Брайан Гордон,

Ответы:

Вау, отличный вопрос! Позвольте мне попытаться объяснить решение. Это займет три четких шага.

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

В вашей процедуре выборки максимальное количество случайных битов, необходимых для каждого отрисовки, составляет битов, но среднее количество необходимых битов составляет 2 бита (среднее геометрического распределения с ) - это потому, что существует Вероятность что вам нужен только 1 бит (если первый бит оказывается равным 1), вероятность что вам нужно только 2 бита (если первые два бита оказываются равным 01), вероятность того, что вам нужно только 3 бита (если первые три бита окажутся 001), и так далее. $N$ $p=1/2$ $1/2$ $1/4$ $1/8$

Второе, на что следует обратить внимание, - это то, что энтропия на самом деле не фиксирует среднее количество бит, необходимое для одного розыгрыша. Вместо этого, энтропия захватывает амортизируется число бит , необходимых для выборки IID извлекает из этого распределения. Предположим, нам нужно бит для выборки отрисовок; тогда энтропия является пределом как . $m$ $f(m)$ $m$ $f(m)/m$ $m \to \infty$

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

Но оказывается, что есть способ сэмплировать из дро с использованием менее 2 битов. В это трудно поверить, но это правда! $m$ $2m$

Позвольте мне дать вам интуицию. Предположим, вы записали результат выборки розыгрышей, где действительно велико. Тогда результат может быть указан в виде битной строки. Эта битная строка будет в основном 0, с несколькими 1: в частности, в среднем она будет иметь около 1 (может быть больше или меньше, но если достаточно велико, обычно номер будет близок к этому). Длина промежутков между единицами случайна, но, как правило, будет где-то расплывчато в окрестности (легко может быть вдвое больше или вдвое больше или даже больше, но такого порядка). Конечно, вместо записи всего $m$ $m$ $m$ $m$ $m/2^N$ $m$ $2^N$ $m$ -битная строка, мы могли бы записать ее более кратко, записав список длин пропусков, который несет всю ту же информацию, в более сжатом формате. Насколько более кратким? Ну, нам обычно потребуется около бит для представления длины каждого промежутка; и будет около пробелов; поэтому нам нужно всего около битов (может быть немного больше, может быть немного меньше, но если достаточно велико, оно обычно будет близко к этому). Это намного короче, чем строка бита. $N$ $m/2^N$ $mN/2^N$ $m$ $m$

И если есть способ записать строку так кратко, возможно, это не будет слишком удивительно, если это означает, что есть способ генерировать строку с числом случайных битов, сопоставимых с длиной строки. В частности, вы случайным образом генерируете длину каждого разрыва; это выборка из геометрического распределения с , и это можно сделать с примерно случайных битов в среднем (не ). Вам понадобится примерно iid-отрисовок из этого геометрического распределения, так что вам понадобится всего примерно случайных битов. (Это может быть небольшой постоянный коэффициент больше, но не слишком большой.) И обратите внимание, что это намного меньше, чем бит. $p=1/2^N$ $\sim N$ $2^N$ $m/2^N$ $\sim Nm/2^N$ $2m$

Таким образом, мы можем попробовать н.о.р. розыгрышей от вашего дистрибутива, используя только случайных битов (примерно). Напомним, что энтропия равна . Таким образом , это означает , что вы должны ожидать , что энтропия будет (примерно) . Это немного, потому что приведенный выше расчет был отрывочным и грубым - но, надеюсь, он даст вам некоторое представление о том, почему энтропия такая, какая она есть, и почему все последовательно и разумно. $m$ $f(m) \sim Nm/2^N$ $\lim_{m \to \infty} f(m)/m$ $N/2^N$

DW
источник

Вау, отличный ответ! Но не могли бы вы пояснить, почему выборка из геометрического распределения с занимает в среднем битов? Я знаю, что такая случайная переменная будет иметь среднее значение , поэтому для ее хранения требуется в среднем битов, но я предполагаю, что это не означает, что вы можете сгенерировать ее с битами.

p = \frac{1}{2^{N}}

$p=\frac{1}{2^N}$

N

$N$

2^{N}

$2^N$

N

$N$

N

$N$

Нальзок

@nalzok, честный вопрос! Не могли бы вы задать это как отдельный вопрос? Я понимаю, как это сделать, но набрать текст сейчас довольно сложно. Если вы спросите, возможно, кто-то ответит быстрее, чем я. Подход, о котором я думаю, похож на арифметическое кодирование. Определите (где - геометрическое rv), затем сгенерируйте случайное число в интервале и найдите такой, что . Если вы записываете биты двоичного расхода одному, обычно после записи битов , будет полностью определено.

q_{i} = Pr [X \leq i]

$q_i = \Pr[X\le i]$

X

$X$

r

$r$

[0, 1)

$[0,1)$

i

$i$

q_{i} \leq r < q_{i + 1}

$q_i \le r < q_{i+1}$

r

$r$

N + O (1)

$N+O(1)$

r

$r$

i

$i$

Таким образом, вы в основном используете метод обратного CDF для преобразования равномерно распределенной случайной величины в произвольное распределение в сочетании с идеей, аналогичной бинарному поиску? Мне нужно проанализировать квантильную функцию геометрического распределения, чтобы убедиться, но этого нам достаточно. Благодарность!

Нальзок

@nalzok, ах, да, это хороший способ думать об этом - прекрасно. Спасибо, что предложили это. Да, это то, что я имел в виду.

Вы можете думать об этом задом наперед: рассмотрите проблему двоичного кодирования вместо генерации. Предположим, что у вас есть источник, который испускает символы с , . Например, если , мы получаем . Итак, (говорит нам Шеннон), существует уникально декодируемое двоичное кодирование , где (биты данных), так что нам нужно в среднем около битов данных для каждого исходного символа . $X\in \{A,B\}$ $p(A)=2^{-N}$ $p(B)=1-2^{-N}$ $N=3$ $H(X)\approx 0.54356$ $X \to Y$ $Y \in \{0,1\}$ $0.54356$ $X$

(В случае, если вам интересно, как такое кодирование может существовать, учитывая, что у нас есть только два исходных символа, и кажется, что мы не можем сделать лучше, чем тривиальное кодирование, , , с одним битом на символ, Вы должны понимать, что для аппроксимации границы Шеннона нам нужно взять «расширения» источника, то есть кодировать последовательности входов в целом (см., в частности, арифметическое кодирование). $A\to 0$ $B\to 1$

Как только вышеприведенное ясно, если мы предположим, что у нас есть обратимое отображение , и отметим, что в пределе Шеннона должен иметь максимальную энтропию (1 бит информации на бит данных), т.е. , имеет статистику честной монеты, тогда у нас есть схема генерации: нарисуйте случайных битов (здесь не имеет отношения к ) с честной монетой, интерпретируйте ее как вывод кодера и декодировать из него. Таким образом, будет иметь желаемое распределение вероятностей, и нам нужно (в среднем) монеты , чтобы генерировать каждое значение . $X^n \to Y^n$ $Y^n$ $Y^n$ $n$ $n$ $N$ $Y^n$ $X^n$ $X^n$ $H(X)<1$ $X$

leonbloy
источник