Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

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

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

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. Я прочитал эту статью, потому что о ней упомянул некролог ее автора, статистика и специалиста по теории информации Тома Кавера.
Subscribe

  • не страшно

    Рассказали анекдот, наверное старый, но не знал, очень понравился: — От чего умер ваш дедушка? — Грипп. — А, ну это не страшно...

  • действительно физик

    Видел шутку про нобелевскую премию по физике (напомню, что все сразу стали спорить, имеют ли работы, за которые ее дали, отношение к физике).…

  • анекдот про уши

    Анекдот из фейсбука, пост из сентября 2014, за прошедшие 10 лет стал только более актуальным: Мужику оторвало голову. Безголовая тушка мечется…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 19 comments

  • не страшно

    Рассказали анекдот, наверное старый, но не знал, очень понравился: — От чего умер ваш дедушка? — Грипп. — А, ну это не страшно...

  • действительно физик

    Видел шутку про нобелевскую премию по физике (напомню, что все сразу стали спорить, имеют ли работы, за которые ее дали, отношение к физике).…

  • анекдот про уши

    Анекдот из фейсбука, пост из сентября 2014, за прошедшие 10 лет стал только более актуальным: Мужику оторвало голову. Безголовая тушка мечется…