![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
кто жульничал?
Aug. 4th, 2022 11:42 amИнтересная задача на проверку вероятностной интуиции, от Гила Калая.
Рон и Рут создают случайное блуждание по целым числам следующим образом. Они начинают оба на числе ноль. Потом Рон разыгрывает случайно +1 или -1, и они оба двигаются в этом направлении; потом Рут делает то же самое, потом опять Рон и так далее. Таким образом, они все время двигаются вместе, но поочередно отвечают за выбор шага.
Из теории случайных процессов известно, что такое случайное блуждание должно возвращаться в 0 бесконечное число раз. Но когда мы посмотрели на (бесконечную) запись всего блуждания Рона с Рут, то увидели, что на самом деле они ни разу не вернулись в 0 после первого шага. Вывод: один из них жульничал, т.е. делал вид, что случайно разыгрывает шаг, а на самом деле говорил не случайные числа.
Внимание, вопрос: если ровно один из них жульничал, можем ли мы определить, изучая запись шагов, кто жульничал, Рон или Рут? Что вам говорит ваша интуиция (можем или не можем определить) и можете ли это обосновать?
Update: от А. Шеня в ФБ: "свойство возвращения имеет меру нуль и даже эффективно нулевое по Шнорру, поэтому существует вычислимый мартингал, не ограниченный на последовательности, и раскладывая его в произведение двух мартингалов для двух игроков, убеждаемся, что для одного из игроков (чётного или нечётного) такой мартингал есть - и потому соответствующая подпоследовательность не онлайн-случайна".
Если вы хотите понять, что здесь написано, приходите на импровизированную зум-лекцию А.Шеня сегодня в 7 вечера по Москве, ссылка:
https://us02web.zoom.us/j/83498766491?pwd=cjF4bDgrYnI2NG9pbDVROHFoZ3FIZz09
Meeting ID: 834 9876 6491
Passcode: 921716
Доска:
https://jamboard.google.com/d/1aNepqiZ6glDBNTkN-0IWJPBlRpk0DY9byglih3eHK2U/viewer
Рон и Рут создают случайное блуждание по целым числам следующим образом. Они начинают оба на числе ноль. Потом Рон разыгрывает случайно +1 или -1, и они оба двигаются в этом направлении; потом Рут делает то же самое, потом опять Рон и так далее. Таким образом, они все время двигаются вместе, но поочередно отвечают за выбор шага.
Из теории случайных процессов известно, что такое случайное блуждание должно возвращаться в 0 бесконечное число раз. Но когда мы посмотрели на (бесконечную) запись всего блуждания Рона с Рут, то увидели, что на самом деле они ни разу не вернулись в 0 после первого шага. Вывод: один из них жульничал, т.е. делал вид, что случайно разыгрывает шаг, а на самом деле говорил не случайные числа.
Внимание, вопрос: если ровно один из них жульничал, можем ли мы определить, изучая запись шагов, кто жульничал, Рон или Рут? Что вам говорит ваша интуиция (можем или не можем определить) и можете ли это обосновать?
Update: от А. Шеня в ФБ: "свойство возвращения имеет меру нуль и даже эффективно нулевое по Шнорру, поэтому существует вычислимый мартингал, не ограниченный на последовательности, и раскладывая его в произведение двух мартингалов для двух игроков, убеждаемся, что для одного из игроков (чётного или нечётного) такой мартингал есть - и потому соответствующая подпоследовательность не онлайн-случайна".
Если вы хотите понять, что здесь написано, приходите на импровизированную зум-лекцию А.Шеня сегодня в 7 вечера по Москве, ссылка:
https://us02web.zoom.us/j/83498766491?pwd=cjF4bDgrYnI2NG9pbDVROHFoZ3FIZz09
Meeting ID: 834 9876 6491
Passcode: 921716
Доска:
https://jamboard.google.com/d/1aNepqiZ6glDBNTkN-0IWJPBlRpk0DY9byglih3eHK2U/viewer
