Выношу из комментов:
rvn
А расскажи еще, пожалуйста, где добыть монетку, которая с вероятностью f(x) падает орлом? :)
vvv
Это же тоже хорошая задача
Как из симметричной монетки получить несимметричную
Даже можно добавить какое-то требование, что в среднем понадобится не более двух бросков симметричной монетки
Формализация задачи:
У вас есть честная монетка (выпадает орлом или решкой с вероятностью ровно 1/2). Дано число p, 0 < p < 1. Придумайте процедуру, которая позволяет имитировать нечестную монетку, которая выпадает орлом с вероятностью p. Дополнительное требование: матожидание числа бросков честной монетки согласно этой процедуре должно быть не больше 2.
Решение в комментах под спойлером.
Давайте сначала научимся с помощью честной монетки генерировать число x, равномерно распределенное на [0, 1], за бесконечно много бросков. Для этого будем производить бинарный поиск этого самого x, отвечая на вопросы "больше или меньше" с помощью монетки. То есть, допустим, первый вопрос: х больше 1/2? Монетка выпала орлом, ответ "нет". Второй вопрос: x больше 1/4? Монетка выпала решкой, ответ "да". Третий вопрос: x больше 3/8? И так далее.
Наша процедура заключается в том, что мы делаем именно это, но если мы после какого-то количества вопросов уже знаем, что x > p, или что x < p, то мы ее прекращаем и возвращаем соответствующий ответ симулируемой нами "нечестной монетки".
Давайте прикинем, сколько нам в среднем нужно будет бросков. Перед n-тым броском мы знаем, что x находится где-то на отрезке длины 1/2n-1. На этом же отрезке также находится и p (в противном случае мы уже закончили процедуру). С вероятностью 1/2 на n-том броске мы попадаем в ту же половину, где находится p, а с вероятностью 1/2 в другую и можем остановиться. Итого вероятность выдать ответ равна 1/2 на каждом броске. Значит, матожидание числа бросков равно 1 + 1/2 + (1/2)2 + (1/2)3 + ... = 2.
ответить
