Comments 12
Асимметричная монетка выпадает орлом с вероятностью
и решкой с вероятностью
. Как двум людям вытянуть честный жребий с её помощью?
Вариант избыточный, но зато без расчета - можно бросить монетку 6 раз, 3 раза из которых орел трактуется в пользу первого участника, а 3 раза - в пользу второго. Кто получил больше орлов - тот и побеждает. Если равное количество - бросаем еще 2 раза....
Подозреваю, что можно и за меньшее количество бросков?
Как послематчевые пенальти
Соревновательная модель получается, если я не ошибаюсь. Чем больше асимметрия, тем больше ходов.
Я думал об устранении асимметричности путём удаления k вхождений результатов с большей вероятностью. Пусть p=2/3, а q=1/3. Кидаем монетку три раза и удаляем одного орла, если он есть. Считаем процентное соотношение. У кого больше, тот и победил.
Еще проще - каждый кидает по 1 разу. Если выпало одинаково - перекидываем, если разное - у кого орел тот и победил.
Но задача видимо в том как сделать за еще меньшее число.
Ну и да, если p=0.99 то ходов даже с оптимальным алгоритмом потребуется много, ведь если все время выпадает орел он никакой полезной информации не приносит.
Еще проще - каждый кидает по 1 разу. Если выпало одинаково - перекидываем, если разное - у кого орел тот и победил.
Да, это хороший базовый алгоритм, от которого стоит отталкиваться
Ну а для оптимального алгоритма, я так понимаю, надо использовать тот же метод что и в статье (записать двоичное число и при отклонении от него вверх считать что победил первый, а отклонении вниз - второй), только система записи будет не двоичная а "действительнозначная" - первый разряд = 1 если текущий остаток больше p (примем что p >= 0.5), второй разряд = 1 если текущий остаток больще p*p и т.д.
Подбираем такую последовательность бросков, чтобы вероятность была 1/2. Например, если p = 2/3, q = 1/3, то первые 2 броска будет орел (2/3*2/3 < 1/2), далее решка.
В целом надо будет бросать первую серию в k орлов , где k - первое целое, при котором p^k < 1/2, потом решка и опять серия орлов. Общей формулы по типу записи в системе исчисления не могу что-то придумать.
Imho в этой статье была бы уместной отсылка к арифметическому кодированию – задачи очень пересекаются и алгоритм по сути общий (единственное – в арифметическом кодировании он повторяется раз за разом).
Для асимметричной монеты есть еще такой паззл: надо бросить честный жребий на 5 чел., но мы имеем право на старте выбрать и зафиксировать p (и q = 1 - p) по своему разумению. Придумать это самое "p" и алгоритм, чтобы гарантировать результат не более чем за N бросков (чем меньше N, тем лучше, знаю решение за N=5)
Жребий брошен: оптимальная генерация распределений и алгоритм Кнута-Яо