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