April 12th, 2012

moose, transparent

о несимметричной монете (математическое)

Эта статья немножко взорвала мне мозг:

On Determining the Irrationality of the Mean of a Random Variable (1973)

Предположим, у вас есть несимметричная монета, с вероятностью выпадения орла P, которая может быть даже иррациональной. Статья демонстрирует алгоритм, который делает следующее. Вы кидаете монету раз за разом, и после каждого броска согласно алгоритму заявляете либо "я считаю, что P равна такому-то рациональному числу", либо "я считаю, что P иррациональна". Вы так продолжаете до бесконечности. В статье доказывается, что вы в таком случае ошибетесь только конечное число раз (добавления мелким шрифтом: с вероятностью 1 и при условии, что P лежит вне определенного иррационального подмножества меры 0).

То, что можно отличить рациональную от иррациональной вероятности после помощью конечного числа ошибок - очень анти-интуитивно. Важно понять, конечно, что алгоритм не дает возможности в какой-то конкретный момент остановиться и сказать: все, я уверен, что P рационально/иррационально, и моя оценка не изменится. Но даже и без этого, все равно впечатляет.

Основная идея алгоритма следующая. После броска номер N мы вычисляем среднее значение результатов до сих пор, берем маленький интервал delta(N) вокруг него (величина интервала сужается от броска к броску), и находим в заранее фиксированной нумерации всех рациональных чисел первое, которое попадает в этот интервал. Если его номер в этой нумерации меньше некоего предела k(N), который растет вместе с N, то мы говорим, что P - это рациональное число. Если меньше - говорим, что P иррационально. Интуитивно говоря, порядковый номер рационального числа служит мерой его "сложности", и после каждого броска мы ищем самое "простое" рациональное число, которое попадает в интервал, но настаиваем при этом, чтобы оно не было слишком "сложным", иначе выбираем иррациональность.

Тогда получается, что если настоящее значение P рационально, то после того, как k(N) превзойдет его порядковый номер, оно постепенно вытеснит более "простых", но менее точных кандидатов из сужающихся интервалов, и по закону больших чисел с вероятностью 1 будет оставаться внутри интервалов для всех кроме конечного числа бросков. Если же P иррационально, то описанного выше недостаточно, и нужно добавить еще, что мы все эти вычисления и решения делаем не после каждого броска, а время от времени, а в промежутках повторяем предыдущее предсказание. Размеры "промежутков" дают еще один параметр, и подбирая его вместе с k(N) и delta(N), мы можем гарантировать, что "рациональные" предсказания будут продолжаться неограниченно лишь на небольшом подмножестве иррациональных P, которое оказывается меры 0. Эту часть доказательства (для иррациональных P) я не до конца понял и проследил, признаться.

Еще там есть обсуждение гипотетических приложений в физике, которое по-своему взрывает мозг, потому что открывает теоретическую возможность проверки, является какая-то физическая константа рациональной или иррациональной - опять-таки, "проверка" тут подразумевается в специальном и не очень полезном смысле, потому что невозможно остановиться и сказать, я закончил проверку и пришел к такому-то выводу. Там упоминают гипотезу, которая в 60-х годах, когда вышла эта статья, еще соглашалась с опытом: что отношение масс протона и электрона равно в точности 6*pi5. Думаю, что эта гипотеза многих успела в то время повеселить; сейчас, если википедия не врет, это отношение знают с большей точностью, и она определенно неверна (статья в википедии даже не упоминает ее).

P.S. Я прочитал эту статью, потому что о ней упомянул некролог ее автора, статистика и специалиста по теории информации Тома Кавера.