Несмещенный генератор случайных чисел с помощью смещенного
У Вас есть смещенный генератор случайных чисел, который производит 1 с вероятностью p и 0 с вероятностью (1-p). Вы не знаете значение p. Используя это делают несмещенный генератор случайных чисел, который производит 1 с вероятностью 0.5 и 0 с вероятностью 0.5.
Примечание: этой проблемой является проблема осуществления от Введения до Алгоритмов Cormen, Leiserson, Rivest, Глиняной кружкой. (сбрасывает)
4 ответа
События (p)(1-p) и (1-p)(p) являются равносильными. Принимая их за 0 и 1 соответственно и отбрасывая две другие пары результатов, вы получаете несмещенный генератор случайных чисел.
В коде это сделано так же просто, как:
int UnbiasedRandom()
{
int x, y;
do
{
x = BiasedRandom();
y = BiasedRandom();
} while (x == y);
return x;
}
Необходимо отрисовать из RNG пар значений до тех пор, пока не получится последовательность различных значений, т.е. ноль, за которым следует один или один, за которым следует ноль. Затем вы берете первое значение (или последнее, не имеет значения) этой последовательности. (т.е. повторяйте до тех пор, пока рисуемая пара будет либо двумя нулями, либо двумя)
Математика за этим проста: последовательность 0 и 1 имеет такую же вероятность, что и последовательность 1 и 0. Всегда принимая первый (или последний) элемент этой последовательности за результат вашего нового RNG, мы получаем ровный шанс получить ноль или единицу.
.Вот один способ, вероятно, не самый эффективный. Прогрызайте кучу случайных чисел, пока не получите последовательность формы [0..., 1, 0..., 1] (где 0... - это одна или более 0). Считайте число 0. Если первая последовательность длиннее, сгенерируйте 0, если вторая последовательность длиннее, сгенерируйте 1. (Если они одинаковые, попробуйте еще раз)
Это похоже на то, что HotBits делает для генерации случайных чисел из радиоактивного распада частиц:
Так как время любого заданного распада случайно, то интервал между двумя последовательными распадами также случайен. Тогда мы измеряем пару этих интервалов и излучаем ноль или один бит, исходя из относительной длины этих двух интервалов. Если мы измеряем один и тот же интервал для двух распадов, то отбрасываем измерение и пытаемся снова
Уже появился трюк, приписываемый фон Нейману - получение двух битов одновременно, когда 01 соответствует 0 и 10 к 1, а повторение для 00 или 11. Ожидаемое значение битов, которое необходимо извлечь для получения одного бита этим методом, составляет 1/p(1-p), которое может получиться достаточно большим, если p особенно малым или большим, поэтому стоит спросить, можно ли улучшить этот метод, тем более, что очевидно, что он отбрасывает много информации (все 00 и 11 случаев).
Гуглинг на "von neumann trick biased" дал эту статью , которая развивает лучшее решение проблемы. Идея заключается в том, что вы все еще берут биты по два за раз, но если первые две попытки производят только 00s и 11s, вы относитесь к паре 0s как к одному 0 и паре 1s как к одному 1, и применить трюк фон Неймана к этим парам. И если это тоже не сработает, продолжайте комбинировать аналогичным образом на этом уровне пар, и так далее.
Далее в статье это развивается в генерацию множества несмещённых битов из смещённого источника, по существу используя два различных способа генерации битов из пар битов, и давая эскиз, что это оптимально в том смысле, что генерируется именно то количество битов, которое изначальная последовательность имела в своём составе энтропию.