пусть велосипед, зато красивый
В ру_мат обсуждают задачку: как, имея генератор случайных битов, равновероятно дающий 0 и 1, построить генератор, дающий 0 с вероятностью Р и 1 с вероятностью 1-Р?
Ну, и чтоб быстро работал, конечно.

Решение. (Наверняка известное, но все равно красивое)

Запишем Р в двоичной системе в виде бесконечной дроби:
Р=0.а1 а2 а3...
Для получения одного бита:
кидаем монетку до тех пор, пока очередной результат х не будет отличаться от очередной цифры ак. Возвращаем х.

(То есть, если на первом шаге совпало с а1, кидаем еще раз, сравниваем с а2 и т.д.)

Работает, даже если Р - двоично-рациональное число, причем все равно как записать Р: с хвостом из нулей или единиц.
Среднее число шагов на один выходной бит легко подсчитать; оно равно 2 для любого Р (для двоично-рационального, за счет очевидной оптимизации, даже меньше 2).


Задачка. Доказать, что быстрее нельзя.

UPD. Не удержался, скопировал в ру_мат.