Монеты

[Antananarivu]

Два игрока играют в кооперативную игру. В разных комнатах, без сообщения между ними, они бросают честную двустороннюю монетку много раз (можно считать количество бросков бесконечным). После этого игроки одновременно называет порядковый номер броска в последовательности своего партнера. Ни один не знает о том, какой номер назвал другой. Если результаты по этим индексам совпадают, игроки выигрывают. Игра проводится один раз.
1) есть ли стратегия, которая позволит получить вероятность выигрыша больше 0.5?
2) если да, то какова оптимальная стратегия / вероятность выигрыша?

Пример игры:
Игрок A: OОРРРОРОО...
Игрок Б: РООРОООРР...
Игрок A называет номер 8, у игрока В результат 8-го броска - решка
Игрок Б называет номер 4, у игрока A результат 4-го броска - решка
Результат совпадает, поэтому игроки выиграли.

Я знаю, что ответ 2/3, но не могу понять, как здесь можно получить что-то выше, чем 1/2

[mihaild]

Давайте для начала рассмотрим ситуацию с двумя бросками.
Если у одного из игроков выпало два раза одно и то же - то вероятность выигрыша $\frac{1}{2}$ независимо от действий. Итого остаются 4 интересных варианта: (ОР, ОР), (ОР, РО), (РО, ОР), (РО, РО). Можете ли вы придумать какой-то способ, как выиграть больше чем в двух из них?

[grizzly]

Antananarivu
В задаче не хватает важного условия: перед игрой игроки могут согласовать стратегию игры. Без этого больше 1/2 получить нельзя.

[VAL]

Нет никаких сомнений, что идеальная стратегия дает вероятность выигрыша $0.7$, как, впрочем, нет и доказательства этого факта.

Больше информации здесь.

[Antananarivu]

VAL в сообщении #1282478 писал(а):

Нет никаких сомнений, что идеальная стратегия дает вероятность выигрыша $0.7$, как, впрочем, нет и доказательства этого факта.

Больше информации здесь.

Спасибо! Я правильно понимаю, что самой стратегии, чтобы получить эти самые 0,7 для произвольного количества бросков не найдено?

[VAL]

Antananarivu в сообщении #1282483 писал(а):

Спасибо! Я правильно понимаю, что самой стратегии, чтобы получить эти самые 0,7 для произвольного количества бросков не найдено?

В заметке К. Кнопа есть некое приближение к такой стратегии.

[mihaild]

Antananarivu в сообщении #1282483 писал(а):

Я правильно понимаю, что самой стратегии, чтобы получить эти самые 0,7 для произвольного количества бросков не найдено?

Dmitry Lyubarski в комментарии писал(а):

рассмотрим первую тройку битов $(A_k, A_{k+1}, A_{k+2}), k = 2n \geqslant 0$ такую что не все три бита одинаковы, и выдадим ответ из множества $\{k, k+1, k+2\}$ по табличке ABC из статьи

[Antananarivu]

mihaild в сообщении #1282471 писал(а):

Давайте для начала рассмотрим ситуацию с двумя бросками.
Если у одного из игроков выпало два раза одно и то же - то вероятность выигрыша $\frac{1}{2}$ независимо от действий. Итого остаются 4 интересных варианта: (ОР, ОР), (ОР, РО), (РО, ОР), (РО, РО). Можете ли вы придумать какой-то способ, как выиграть больше чем в двух из них?

Спасибо за помощь! Называешь число хода, когда впервые выпал, например, орел и получаешь 100 процентное попадание для этих 4 случаев!)

[worm2]

Вероятность 0.7 получена в чистых стратегиях. Возможно, в смешанных удастся получить ещё большую величину.
(правда, понятие "смешанные стратегии" возникает в играх, когда играют друг против друга, а тут кооперативная игра, но, кажется, это не мешает).

[mihaild]

Пусть у нас есть смешанная стратегия - при данной строчке называть $i$ с вероятностью $p_i$, и она обеспечивает выигрыш с вероятностью $t$. Ее можно переделать в чистую с не меньшей вероятностью выигрыша: для числа $i$ мы выигрываем с вероятностью $x_i$ (вероятность относительно строчки второго игрока). Имеем $t = \sum x_i p_i$. Тогда для какого-то $n$ имеем $x_n \geqslant t$. Будем всегда называть наименьшее такое $n$.
Сделаем такую замену стратегии сначала у одного игрока, потом у другого - получим чистый профиль не хуже изначального смешанного.
(еще может оказаться, что вероятность победы растет с ростом числа, которое мы называем - и в итоге для любой стратегии есть стратегия, дающая лучший результат)

[B@R5uk]

Вот прочитал доказательство про 2/3, но не поверил. Вникать лень, ну, думаю, эксперимент — критерий истины! Написал, попробовал, оказалось и правда 2/3 (в пределах погрешности, разумеется). Всё-таки потрясающая вещь статистика!