о несимметричной монете (математическое)
Apr. 12th, 2012 02:37 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЭта статья немножко взорвала мне мозг:
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. Я прочитал эту статью, потому что о ней упомянул некролог ее автора, статистика и специалиста по теории информации Тома Кавера.
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. Я прочитал эту статью, потому что о ней упомянул некролог ее автора, статистика и специалиста по теории информации Тома Кавера.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-04-12 11:44 am (UTC)Это довольно сильное условие. К примеру, мера рациональных чисел равна нулю...
no subject
Date: 2012-04-12 11:47 am (UTC)странно -
Date: 2012-04-12 12:27 pm (UTC)прошу прощения,
Date: 2012-04-12 12:29 pm (UTC)no subject
Date: 2012-04-12 01:33 pm (UTC)no subject
Date: 2012-04-12 02:37 pm (UTC)no subject
Date: 2012-04-12 04:19 pm (UTC)no subject
Date: 2012-04-12 06:32 pm (UTC)Даю более быстро сходящийся алгоритм: на первом броске заявляете, что P - рационально, на втором, что иррационально.
Задача решена? В лучшем случае вы сразу даёте правильный ответ, в худшем - со второй попытки.
no subject
Date: 2012-04-12 07:00 pm (UTC)no subject
Date: 2012-04-12 07:08 pm (UTC)Вообще-то лучше сначала убедиться, что вы правильно поняли, о чем речь, а потом кидаться глупостями.
no subject
Date: 2012-04-12 07:54 pm (UTC)no subject
Date: 2012-04-12 08:18 pm (UTC)T(z)=Exp[2*Pi*A*z]
где у нас есть периодичность в случае рационального A=p/q и всюду плотность в случае иррационального. В аспекте этого примера процитированный результат вполне интуитивен, поскольку периодичность должна ловится за конечное число шагов, и фишка как поймать непериодичность, и тут нам должно помочь равномерное распределение точек.
no subject
Date: 2012-04-12 08:22 pm (UTC)Любопытно было бы узнать хотя бы одно число из этого подмножества. (На полное описание подмножества я не претендую :-)
apropos
Date: 2012-04-12 08:41 pm (UTC)http://dl.dropbox.com/u/3198145/bdd-mem.pdf
Взрыв мозга гарантирован.
no subject
Date: 2012-04-12 08:42 pm (UTC)no subject
Date: 2012-04-12 08:44 pm (UTC)no subject
Date: 2012-04-12 08:52 pm (UTC)no subject
Date: 2012-04-12 11:06 pm (UTC)no subject
Date: 2012-04-12 11:11 pm (UTC)no subject
Date: 2012-04-12 11:16 pm (UTC)был на вашем токе, контент помню очень смутно, но помню, что понравилось.
no subject
Date: 2012-04-13 04:46 am (UTC)Рад, что вам понравилось. А вы сами не представитесь (можно в личку)?
no subject
Date: 2012-04-13 05:16 am (UTC)бахтияр нейман, 2nd year grad student, работаю с тарой джавиди.
no subject
Date: 2012-04-13 06:44 am (UTC)no subject
Date: 2012-04-14 12:34 am (UTC)