Александр Шень: как поймать жулика с помощью вычислимых мартингалов

Лекция Александра Шеня, 4/08/2022, о решении следующей задачи, предложенной Гилем Калаем: “Рон и Рут создают случайное блуждание по целым числам следующим образом. Они начинают оба на числе ноль. Потом Рон разыгрывает случайно 1 или -1, и они оба двигаются в этом направлении; потом Рут делает то же самое, потом опять Рон и так далее. Таким образом, они все время двигаются вместе, но поочередно отвечают за выбор шага. Из теории случайных процессов известно, что такое случайное блуждание должно возвращаться в 0 бесконечное число раз. Но когда мы посмотрели на (бесконечную) запись всего блуждания Рона с Рут, то увидели, что на самом деле они ни разу не вернулись в 0 после первого шага. Вывод: один из них жульничал, т.е. делал вид, что случайно разыгрывает шаг, а на самом деле говорил не случайные числа. Внимание, вопрос: если ровно один из них жульничал, можем ли мы определить, изучая запись шагов, кто жульничал, Рон или Рут? Что вам говорит ваша интуиция (можем или не можем определить