кто жульничал?

[avva]

Интересная задача на проверку вероятностной интуиции, от Гила Калая.

Рон и Рут создают случайное блуждание по целым числам следующим образом. Они начинают оба на числе ноль. Потом Рон разыгрывает случайно +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

Comments

[epimorphisms_split]

My intuition says no, we can't. The cheater might play something along these lines of playing +1 with probability of 1/2 + f(p), p current position, f a function that the player chooses in secret such that it all sums to 0, but f(1)=1/2.

This way the walk should visits each position only a finite number of times, but we cannot tell who is responsible for it.

I might be talking out of my arse here.

[avva]

I think you hit on the best strategy for the cheater, at least I was thinking along the same lines. In the lecture by Shen he talked us through how even that is exploitable through the machinery of computable martingales, but that is not easy to intuitively put into words.

Briefly, a martingale is a betting strategy that assigns fractions a_-1,a_+1 summing up to 1 to any finite prefix {-1,+1}^n; coming up to that prefix with money D you bet corresponding portions of D on seeing -1/+1 next, and get double your bet back. If starting up with $1 your winnings are unbounded on a particular infinite string, that string is nonrandom by definition (the intuition is, you keep using your knowledge of any computable regularities in the string to keep winning more money). It turns out that because the set of strings that never come back to 0 is of measure 0, any such string is exploitable in this way - you can build a martingale [a finite program that doesn't need to encode the entire infinite string] winning on it. It's also easy to show that if you split this martingale into two, one making decisions only on even steps and betting 0.5/0.5 on the odd steps, and vice versa, one of them will also be unbounded, and that corresponds to the cheating sequence (formally we can prove that the odds of getting a sequence that has an unbounded martingale, if one uses a fair coin, are 0).

So I guess one way to try and put it more simply is to say that we can exploit the unavoidable need of the cheater to stay away from 0 by betting money in a way that relies on that bias, even w/o knowing how precisely the cheater does it; and then this exploit must shine through on either the odds or the evens.