2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 кооперативная игра со случайными битами
Сообщение30.03.2019, 16:04 
Модератор
Аватара пользователя


11/01/06
5660
Пусть $n$ - фиксированное натуральное число.

Алиса и Боб, не общаясь друг с другом, играют в следующую игру. В каждом раунде ведущий независимо и равномерно генерирует две случайные последовательности $A$ и $B$ длины $n$ из нулей и единиц. Последовательность $A$ показывается Алисе в тайне от Боба, после этого Алиса называет ведущему число $a$, $1\leq a\leq n$. Аналогично, последовательность $B$ показывается Бобу в тайне от Алисы, и он после этого называет ведущему число $b$, $1\leq b\leq n$.
Если оказывается, что $A_b = B_a = 1$, то Алиса и Боб выигрывают раунд; иначе - проигрывают.

Понятно, что если Алиса и Боб всегда называют некоторые фиксированные числа (независимо от увиденных $A$ и $B$), например $a=b=1$, то раунд выигрывается с вероятностью $\frac{1}{4}$.

1) Докажите, что есть стратегия, придерживаясь которой, Алиса и Боб выигрывают с вероятностью $\geq \frac{1}{3}$ (при $n\to\infty$).

2) Какова максимально достижимая вероятность выигрыша в такой игре? (как функция от $n$ или при $n\to\infty$)

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение30.03.2019, 16:19 
Аватара пользователя


07/01/16
1426
Аязьма
Похожа на задачу про Читу и Ниту, там, правда, для выигрыша достаточно $A_b=B_a$

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение30.03.2019, 17:33 
Модератор
Аватара пользователя


11/01/06
5660
waxtep, интересно. Для той игры получена вероятность $0.7$ - напрашивается вопрос: можно ли ту стратегию адаптировать для этой игры, чтобы достичь хотя бы половины от $0.7$, т.е. $0.35$?

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение31.03.2019, 00:02 
Заслуженный участник


26/05/14
981
Не откажу себе в удовольствии воспроизвести стратегию mihaild в применении к вашей задаче. Та стратегия работает для бесконечных последовательностей:

Бьем последовательность на тройки.
Выбираем первую тройку, в которой не все результаты одинаковые.
Называем число "начальная позиция тройки" + {001: 0, 010: 2, 011: 0, 100: 1, 101: 1, 110: 2}.
Если у Алисы и Боба номера выбранных троек совпадают - то вероятность победы $\frac{5}{12}$, иначе - $\frac{1}{4}$.
Вероятность того, что номера выбранных троек совпадают - $\frac{3}{5}$.
Итого вероятность победы $0.35$.

-- 31.03.2019, 00:10 --

maxal, откуда у вас эта задача?

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение31.03.2019, 00:15 
Модератор
Аватара пользователя


11/01/06
5660
slavav, задача отсюда: https://mathoverflow.net/q/326669
Добавьте туда это решение.

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение31.03.2019, 00:49 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
Добавил. Правда аргумента за то, что убирание требования равенства едиинце (из комментариев) я не понимаю. Очевидно что вероятность победы в этой задаче не меньше половины вероятности победы в старой (вероятность победы в старой либо с двумя нулями, либо с двумя единицами, не меньше половины общей; если вероятность победы с двумя нулями больше - инвертируем всё).

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение31.03.2019, 02:12 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
Ладно, если подумать, то всё же понятно:
$$P(A = 1, B = 1) = P(A = 1) - P(A = 1, B = 0) = \frac{1}{2} - (P(B = 0) - P(A = 0, B = 0)) = P(A = 0, B = 0)$$.

 Профиль  
                  
 
 Re: кооперативная игра со случайными битами
Сообщение31.03.2019, 23:32 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
Если $q_i^j$ - вероятность "назвали $i$, в $j$-м бите единица" (т.е. $i$-я строка матрицы $Q$ получается делением на $2^n$ суммы всех исходов, при которых мы называем $i$), то вероятность победы равна $\operatorname{tr} Q^2$. Правда ограничения на $Q$, чтобы по ней можно было получить какой-то профиль стратегий, очень некрасивые получаются (для любого набора из $k$ колонок сумма минимумов значения в этих колонках по всем строкам не меньше чем $2^{-k}$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group