(Фон Нейман дал алгоритм, который имитирует честную монету при доступе к одинаковым смещенным монетам. Алгоритм потенциально требует бесконечного числа монет (хотя в ожидании достаточно конечного числа). Этот вопрос касается случая, когда допустимое количество бросков монет ограниченная.)
Предположим, у нас есть одинаковых монет с уклоном . Цель состоит в том, чтобы смоделировать бросок одной монеты при минимальном смещении.δ = P [ H e a d ] - P [ T a i l ]
Моделирование должно быть эффективным в следующем смысле: алгоритм, работающий за полиномиальное время, просматривает случайных битов и выводит один бит. Смещение алгоритма определяется какгде ожидание берется по распределению, определенному 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 i
Какой алгоритм работает в полиномиальное время имеет наименьшее смещение смещения (А) ?
Этот вопрос кажется мне очень естественным, и вполне вероятно, что он рассматривался ранее.
Что известно об этой проблеме? Известно ли что-нибудь, когда рассматривается более слабый класс (в и т. Д.) Алгоритмов?
Вы не говорите, если предвзятость известна или неизвестна. Магия алгоритма фон Неймана заключается в том, что он работает в любом случае.
Предположим, это известно. Лучший ответ в этом случае критически зависит от теоретических особенностей смещения. Давайте возьмем р = 2/3. Подбросьте монету дважды и отобразите HH на 0, а TH и HT на 1, повторив эксперимент, если результат будет TT. Тогда 0 и 1 одинаково вероятны, и вероятность повторения составляет всего 1/9 вместо 5/9 с алгоритмом фон Неймана. Или, если выразить это словами, вы смещаете один из результатов только на 1/9, если ваш предел итерации равен 2.
Все это тесно связано с теорией информации и теорией кодирования. Когда p является дробью с более сложным числителем и знаменателем, лучший алгоритм потребует большей длины блока, чем 2. Вы можете использовать аргумент существования в стиле Шеннона, чтобы показать, что для данного смещения существует процедура, которая является оптимальной, так как Вы хотите, но длина блока может быть очень большой.
Перес в своей статье « Итерация процедуры фон Неймана для извлечения случайных битов» доказывает, что версия алгоритма фон Неймана может подходить к пределу Шеннона произвольно хорошо. Большая часть работы в этой области, похоже, была проделана теоретиками и статистиками, поэтому я не могу представить ни одного документа с теоретико-сложным уклоном, который бы дал вам прямой ответ на ваш вопрос.
Существует забавная проблема, которая требует обратного: если у вас есть источник достоверных битов, как вы эффективно генерируете равномерное распределение по некоторому набору не-степени-двух? Ограниченная итерациями версия проблемы, схожая с вашим вопросом, просит максимизировать энтропию (т.е. сделать распределение как можно более равномерным) с n бросками честной монеты.
источник
Я предпочитаю думать об этом вопросе в следующей обобщенной форме: у нас есть полное двоичное дерево высоты n, где каждому узлу присваивается число, а сумма чисел равна 1. Можем ли мы разделить листья на два множества, где суммы номера их близки?
РЕДАКТИРОВАТЬ "Это в основном проблема кодирования Шеннона." (Спасибо Per Vognsen.) Конец редактирования
(Этот ответ может содержать ошибки, я не проверил детали.)
источник
Вы также можете получить много случайных битов из смещенных монет, см. Статью Габизона «Дерандомизированные алгоритмы» в разделе «Распределение продуктов» (http://sites.google.com/site/arielgabizon1/).
источник
Связанный вопрос, другой сайт: отбеливание случайной битовой последовательности
источник
Если вы хотите, чтобы четное число подбрасываний монет было беспристрастным по отношению к предвзятым монетам, простой способ убрать смещение - это обратный результат каждого другого броска.
источник