Зачем все это нужно если достаточно заметить что первый ход у обоих участников одинаковый?

При двух честных игроках первый ход будет одинаков в половине случаев.

В казино жуликов без алгоритмов вылавливают, причем даже тех кто не жульничал)

Трудно поймать черную кошку в темной комнате, особенно если ее там нет.

Верно ли я поняла, что речь идет об алгоритме, который по наблюденным N отсчетам (а не бесконечной последовательности) дает возможность угадать следующий ход с вероятностью больше 1/2 ?
Речь идет о наблюдении одной игры или многих ?

Этот алгоритм показан в лекции ?

Давайте я сформулирую утверждение почти строго и дам некоторые определения.

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

Префикс бесконечной последовательности x1x2x3... это конечное слово x1x2...xn (без пропусков!) для некоторого n. (Вероятностная) мера m сопоставляет каждому конечному слову некоторое неотрицательное число, так что (A) m от пустого слова равно 1 и (B) m(x) = m(x0) + m(x1) для любого конечного слова x. Равномерная мера равна 2^{-n} на словах длины n. Отношение меры m к равномерной (то есть m(x)*2^{длина x}) называется мартингалом относительно равномерной меры.

Мера вычислима, если существует алгоритм, который по x и требуемому числу знаков выдаёт приближение к m(x) с заданным числом знаков.

Те меры m1 и m2, существование которых утверждается выше (и в посте очень кратко описано, как их строить), соответствуют игрокам в следующем смысле: m1(x0)=m1(x1)=0.5m1(x) для x нечётной длины, и то же для m2 и чётной длины. В терминах мартингалов, мы не ставим на чётных / нечётных шагах, так что отношение меры к равномерной не изменяется. Жульничал тот игрок, для которого отношение "его" меры к равномерной стремится к бесконечности.

Сейчас буду смотреть лекцию, потому что по описанию остался вопрос.
Если мы делаем ставки постфактум, зная все ходы Рона, то мы можем не угадывать, а играть наверняка.
А если мы делаем ставки, не зная ходы Рона, в процессе игры, то мы и не можем опираться на то, что ноль никогда не будет встречен. Ведь жульническая стратегия Рона может давать результат, скажем, пересечения 0 с вероятностью 1/2, а бесконечное количество пересечений 0 с вероятностью 1/4, и во время игры ни мы, ни жулик-Рон не знаем, встретится ли ноль.
Насколько корректно оставить этот один факт, но не оставлять информацию об отдельных ходах?

Пока писал коммент, кажется, понял.
Суть не в том, что для любой бесконечной последовательности, не проходящей через ноль, существует вычислимый мартингал, дающий неограниченную прибыль, а в том, что существует вычислимый мартингал, который для любой бесконечной последовательности, не пересекающей ноль, даёт неограниченный выигрыш. Я прав?

Осталось понять, почему, если сама случайная последовательность неограничена, для любого выичлимого мартингала (например, всегда ставящего половину на +1 и половину на -1) выигрыш будет ограничен. Может быть, под неограниченным выигрышем понимается что-то другое — например, что выигрыш стремится к бесконечности?

Если мы делаем ставки постфактум, зная все ходы Рона, то мы можем не угадывать, а играть наверняка.
Вот и я — о том же.

Спасибо Александру и вам. Очень интересно. Если я всё правильно понял, то мне кажется, возможно не все нарушения случайности могут быть обнаружены этим мартингальным методом. Например, если жулик будет бороться против какого-нибудь “асимптотического” свойства бесконечной последовательности орлов-решек.

Конкретный пример. Известно, что длина самой длинной серии (подряд) орлов в последовательности длины N приблизительно log(N) (для любопытных: http://www.csun.edu/~hcmth031/tlroh.pdf ). Представьте, что жулик озабочен только этим, и следит, чтоб в асимптотике было log(N)^.5 (или еще хуже: все что угодно, но не log (N)). Элементарно вставляя время от времени решку в длинные серии орлов. В чем проблема? Ломается красивая “эпсилон лемма”. Для конечных последовательностей орлов решек мы четко видим, где мы вернулись в ноль, а где -- нет. Для асимптотических свойств этой определенности – нет.

Хотя это не означает, что такие отклонения от случайности не определяются вычислимыми мартингалами в принципе. В качестве множества S (из леммы), наверное, можно взять множество последовательностей длины N, где длина самой длинной серии орлов короче ожидаемой (приблизительно log (N)) на, скажем, log(log(N)) (см. опять же: http://www.csun.edu/~hcmth031/tlroh.pdf). Но деталей, через которые надо продраться, становится слишком много.

Edited at 2022-08-08 14:44 (UTC)

По моему его рассуждения будут работать, даже если последовательность будет проходить через ноль, но статистически реже чем случайная. Таких последовательностей тоже гораздо меньше чем настоящих случайных и т.д. Это похоже на ваше асимптотическое свойство.

Спасибо, очень интересно. Интересно можно ли методами анализа без мартингалов понять, кто жулик. Действительно ясно, что lim inf S_n=infty , но дальше непонятно что делать.

Из лекции не вполне понятно, почему конечный алгоритм (не зависящий от числа шагов n) может вычислять распределение вероятностней выигрыша для любой глубины n. И еще вопрос А. Шеню: любое ли свойство меры нуль вычислимо конечным алгоритмом?

Он не совсем конечный: "Выигрышный мартингал может последовательно увеличивать капитал игрока в 2,4,8,16 и так далее раз, рассматривая все более длинные префиксы блуждания."

1 2 2
2 2 4
3 4 8
4 6 16
5 12 32
6 20 64
7 40 128
8 70 256
9 140 512
10 252 1024
11 504 2048
12 924 4096
13 1848 8192
14 3432 16384
15 6864 32768
16 12870 65536
17 25740 131072
18 48620 262144
19 97240 524288
20 184756 1048576

Выше число ненулевых цепочек на каждый ход до 20. Также для подсчета вероятности указано их общее число.

Как мы видим, вероятность изменяется только на четном шаге, на нечетном она такая же.

Видим уменьшение её. Ну вот хотелось бы теперь на конкретных числах увидеть пример, как применяются описанные выше рассуждения.

UPD. Я прослушал лекцию, мне всё понравилось, но как всегда с применением возникают проблемы.
1) За счет чего мы можем вообще как-то ставить на то, что первый жулик, у нас нет информации чтобы ловить его. Поскольку все возвраты в ноль на четных ходах и только там мы можем ставить с выигрышем.

2)Ну вот на 20 итерации 184756, я поставлю на каждую мой выигрыш X. Тогда мой выигрыш 2/184756 X, да это больше, чем 2/1048576 X, но я всё равно продувая, что будет дальше, ведь число цепочек будет небольшим по сравнению с общим числом, но тоже будет стремиться к бесконечности

Edited at 2022-08-09 10:58 (UTC)

Рискну высказать утверждение, что приведённое решение неверно или, как минимум, существенно не полно.

Причина — именно отличие между неограниченным и бесконечным выигрышем. Для последовательности, не проходящей через ноль, существует мартингал, дающий бесконечный выигрыш, но если разложить его на два мартингала, делающих нейтральный выбор для чётных и для нечётных ходов, то каждый из них может давать неограниченный, но не бесконечный выигрыш, и найти читера не получится.

Более конкретно. Рассмотрим алгоритм (мартингал), который для координаты N делает ставку 1/2+1/4N на увеличение и, соответственно, 1/2-1/4N на уменьшение. Иными словами, при увеличении получается выигрыш 1/2N, при уменьшении проигрыш 1/2N. Если мы сходили на +1 вправо и вернулись обратно, то мы выигрыли 1/2N и потом проиграли (1+1/2N)/2(N+1) = (2N+1)/4N(N+1), т.е. выиграли больше, чем проиграли, остались в плюсе (этот проигрыш легко сравнить с выигрышем 1/2N: после умножения на 2N получится (2N+1)/(2N+2), что меньше единицы).
Можно увидеть, что для любого участка, который заканчивается там же, где начинается, и не пересекает точку старта, такой мартингал тоже даёт выигрыш, причём не меньше, чем для случая, когда сделали один ход вправо и вернулись, разложив его на более элементарные участки с монотонным увеличнием и потом монотонным спуском.
Всю бесконечную последовательность, не проходящую через ноль, можно разложить на участки, которые возвращаются в исходную точку, являющуюся при этом минимумом для этого участка (т.е., начинается с k, потом возвращается в k, и нигде посередине не принимает значения меньше k), и монотонно возрастающие участки. Если монотонно возрастающие участки составляют бесконечную последовательность, то вся наша исходная последовательность стремится к бесконечности, и суммарный выигрыш тоже бесконечен (ряд 1/2N расходится, а участки с возвратом не дают уменьшения). Если бесконечного увеличения нет, то поледовательность бесконечно возвращается к какому-то одному числу, и на каждом участке между этими возвращениями сумма выигрыша увеличивается не менее, чем на вполне фиксированную сумму, т.е. выигрыш в этом случае тоже бесконечно растёт.
Это конкретный явный пример вычислимого мартингала, дающего бесконечный выигрыш на любой последовательности, никогда не пересекающей ноль.

Теперь возьмём для примера такую последовательность. Пусть чётные ходы всегда (после первых двух ходов на +1) зеркалят нечётные, т.е. мы всегда остаёмся в точке 2 плюс-минус 1. А нечётные делают 1 ход вправо, потом 2 влево, 4 вправо, 8 влево, 16 вправо и т.д. Каждая такая убывающая серия заставит мартингал A проиграть всё накопленное, в то время как мартингал B получит приличный выигрыш (для него ведь это будет большая возрастающая серия). Но при смене направления произойдёт наоборот: теперь уже B всё проиграет, пока A будет подниматься к новым рубежам. В итоге ни у одного из этих мартингалов выигрыш не будет бесконечным (хотя, конечно, будет неограниченным), несмотря на бесконечный выигрыш их произведения: рост одного будет соответствовать падению другого. А неограниченность выигрыша не даёт нам сделать вывод о неслучайности последовательности.
И получается, что в таком варианте мы таким способом не определим, кто из них жулик.

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

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

Да, это тот тонкий момент, про который я говорил, но который остался неразобранным. Рассуждение в видео приводилось для случая интерпретации случайности как существования неограниченного мартингала. Тогда неограниченность произведения гарантирует неограниченность одного из сомножителей. Для мартингалов, стремящихся к бесконечности, это, вообще говоря, неверно. Однако можно преобразовать вычислимый мартингал так в другой вычислимый мартингал так, чтобы на всех последовательностях, на которых первый не ограничен, второй стремился к бесконечности. Для этого надо разделить капитал на части (бесконечное число положительных частей), и дать на i-й части играть неограниченному мартингалу (с тем капиталом, который ему достанется, пусть и очень малым), пока он не достигнет капитала 1 (например). Тогда вместе они гарантируют стремление к бесконечности.

(Другой вариант — saving trick — надо, когда капитал превосходит 2, откладывать 1 и продолжать игру с оставшимся капиталом — в какой-то момент мы снова достигнем 2 и т.д. )

1. Спустя две недели я понял, что меня смущает в этом решении — я не понимаю, где в нем используется онлайновость.

То есть, если бы задача была такой: сначала генерируется случайная последовательность, а затем жулик, глядя на нее, конструирует свою и выбирает ходить первым или вторым; то кажется очевидным, что если он просто повторит первый ход и отзеркалит остальные, то его не вычислить. В апдейте изначального поста есть слова "и потому соответствующая подпоследовательность не онлайн-случайна", может быть Александр в лекции это объяснил, было бы интересно об этом прочитать.

2. Гил опубликовал статью, где эта задача решается, решение там намного более сложное.

Ссылка на пост https://gilkalai.wordpress.com/2022/08/15/answer-to-test-your-intuition-50-detecting-a-deviator/ (на всякий случай отдельным комментом, вдруг ссылки скринятся).