Каков наилучший способ получить бросок монеты с одинаковым смещением?

21

(Фон Нейман дал алгоритм, который имитирует честную монету при доступе к одинаковым смещенным монетам. Алгоритм потенциально требует бесконечного числа монет (хотя в ожидании достаточно конечного числа). Этот вопрос касается случая, когда допустимое количество бросков монет ограниченная.)

Предположим, у нас есть одинаковых монет с уклоном . Цель состоит в том, чтобы смоделировать бросок одной монеты при минимальном смещении.δ = P [ H e a d ] - P [ T a i l ]nδ=P[Head]P[Tail]

Моделирование должно быть эффективным в следующем смысле: алгоритм, работающий за полиномиальное время, просматривает случайных битов и выводит один бит. Смещение алгоритма определяется какгде ожидание берется по распределению, определенному iid битами такими, что Prob [x_i = 1] -Prob [x_i = 0] = \ delta .B i a s ( A ) = | E [ A = 0 ] - E [ A = 1 ] | n x 1 , , x n P r o b [ x i = 1 ] - P r o b [ x inBias(A)=|E[A=0]E[A=1]|nx1,,xnProb[xi=1]Prob[xi=0]=δ

Какой алгоритм работает в полиномиальное время имеет наименьшее смещение смещения (А) ?ABias(A)

Этот вопрос кажется мне очень естественным, и вполне вероятно, что он рассматривался ранее.

Что известно об этой проблеме? Известно ли что-нибудь, когда рассматривается более слабый класс (в AC0 и т. Д.) Алгоритмов?

Hrushikesh
источник

Ответы:

15

Бросив n смещенных монет и взяв соотношение паритетов, экспоненциально приближается к .12

[Для доказательства рассмотрим случайную переменную, которая равна -1 для голов и 1 для хвостов, тогда вероятность наличия нечетного числа голов составляет всего лишь ]E[12+12iXi]=12+12δn

Возможно, это также оптимально по следующей причине. Пусть будет любой композиционной функцией этих битов. Тогда и лучшим кажется функцией четности (не так ли?).fBias(f)=Sf^(S)δ|S|f

Если вы заинтересованы в композиционных функциях меньшей сложности, то, возможно, статья Райана О'Доннелла «Усиление твердости в NP» была бы очень актуальной. Там он использует монотонные композиционные функции для усиления твердости, а функции, которые работают, характеризуются их чувствительностью к шуму.

Ramprasad
источник
Не могли бы вы пояснить, почему паритет должен быть лучшей функцией? (Кроме того , не то, что она имеет значение очень асимптотически, но не должно быть , что в разложении Фурье , так как Е [ х я ] = δ ?). Спасибо за указатель на бумагу! delta|S|E[xi]=δ
Хрушикеш
О, извини, ты прав. Выражение было неверным и теперь исправили его. У меня нет доказательства оптимальности (возможно , не является оптимальным) , но причина , почему я догадался так, что это было бы верно , если выражение было вместо так как это тогда выпуклая комбинация. Sf^(S)2δ|S|
Рампрасад
Возможно, это могло бы пролить некоторый свет. По Коши-Шварца, мы знаем , что , Одним из способов оптимизации было бы сведение к минимуму верхней границы, насколько это возможно, и это происходит, когда функцияfявляется функцией четности, и в этом случае интересующая нас величина совпадает также с верхней границей. Однако, это может быть тот случай, когда вектор коэффициентов Фурье полностью ортогоналенδ-вектору, и в этом случае LHS равен нулю! Существуют ли специальные значенияδ,для которых мы знаем такие примеры? Sf^(S)S:f^(S)0δ2|S|fδδ
Рампрасад
На самом деле, если взять какую-то нетривиальную монотонную функцию , то при δ = - 1 ожидание вероятности того, что f ( x 1 , , x n ) = 1, равно 0, а при δ = 1 - 1 . Следовательно, для некоторого промежуточного δ оно должно принимать значение 1fδ=1f(x1,,xn)=1δ=11δ . Следовательно, было бы несправедливо ожидать, что для каждогоδфункция четности является оптимальной. 12δ
Рампрасад
Можете ли вы объяснить последний комментарий более подробно? Игнорирование проблемы сложности F, является не ваше заключение верно только если для б 1E[f]=1/2 поскольку четность принимает смещение отδдоδn? δ121/nδδn
Хрушикеш
12

Вы не говорите, если предвзятость известна или неизвестна. Магия алгоритма фон Неймана заключается в том, что он работает в любом случае.

Предположим, это известно. Лучший ответ в этом случае критически зависит от теоретических особенностей смещения. Давайте возьмем р = 2/3. Подбросьте монету дважды и отобразите HH на 0, а TH и HT на 1, повторив эксперимент, если результат будет TT. Тогда 0 и 1 одинаково вероятны, и вероятность повторения составляет всего 1/9 вместо 5/9 с алгоритмом фон Неймана. Или, если выразить это словами, вы смещаете один из результатов только на 1/9, если ваш предел итерации равен 2.

Все это тесно связано с теорией информации и теорией кодирования. Когда p является дробью с более сложным числителем и знаменателем, лучший алгоритм потребует большей длины блока, чем 2. Вы можете использовать аргумент существования в стиле Шеннона, чтобы показать, что для данного смещения существует процедура, которая является оптимальной, так как Вы хотите, но длина блока может быть очень большой.

Перес в своей статье « Итерация процедуры фон Неймана для извлечения случайных битов» доказывает, что версия алгоритма фон Неймана может подходить к пределу Шеннона произвольно хорошо. Большая часть работы в этой области, похоже, была проделана теоретиками и статистиками, поэтому я не могу представить ни одного документа с теоретико-сложным уклоном, который бы дал вам прямой ответ на ваш вопрос.

Существует забавная проблема, которая требует обратного: если у вас есть источник достоверных битов, как вы эффективно генерируете равномерное распределение по некоторому набору не-степени-двух? Ограниченная итерациями версия проблемы, схожая с вашим вопросом, просит максимизировать энтропию (т.е. сделать распределение как можно более равномерным) с n бросками честной монеты.

Пер Вогсен
источник
1
Мне пришло в голову, что оптимизация времени выполнения без смещения (то, что делает бумага) - это двойственное отношение Лагранжа к оптимизации смещения в зависимости от времени работы. Итак, я думаю, что статья действительно отвечает на ваш вопрос!
Per Vognsen
5

Я предпочитаю думать об этом вопросе в следующей обобщенной форме: у нас есть полное двоичное дерево высоты n, где каждому узлу присваивается число, а сумма чисел равна 1. Можем ли мы разделить листья на два множества, где суммы номера их близки?

pq=1ppiqni

i(ni)parity(x)piqni=i(ni)(p)iqni=(qp)n

PSpace

РЕДАКТИРОВАТЬ "Это в основном проблема кодирования Шеннона." (Спасибо Per Vognsen.) Конец редактирования

AC0

(Этот ответ может содержать ошибки, я не проверил детали.)

Кава
источник
2
«Можем ли мы разделить листья на два набора, чтобы суммы чисел были близки?» Это в основном проблема кодирования Шеннона. Алгоритм Шеннона-Фано является нисходящим и начинается с набора взвешенных по вероятности элементов и запрашивает четное разделение на две части. Применение этого рекурсивно дает интегральный код без префиксов. Алгоритм Хаффмана является восходящим: он начинается с одноэлементных деревьев и многократно объединяет пары с минимальной вероятностью. Если вы знаете об арифметическом кодировании, это также справедливо говорит о том, что лучше генерировать сразу несколько правильных битов, а не по одному за раз.
Per Vognsen
4

Вы также можете получить много случайных битов из смещенных монет, см. Статью Габизона «Дерандомизированные алгоритмы» в разделе «Распределение продуктов» (http://sites.google.com/site/arielgabizon1/).


источник
1

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

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