?

Log in

о несимметричной монете (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о несимметричной монете (математическое) [апр. 12, 2012|02:37 pm]
Anatoly Vorobey
Эта статья немножко взорвала мне мозг:

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

Comments:
[User Picture]From: burrru
2012-04-12 11:44 am
и при условии, что P лежит вне определенного подмножества меры 0

Это довольно сильное условие. К примеру, мера рациональных чисел равна нулю...
(Ответить) (Thread)
[User Picture]From: avva
2012-04-12 11:47 am
Да, мне надо, конечно, добавить, что мера 0 имеется в виду для иррациональных P. Спасибо.
(Ответить) (Parent) (Thread)
From: a_shen
2012-04-12 12:27 pm

странно -

казалось бы, простейшее правило "говорить, что рациональное, если в текущей дроби больше 90% составляет периодическая часть", обладает тем же самым свойством?
(Ответить) (Thread)
From: a_shen
2012-04-12 12:29 pm

прошу прощения,

написал ерунду - нам, конечно, дают не дробь, а нули и единицы, дробь ещё надо получить с нужной точностью и с большой вероятностью, взяв соответствующее число испытаний из закона больших чисел. Видимо, примерно это и написано в статье...
(Ответить) (Parent) (Thread)
From: (Anonymous)
2012-04-12 01:33 pm
Логично было бы сопроводить этот пост ссылкой на один из некрологов. Лучше всего на тот, в котором Вы увидели ссылку на эту статью.
(Ответить) (Thread)
[User Picture]From: avva
2012-04-12 07:00 pm
Да, вы правы, я добавил.
(Ответить) (Parent) (Thread)
[User Picture]From: buddha239
2012-04-12 02:37 pm
Если честно, не вижу в этом результате ничего удивительного - и, видимо, ничего нетривиального.:)
(Ответить) (Thread)
[User Picture]From: migmit
2012-04-13 06:44 am
В общем, да. Особенно в свете условия "P лежит вне определенного иррационального подмножества меры 0", что как бы defeats the purpose, ибо такие подмножества могут быть очень большими.
(Ответить) (Parent) (Thread)
[User Picture]From: niobium0
2012-04-12 04:19 pm
а эти 6*pi^5 небось в N_0.
(Ответить) (Thread)
[User Picture]From: amarao_san
2012-04-12 06:32 pm
Какая глупость.

Даю более быстро сходящийся алгоритм: на первом броске заявляете, что P - рационально, на втором, что иррационально.

Задача решена? В лучшем случае вы сразу даёте правильный ответ, в худшем - со второй попытки.
(Ответить) (Thread)
[User Picture]From: avva
2012-04-12 07:08 pm
По условиям нужно давать гипотезу после каждого броска.

Вообще-то лучше сначала убедиться, что вы правильно поняли, о чем речь, а потом кидаться глупостями.
(Ответить) (Parent) (Thread)
[User Picture]From: niobium0
2012-04-12 07:54 pm
Том Ковер умер??!! Я в шоке. В феврале он выглядел совершенно нормально. Аллах ряхмят элсин. :(
(Ответить) (Thread)
[User Picture]From: ded_maxim
2012-04-12 08:42 pm
Да, в феврале я еще с ним беседовал на конференции в Сан Диего ...
(Ответить) (Parent) (Thread)
[User Picture]From: niobium0
2012-04-12 11:06 pm
вы - макс рагинскй?
(Ответить) (Parent) (Thread)
[User Picture]From: ded_maxim
2012-04-12 11:11 pm
Каюсь, я.
(Ответить) (Parent) (Thread)
[User Picture]From: niobium0
2012-04-12 11:16 pm
да, мир тесен.
был на вашем токе, контент помню очень смутно, но помню, что понравилось.
(Ответить) (Parent) (Thread)
[User Picture]From: ded_maxim
2012-04-13 04:46 am
Вот этот: http://ita.ucsd.edu/workshop/12/files/abstract/abstract_1442.txt ?

Рад, что вам понравилось. А вы сами не представитесь (можно в личку)?
(Ответить) (Parent) (Thread)
[User Picture]From: niobium0
2012-04-13 05:16 am
yep, assuming my mind doesn't play tricks on me. :)

бахтияр нейман, 2nd year grad student, работаю с тарой джавиди.
(Ответить) (Parent) (Thread)
[User Picture]From: ded_maxim
2012-04-14 12:34 am
Мир воистину тесен! Передавайте Таре привет !
(Ответить) (Parent) (Thread)
[User Picture]From: akor168
2012-04-12 08:18 pm
Так как мне сразу пришел в голову стандартный пример поворота единичной окружности на угол:

T(z)=Exp[2*Pi*A*z]

где у нас есть периодичность в случае рационального A=p/q и всюду плотность в случае иррационального. В аспекте этого примера процитированный результат вполне интуитивен, поскольку периодичность должна ловится за конечное число шагов, и фишка как поймать непериодичность, и тут нам должно помочь равномерное распределение точек.
(Ответить) (Thread)
[User Picture]From: p_govorun
2012-04-12 08:22 pm
при условии, что P лежит вне определенного иррационального подмножества меры 0

Любопытно было бы узнать хотя бы одно число из этого подмножества. (На полное описание подмножества я не претендую :-)
(Ответить) (Thread)
[User Picture]From: akor168
2012-04-12 08:44 pm
Я не смотрел статью, но нередко такие множества полностью неконструктивны, то есть доказывается, что его можно покрыть интервалами сколь угодно малой длины, иногда даже с оценкой или вычислением точной Хаусдофовой размерности, но доказать, что конкретное число находится в нем, есть отдельная, и причем значительно более сложная задача. Например, почти все числа нормальны, а вот доказать, что конкретное вроде Sqrt(2) может быть задачей на Миллион.
(Ответить) (Parent) (Thread)
[User Picture]From: p_govorun
2012-04-12 08:52 pm
Спасибо, интересно. Значит, не всё так просто.
(Ответить) (Parent) (Thread)
[User Picture]From: ded_maxim
2012-04-12 08:41 pm

apropos

Анатолий, посмотрите еще вот на эту статью:

http://dl.dropbox.com/u/3198145/bdd-mem.pdf

Взрыв мозга гарантирован.
(Ответить) (Thread)