![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
о несимметричной монете (математическое)
Эта статья немножко взорвала мне мозг:
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. Я прочитал эту статью, потому что о ней упомянул некролог ее автора, статистика и специалиста по теории информации Тома Кавера.
no subject
Это довольно сильное условие. К примеру, мера рациональных чисел равна нулю...
no subject
странно -
прошу прощения,
no subject
(Anonymous) 2012-04-12 01:33 pm (UTC)(link)no subject
no subject
no subject
no subject
no subject
Даю более быстро сходящийся алгоритм: на первом броске заявляете, что P - рационально, на втором, что иррационально.
Задача решена? В лучшем случае вы сразу даёте правильный ответ, в худшем - со второй попытки.
no subject
Вообще-то лучше сначала убедиться, что вы правильно поняли, о чем речь, а потом кидаться глупостями.
no subject
no subject
no subject
no subject
no subject
был на вашем токе, контент помню очень смутно, но помню, что понравилось.
no subject
Рад, что вам понравилось. А вы сами не представитесь (можно в личку)?
no subject
бахтияр нейман, 2nd year grad student, работаю с тарой джавиди.
no subject
no subject
T(z)=Exp[2*Pi*A*z]
где у нас есть периодичность в случае рационального A=p/q и всюду плотность в случае иррационального. В аспекте этого примера процитированный результат вполне интуитивен, поскольку периодичность должна ловится за конечное число шагов, и фишка как поймать непериодичность, и тут нам должно помочь равномерное распределение точек.
no subject
Любопытно было бы узнать хотя бы одно число из этого подмножества. (На полное описание подмножества я не претендую :-)
no subject
no subject
apropos
http://dl.dropbox.com/u/3198145/bdd-mem.pdf
Взрыв мозга гарантирован.