2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Чита, Нита и Дракон
Сообщение15.02.2019, 13:36 
Заслуженный участник


26/05/14
981
Нечётного числителя в вероятности оптимальной стратегии быть не должно.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение15.02.2019, 13:48 


05/09/16
11469
slavav в сообщении #1376186 писал(а):
Нечётного числителя в вероятности оптимальной стратегии быть не должно.

Но ведь для четырех бросков $\frac{178}{256}=\frac{89}{128}$
Хорошо, а какая вероятность для 5 бросков? Выбор-то небольшой: бОльшие чем $\frac{178}{256}=\frac{712}{1024}$ это: $\frac{713}{1024};\frac{714}{1024};\frac{715}{1024};\frac{716}{1024}$ Следующее уже больше $0,7$

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение15.02.2019, 13:58 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
wrest в сообщении #1376189 писал(а):
Но ведь для четырех бросков $\frac{178}{256}=\frac{89}{128}$
Имелось в виду если в знаменателе $2^{2n}$, где $n$ - число бросков.
slavav в сообщении #1376186 писал(а):
Нечётного числителя в вероятности оптимальной стратегии быть не должно
А почему? Для случая одинаковых стратегий очевидно, для не одинаковых - не понимаю, почему так должно быть.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение15.02.2019, 14:02 
Заслуженный участник


26/05/14
981
Я говорил про симметричную стратегию (то что вы называете одинаковыми стратегиями).

-- 15.02.2019, 14:05 --

Пользователь achikin из ODS:
Цитата:
Да, походу 0.7 пробить не просто (если вообще возможно). Искал генетическими алгоритмами симметричные стратегии для фиксированных последовательностей длины 1-8

Нашел стратегии со следующими вероятностями:
# 1: 0.5
# 2: 0.625
# 3: 0.6875
# 4: 0.6953125
# 5: 0.69921875
# 6: 0.69970703125
# 7: 0.699951171875
# 8: 0.699981689453125

Искать несимметричные стратегии смысла не вижу.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение15.02.2019, 14:14 


05/09/16
11469
slavav в сообщении #1376196 писал(а):
# 5: 0.69921875

Ok, т.е. для 5 бросков выходит $\frac{716}{1024}$
Далее
6 бросков, $\frac{2866}{4096}$
7 бросков, $\frac{11468}{16384}$
8 бросков, $\frac{45874}{65536}$

-- 15.02.2019, 14:40 --

Немножко нумерологии.
Числители в двоичном формате $(2;10;44;178...)$
10
1010
101100
10110010
1011001100
101100110010
10110011001100
1011001100110010

Ну и $0,7_{10}=0,10(1100)_2=0,B(3)_{16}$

Так что стремление к $0,7$ просматривается довольно ясно, как и формулы для вероятности при четном\нечетном количестве бросков.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 00:58 
Аватара пользователя


07/01/16
1426
Аязьма
Я от прогрессивного человечества отстал, пока смог преодолеть только случай трех бросков (вручную, каким-то чудом); стратегия получилась зеркальная:$$\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
case&001&010&011&100&101&110\\
\hline
1st&2&1&2&3&3&1\\
\hline
2nd&1&3&3&2&1&2\\
\hline
\end{tabular}$$То есть, если, например, у Ниты выпало $\texttt{РОР}=010$, то она просит показать первый бросок Читы, а если у Читы выпало столько же, она просит показать третий бросок Ниты и т.д. При этом, совершенно не важно, что просить, если выпало $000$ или $111$, повезет ровно в половине случаев; поэтому эти исходы не показаны. Для этой стратегии принцессы не спасаются строго на анти-диагонали, т.е. когда у одной выпало $010$, а у другой $101$ и т.п. Если бы это так же работало для любого числа бросков $n$ у каждой, то принцессы не спасаются только в $3\cdot2^n-4$ случаях из $2^{2n}$ возможных; что в пределе $n\rightarrow\infty$ дает единичную вероятность спасения. Однако, видимо, численные эксперименты этого не подтверждают....

-- 16.02.2019, 01:07 --

Интересно отметить, что стратегии обеих сторон подходят под правило "не совпадать с $(3,2,1,1,2,3)$ ни в одной позиции"

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 01:45 
Заслуженный участник


26/05/14
981
Шесть найденных полным перебором стратегий. Я нумерую позиции с нуля. Ваши две стратегии в списке есть.
Код:
0 2 0 1 1 2
0 2 2 1 0 1
1 0 0 2 1 2
1 0 1 2 2 0
2 1 1 0 2 0
2 1 2 0 0 1

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 02:15 


14/01/11
2916
waxtep в сообщении #1376357 писал(а):
Интересно отметить, что стратегии обеих сторон подходят под правило "не совпадать с $(3,2,1,1,2,3)$ ни в одной позиции"

А если выбрать обе стратегии $(3,2,1,1,2,3)$, получим ровно половину благоприятных исходов для каждого из раскладов, т.е. вероятность спасения $\frac{1}{2}.$
slavav в сообщении #1376364 писал(а):
Шесть найденных полным перебором стратегий.

Можно заметить, что половина из них представляют собой зеркальные отражения остальных.

-- Сб фев 16, 2019 02:29:51 --

Кроме того, три последовательности, выражающие стратегии в любой из этих половин, получаются друг из друга прибавлением единичек в $Z_3$. :-)
Иными словами, все оптимальные стратегии получаются из одной с помощью небольшого набора простых преобразований.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 08:46 
Аватара пользователя


07/01/16
1426
Аязьма
Sender в сообщении #1376369 писал(а):
А если выбрать обе стратегии $(3,2,1,1,2,3)$, получим ровно половину благоприятных исходов для каждого из раскладов, т.е. вероятность спасения $\frac{1}{2}.$
Точно, я ведь так свой вариант и вымучал: если одна сторона выбирает крайне неудачную стратегию $(3,2,1,1,2,3)$, то второй ее никакими усилиями на достойные шансы спасения не вытянуть. Значит, искать надо "в противоположном углу". Но вот обобщается ли это на случай $n>3$ и как, если да? С учетом того, что для $n=2$, $(1,2)$ (или $(2,1)$) как раз является оптимальной стратегией для обеих сторон

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 10:36 


05/09/16
11469
У меня такой вопрос. Я не понял, является ли условие предварительного сговора принцесс существенным?

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 11:30 


14/01/11
2916
Вообще говоря, да. Несущественным оно может оказаться только в том случае, если индивидуальные оптимальные стратегии принцесс в любом сочетании дадут оптимальную общую стратегию.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 11:52 


05/09/16
11469
Sender
Вопрос в другом: смогут ли принцессы поднять вероятность выше $1/2$ если принцессы умные и разумные, но поговорить перед испытанием им не дали.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 12:38 
Заслуженный участник


26/05/14
981
Sender в сообщении #1376369 писал(а):
Иными словами, все оптимальные стратегии получаются из одной с помощью небольшого набора простых преобразований.

Вы правы. Рассмотрим симметричную стратегию $s$. Она отображает последовательность бит в номер бита. Номер бита закодируем в виде последовательности бит. Все биты нулевые, один бит в указанной позиции единица: $0 \to (1, 0, 0), 1 \to (0, 1, 0), 2 \to (0, 0, 1)$. Далее я буду считать что $s: \left\lbrace0, 1\right\rbrace^3 \to \left\lbrace0, 1\right\rbrace^3$. Рассмотрим любую перестановку $p \in S^3$. Тогда верно что число побед для $s$ равно числу побед для $p^{-1} \circ s \circ p$.
Все шесть ($3!$) оптимальных стратегий для трёх бит получаются друг из друга такими преобразованиями.

Для четырёх бит число оптимальных симметричных стратегий равно $240$. Десять групп по $24 (= 4!)$.

-- 16.02.2019, 12:41 --

wrest в сообщении #1376401 писал(а):
Sender
Вопрос в другом: смогут ли принцессы поднять вероятность выше $1/2$ если принцессы умные и разумные, но поговорить перед испытанием им не дали.

Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат. Принцессам надо договорится перед испытанием.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 20:06 


05/09/16
11469
slavav в сообщении #1376409 писал(а):
Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат. Принцессам надо договорится перед испытанием.

Это ясно, но можно ли все хоть как-то же повысить вероятность не сговариваясь?

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение16.02.2019, 20:37 
Аватара пользователя


07/01/16
1426
Аязьма
slavav в сообщении #1376409 писал(а):
Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат
Там же получается три пары стратегий, если не ошибаюсь, т.е., скажем, Нита может выбрать любую из шести, но, тогда Чита должна выбрать вторую стратегию четко из этой же пары. При этом, одна из пар зеркальная, а две другие - несимметричные. Без сговора, правда, все равно ничего у них не получится

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 101 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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