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

Question

Как построить случайный источник, который выводит биты 0 и 1 с $ prob (0) = prob (1) = 0,5 $. У нас есть доступ к другому случайному источнику $ s $, который выводит $ a $ или $ b $ с независимыми вероятностями $ prob (a) $ и $ prob (b) = 1 - prob (a) $, которые нам неизвестны.

Как мне указать алгоритм, который выполняет задание и не потребляет больше, чем ожидаемое число $ (prob (a) cdot prob (b))^{-1} $ символов $ s $ между двумя выходными битами и доказать его корректность?

Answer 1

Подумайте об этом: получите два элемента $ x_0 $ и $ x_1 $ от $ s $. Если $ x_0x_1 $ - это $ aa $ или $ bb $, отбросьте их и повторите. В противном случае вернуть $ 0 $ за $ ab $ и $ 1 $ за $ ba $, события, которые происходят с той же вероятностью $ p_ap_b $.

Это будет использовать $ 2N $ Elements от $ S $, $ N $ Количество выполненных шагов. Вероятность остановки на каждом шаге равен $ p = 1-2p_ap_b $. Ожидаемое значение $ 2n $ составляет $$ 2p sum_ {n = 1}^∞ {n (1-p)^{n-1}} = frac {2p} {(1- (1-p) )^2} = frac {1} {p_ap_b} enspace. $$