Чита, Нита и Дракон

[slavav]

waxtep, проверьте меня, пожалуйста.

148 побед на этой диаграмме (а значит 178 на полной):

        1 0 1 0 1 0   1 0   1 0 1 0 1 0
        0 1 1 0 0 1   1 0   0 1 1 0 0 1
        0 0 0 1 1 1   1 0   0 0 0 1 1 1
        0 0 0 0 0 0   0 1   1 1 1 1 1 1
                                       
        0 2 0 1 1 2   0 3   0 2 0 1 1 2
                                       
1000 0  X X X X - X   X X   X X X X - X
0100 2  X X X X X -   - X   X X X X X -
1100 0  X X X - X X   X X   X X X - X X
0010 1  X X - X X X   - X   X X - X X X
1010 1  - X X X X X   X X   - X X X X X
0110 2  X - X X X X   - X   X - X X X X
                            
1110 0  X - X - X -   X X   X - X - X -
0001 3  X X X X X X   X X   - - - - - -
                            
1001 0  X X X X - X   X -   X X X X - X
0101 2  X X X X X -   - -   X X X X X -
1101 0  X X X - X X   X -   X X X - X X
0011 1  X X - X X X   - -   X X - X X X
1011 1  - X X X X X   X -   - X X X X X
0111 2  X - X X X X   - -   X - X X X X

waxtep, термин симметричная вы понимаете правильно. Я боюсь это уведёт нас в сторону, но вы упомянули двойственную задачу: найти стратегию с минимальным числом совпадений. Я думаю что это более сложная задача. Например: для "максимальной" задачи всегда находились симметричные решения, для "минимальной" это не так.

[waxtep]

slavav в сообщении #1376574 писал(а):

148 побед на этой диаграмме (а значит 178 на полной):

Ах елочки зелёные, ну конечно! Задача для $n+1$ монет это четыре задачи для $n$ монет, плюс небольшой хвостик. Чуть-чуть до этого своим умом не дошел И понятно, почему у нас ответы расходятся - я перечисляю выборы для лексикографически упорядоченных исходов, а Вы их группируете

-- 17.02.2019, 15:38 --

waxtep в сообщении #1376608 писал(а):

а Вы их группируете

Точнее, порядок разрядов используете противоположный; в общем, чтобы перейти от Ваших обозначений к моим (нумерация с единицы и начинаем с $0001$, а не с $1000$), надо вычесть номер броска из четырех (в общем случае из $n$). В моих обозначениях симметричная стратегия тогда действительно будет $(4,2,4,3,3,2,4,1,4,2,4,3,3,2)$

[waxtep]

Угу. То есть, получается, существуют стратегии, обеспечивающие для числа спасительных исходов $S_n$ при $n$ бросков у каждой стороны следующее:

$$\begin{cases} S_{2m}=4S_{2m-1}+2\\ S_{2m+1}=4S_{2m}+4\\ S_1=2 \end{cases}$$

Предел вероятности спасения у такой штуки действительно $0.7$

[wrest]

waxtep в сообщении #1376641 писал(а):

Предел вероятности спасения у такой штуки действительно $0.7$

То есть это все-таки оценка снизу (при бесконечном количестве бросков существует стратегия с вероятностью победы не менее $0,7$), или есть какие-то соображения, по которым лучших стратегий (на большом количестве бросков) не существует?

[slavav]

Замкнутые формулы для конечных стратегий:
$N_k = \frac{7\cdot4^k - 2 (-1)^k}{10} - 1$,
$D_k = 4^k$,
$\varepsilon_k = \frac{5 + (-1)^k}{5\cdot4^k}$.
$\varepsilon_k = \frac{7}{10} - \frac{N_k}{D_k}$.

Идея была следующая: построить последовательность конечных стратегий с этими свойствами. Предположим что найдется $s_k$ с вероятностью больше $\frac{N_k}{D_k}$, тогда из неё можно построить стратегию $s_{k-1}$ с вероятностью больше $\frac{N_{k-1}}{D_{k-1}}$ (это ещё надо придумать как). По индукции придти к противоречию.

[waxtep]

slavav в сообщении #1376574 писал(а):

Я боюсь это уведёт нас в сторону, но вы упомянули двойственную задачу: найти стратегию с минимальным числом совпадений. Я думаю что это более сложная задача. Например: для "максимальной" задачи всегда находились симметричные решения, для "минимальной" это не так.

Но для двойственной задачи ("xor-дракона", когда принцессы должны выбрать разные исходы их бросков, чтобы спастись), похоже, тот же предел для вероятности; по крайней мере, для $n=2,3,4$ это так. Вычислительная трудность для несимметричных стратегий растет с $n\cdot2^{3n}$ до $n^2\cdot2^{4n}$, для маленьких $n$ все еще обозримо; хочу попробовать, ну, наверное, уже ближе к следующим выходным.

wrest в сообщении #1376644 писал(а):

То есть это все-таки оценка снизу

Нет, я имел в виду, что, скорее всего, это наилучшие стратегии, правда, доказывать, как выше предлагает slavav не пытался, ограничился наглядными соображениями "вот четыре блока для задачи меньшего размера, вот внешний контур, вот "крест" посередине"...

-- 18.02.2019, 01:12 --

(эксельное баловство с картинкой )

Симметричная стратегия для $n=4$:



Из правого нижнего угла подбирается дракон, косичка одной из принцесс уже в его пасти; голова другой принцессы (с косичкой) - в левой части картинки

[waxtep]

waxtep в сообщении #1376781 писал(а):

Вычислительная трудность для несимметричных стратегий растет с $n\cdot2^{3n}$ до $n^2\cdot2^{4n}$, для маленьких $n$ все еще обозримо;

Это я конечно очень погорячился, правильно $n^{2^n}\cdot2^{2n}\rightarrow n^{2\cdot2^n}\cdot2^{2n}$. "Столько ему не съесть", это же рост с $10^{236}$ до $10^{467}$ для $n=8$, как это можно полностью перебрать даже для симметричной задачи?!

[wrest]

То есть, все-таки, доказательства что предел вероятности победы при оптимальной стратегии равен $0,7$, вот именно доказательства -- нет?

[slavav]

wrest в сообщении #1377478 писал(а):

То есть, все-таки, доказательства что предел вероятности победы при оптимальной стратегии равен $0,7$, вот именно доказательства -- нет?

Такого доказательства нет. Как только оно появится, задача будет решена полностью.

-- 21.02.2019, 11:14 --

mihaild в обсуждении на OpenDataScience предъявил бесконечную симметричную стратегию с вероятностью $\frac{7}{10}$:

Цитата:

Бьем последовательность на тройки.
Выбираем первую тройку, в которой не все результаты одинаковые.
Называем число "начальная позиция тройки" + `{'HHT': 1, 'HTH': 2, 'HTT': 2, 'THH': 0, 'THT': 1, 'TTH': 0}`
Если у обеих принцесс номер выбранной тройки совпадает - то вероятность победы $\frac{5}{6}$, иначе - $\frac{1}{2}$.
Вероятность того, что номера выбранных троек совпадают - $\frac{3}{5}$.
Итого вероятность победы $0.7$

[KrimsN]

Стратегию для 4 бросков монеты ( 2 на каждую принцессу) я понял, а вот какая должна быть стратегия для 6, 8, 10...
Для 2 стратегия такая, если у одного выпадают О,О или О,Р то он выбирает номер первого броска в последовательности второго ( если у него чёт - то 1, если нечёт то 2), а если Р,Р или Р,О - то номер второго.
Когда у нас всего 6 бросков( по 3 на принцессу), то вариантов выпадения у каждого по 8, как мы должны их распределить? Так же на 2 варианта ( 1 или 2) или на 3?

З.Ы. И есть ли смысл, если задача найти стратегию, при которой шанс победы больше 0.5, для этого достаточно смотреть только на первые 4 броска. ( Да далее шанс победы выше, но задача же решена)

[mihaild]

KrimsN в сообщении #1436942 писал(а):

Так же на 2 варианта ( 1 или 2) или на 3?

На три. Чуть выше есть конкретный пример как это сделать.

KrimsN в сообщении #1436942 писал(а):

если задача найти стратегию, при которой шанс победы больше 0.5

Кто вам это сказал? Задача - максимизировать вероятность победы. И пока что очень похоже на то что для этого нужна вся бесконечная последовательность (если оптимальная вероятность $0.7$, а на это похоже, то точно конечного числа бросков не хватит).