кооперативная игра со случайными битами

[maxal]

Пусть $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$)

[waxtep]

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

[maxal]

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

[slavav]

Не откажу себе в удовольствии воспроизвести стратегию 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, откуда у вас эта задача?

[maxal]

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

[mihaild]

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

[mihaild]

Ладно, если подумать, то всё же понятно:

$$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)$$

.

[mihaild]

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