Произвольный генератор случайных чисел с использованием предубежденного

Question

У вас есть генератор случайных чисел с предвзятым отношением, который дает вероятность с вероятностью p и 0 с вероятностью (1-p). Вы не знаете значения p. Используя это, создайте непредвзятый генератор случайных чисел, который дает 1 с вероятностью 0,5 и 0 с вероятностью 0,5.

Примечание: эта проблема является проблемой упражнения из Введение в алгоритмы по Cormen, Leiserson, Ривестом, Штейн (CLRS)

Answer 1

события (р) (1-р) и (1-р). (p) равновероятны. Принимая их как 0 и 1 соответственно и отбрасывая две другие пары результатов, вы получаете непредвзятый случайный генератор.

В коде это делается так же просто, как:

int UnbiasedRandom() 
{ 
    int x, y; 

    do 
    { 
     x = BiasedRandom(); 
     y = BiasedRandom(); 
    } while (x == y); 

    return x; 
} 

Answer 2

Вы должны нарисовать пары значений из ГСЧ, пока вы не получите последовательность различных значений, то есть ноль, затем один или один с последующим нуль. Затем вы принимаете первое значение (или последнее, не имеет значения) этой последовательности. (т. е. повторять до тех пор, пока нарисованная пара будет либо двумя нулями, либо двумя)

Математика позади этого проста: последовательность 0, затем 1 имеет ту же самую вероятность, что и последовательность 1, затем нуль. Всегда беря первый (или последний) элемент этой последовательности в качестве вывода вашего нового RNG, мы получаем шанс получить нуль или один.

Answer 3

Вот один из способов, возможно, не самый эффективный. Пробудите кучу случайных чисел, пока не получите последовательность формы [0 ..., 1, 0 ..., 1] (где 0 ... - одно или несколько 0s). Подсчитайте число 0s. Если первая последовательность длиннее, сгенерируйте 0, если вторая последовательность длиннее, сгенерируйте 1. (Если они совпадают, попробуйте еще раз.)

Это похоже на то, что HotBits делает для генерации случайных чисел из радиоактивных Распад частиц:

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

HotBits: How It Works

Answer 4

Трюк приписываемые фон Нейман получение двух бит в то время, имея 01 соответствует 0 и 10 до 1, и повторение для 00 или 11 уже появилось. Ожидаемое значение бит, которое нужно извлечь для получения одного бита с использованием этого метода, равно 1/p(1-p), которое может быть довольно большим, если p особенно мало или крупно, поэтому стоит спросить, может ли этот метод быть улучшен, тем более, что он очевидно, что он отбрасывает много информации (все 00 и 11 случаев).

Похоже на то, что у вас возникли проблемы с «von neumann trick biased» this paper, который разрабатывает лучшее решение проблемы. Идея состоит в том, что вы по-прежнему принимаете биты по два за раз, но если первые две попытки производят только 00 и 11, вы обрабатываете пару 0s как один 0 и пару 1s как единый 1 и применяете трюк фон Неймана к этим парам. И если это не работает, продолжайте комбинировать аналогично на этом уровне пар и так далее.

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

Answer 5

Процедура для produce an unbiased coin from a biased one была сначала отнесена к Von Neumann (парень, который сделал огромную работу в математике и многих связанных областях). Процедура очень проста:

• Бросьте монету дважды.
• Если результаты совпадают, начните с забвения обоих результатов.
• Если результаты отличаются, используйте первый результат, забыв о втором.

Причина этот алгоритм работает потому, что вероятность получения HT является p(1-p), который так же, как получение TH (1-p)p. Таким образом, два события одинаково вероятны.

Я также читаю эту книгу и спрашивает ожидаемое время работы. Вероятность того, что два отказа не равны, равна z = 2*p*(1-p), поэтому ожидаемое время работы 1/z.

---

предыдущий пример выглядит поощрение (в конце концов, если у вас есть предвзятое монету с уклоном p=0.99, вам нужно будет бросать монетку примерно в 50 раз, что не так много). Таким образом, вы можете подумать, что это оптимальный алгоритм. К сожалению, это не так.

Вот так оно сравнивается с Shannon's theoretical bound (взято из этого answer). Это показывает, что алгоритм хорош, но далеко не оптимален.

Вы можете прийти с улучшением, если вы будете считать, что HHTT будет отброшен по этому алгоритму, но на самом деле она имеет ту же вероятность, как TTHH. Таким образом, вы также можете остановиться здесь и вернуть H. То же самое с HHHHTTTT и так далее. Использование этих случаев улучшает ожидаемое время работы, но не делает его теоретически оптимальным.

---

И в конце концов - код Python:

import random 

def biased(p): 
    # create a biased coin 
    return 1 if random.random() < p else 0 

def unbiased_from_biased(p): 
    n1, n2 = biased(p), biased(p) 
    while n1 == n2: 
     n1, n2 = biased(p), biased(p) 

    return n1 

p = random.random() 
print p 

tosses = [unbiased_from_biased(p) for i in xrange(1000)] 
n_1 = sum(tosses) 
n_2 = len(tosses) - n_1 
print n_1, n_2 

Это довольно понятно, а вот пример результата:

0.0973181652114 
505 495 

Как вы видите, тем не менее, мы имели смещение 0.097, мы получили приблизительно такое же число 1 и 0