• 

еще раз о роне и рут

На тему задачи о жулике при случайном блуждании.

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

https://www.youtube.com/embed/aYBTlcxa31M


Дальше идет очень краткий пересказ основных идей решения, его написал я, если что-то непонятно, смотрите видео.

Главная идея, которая нам нужна, называется "вычислимый мартингал". Представьте себе, что вам дают по одному числу бесконечную строку из -1 и +1, напр. это самое случайное блуждание, а вы пытаетесь на основе уже увиденных чисел предсказать, каким будет следующее. У вас есть начальный бюджет, скажем один доллар, и вы решаете сначала, сколько из него поставить на то, что первое число +1, а сколько -1; обратно вы получаете удвоенную ставку. Скажем, если вы уверены на 90%, что первым числом будет +1, то поставьте 90 центов на +1, и 10 центов на -1. Если вы правы, то обратно получите 1.80, если нет - 0.20. Теперь все, что у вас есть, ставьте на следующее число: часть на +1, остальное на -1, и так далее. После N чисел у вас на руках есть какие-то деньги, причем легко видеть, что средним значением по всем возможным 2^N строкам остается $1, но если вы например точно знали, какие числа будут выпадать, то могли всегда ставить правильно и заработать экспоненциально много денег.

Так вот, "вычислимый мартингал" это просто алгоритм, который на каждую конечную строку дает разброс, как вы собираетесь ставить, если вот это уже выпало, и сейчас решать, -1 или +1. Теперь если у вас в руках есть такой алгоритм, и вам дают бесконечную строку, можно посмотреть, сколько денег вы на ней будете делать. Если ваши деньги растут неограниченно, то назовем такую строку НЕСЛУЧАЙНОЙ. Скажем, строка "двоичное разложение числа пи" неслучайна, очень легко на ней делать деньги. А вот строка, полученная броском честной монеты, явно случайна - можно доказать, что вероятность того, что найдется для нее вычислимый мартингал, дающий неограниченную прибыль, равна 0.

Идея решения в том, что вопрос о "случайности" строк Рона, Рут или совместного их блуждания мы переводим на язык мартингалов. Мы знаем, что блуждание Рона и Рут никогда не возвращается в 0. Оказывается, этого факта достаточно, чтобы показать, что на их бесконечной строке можно "делать деньги"; это потому, что доля таких строк длиной N, которые не возвращаются в 0, среди всех строк длиной N, все время уменьшается и стремится к 0. Мы можем построить выигрышный мартингал, использующий это: скажем, если взять достаточно длинный префикс, так, чтобы доля невозвращающихся в 0 строк в нем была меньше 1/64, то на этом префиксе можно увеличить свою прибыль в 64 раза (мы знаем, что наша строка одна из малого числа всех возможных, и "направляем" наши ставки только на такие строки). Выигрышный мартингал может последовательно увеличивать капитал игрока в 2,4,8,16 и так далее раз, рассматривая все более длинные префиксы блуждания. Подробности см. в видео.

Теперь у нас на руках есть конкретный алгоритм (пусть довольно сложный и абстрактный), который использует неслучайность блуждания в финансовых целях, и генерирует неограниченную прибыль. Если мы разобьем этот алгоритм на два, один, который делает то же, что исходный, на четных шагах, а на нечетных ставит поровну 0.5/0.5, и другой наоборот, то эти два мартингала соответствуют попыткам нажиться только на шагах Рона или только на шагах Рут. Меж тем прибыль исходного мартингала, как легко видеть, равна произведению прибыли этих двух, поэтому один из них тоже обязан давать неограниченную прибыль. Он-то и соответствует игроку-жулику. (как сказано выше, если бы этот игрок бросал чистую монету, вероятность существования такого мартингала на шагах только этого игрока была бы 0).


Не супер наглядно, но красиво и очень интересно. Более подробные обсуждения как технических, так и философских вопросов ("что именно мы доказали?", "в каком смысле это можно проверить?", "как интуитивно объяснить, как именно выдает себя жулик?" итд.) есть в видео.

Другие популярные посты

 • 

Те, кто отдаёт свою жизнь чужим детям.Не за зарплату, а по велению души и сердца.

3 комментария Источник

 • 

"На полотне у реки Исакогорка (588-я верста) несколько паровозов с землекопалками за ночь засосало в болото вместе с построенной дамбой. ...

1 комментарий Источник

9