Случайность и закономерность

[AD]

Pi в сообщении #209493 писал(а):

А вот это хорошо известный математический факт, что цифры в числе $\pi$ совершенно случайны

Нормальность числа $\pi$ уже доказали? Когда?

[AlexDem]

ewert в сообщении #209494 писал(а):

Для третьей последовательности гипотеза принимается с доверительной вероятностью что-то порядка 99.5%. Для всех остальных -- безнадёжно отвергается.

И о чём говорит эта цифирь? Как, например, из неё можно получить - сколько раз нужно бросить 50 монет, чтобы получить регулярную серию, достаточную для того, чтобы сбить решающих с толку? То есть, как долго нужно бросать монеты, чтобы сформулировать эту задачу при том, что в качестве реальной можно будет взять регулярную серию?

Добавлено спустя 9 минут 12 секунд:

Да, ещё лучше вопрос - верно ли, что если я поставлю 99.5 руб на 3-й вариант, а кто-то другой - около 0.1 руб на первый, а победитель будет получать все ставки целиком, то при многократных повторениях никто из нас не окажется в особом выигрыше?

[Pi]

ewert в сообщении #209494 писал(а):

Соответствующие статистики Пирсона: 147; 45.122; 0.061; 49.041.

Для третьей последовательности гипотеза принимается с доверительной вероятностью что-то порядка 99.5%. Для всех остальных -- безнадёжно отвергается.

Зачем так сложно?
Максимальный абсолютный коэффициент корреляции вообще дает для этих трех просто единицу. И только для третьей близок к нулю. Причем здесь 100% процентная уверенность - без всяких допущений.

Pi в сообщении #209138 писал(а):

Третья последовательность, и не потому-что энтропия или что либо еще, а потому-что там максимальный абсолютный коэффициент корреляции самый близкий к нулю.

В остальных трех последовательностях максимальный абсолютный коэффициент корреляции равен единице - то есть они полностью детерминированные.

[ewert]

Pi в сообщении #209510 писал(а):

Причем здесь 100% процентная уверенность - без всяких допущений.

100% уверенности быть не может. Это означало бы, что такие последовательности появиться не могут. А это неправда.

[AlexNew]

Pi писал(а):

Я сказал что энтропия не причем, она вообще не адекватна. Энтропия это СРЕДНЕЕ количество информации. Мы же здесь видим частности, а не среднее.
Чтоб понять почему энтропия здесь не адекватна, задайтесь вопросом какова пропускная способность канала должна быть чтоб послать эти последовательности. Она будет одна и таже, потому-что по условию задачи вероятность появлени каждого символа все равно 1/2.

Существует как минимум 3 подхода к определению энтропии
1) информационный (у вас)
2) то что у worm2
3) статистический

Разумеется то о чем вы говорите не имеет отношения к делу.

ewert писал(а):

Проверяем гипотезу : каждый следующий результат не зависит от предыдущего…

Из этого ни в коем случае не будет следовать что данные 4 последовательности более вероятны чем остальные 2^50

Единственное что можно сделать так это отнести данные последовательности к какому либо классу.
Все множество исходов 2^50 разбивается на классы по какому либо признаку, поскольку вероятность каждого исхода одинаково, а количество элементов в классе может быть сильно разным, мы и получим разную вероятность для данных последовательностей.

Вопрос в том каким способом можно разбить все множество исходов на такие группы?

(Например можно взять максимальное число различных подпоследовательностей в последовательности длиной 50, после чего можно будет легко ввести понятие энтропии и посчитать вероятность для данных последовательностей.)

интуитивно мы именно так и поступаем (не раз здесь говорилось об этом)

[Nxx]

Энтропия - это мера сжимаемости информации. Если строчку бит можно сжать, то там низкая энтропия. А если распределение случайное, то энтропия максимальна.

[gris]

А какова вероятность того, что в 50-битовой случайной строке будет не меньше 12 2-битных подстрок каждого из 4 видов (00,01,10,11)?

Какова вероятность того, что в ней поровну 0 и 1?

[Nxx]

gris писал(а):

А какова вероятность того, что в 50-битовой случайной строке будет не меньше 12 2-битных подстрок каждого из 4 видов (00,01,10,11)?

Какова вероятность того, что в ней поровну 0 и 1?

Вероятность того, что поровну 0 и 1 намного выше вероятности того, что там только 1 или только 0.

[gris]

Бернулли говорит 0,11. А вот первую вероятность как посчитать?

Nxx, ну уж не намного, чуть больше, чем на 0,1

[Nxx]

gris писал(а):

Nxx, ну уж не намного, чуть больше, чем на 0,1

Зато, во много раз

[AlexNew]

Nxx писал(а):

Энтропия - это мера сжимаемости информации. Если строчку бит можно сжать, то там низкая энтропия. А если распределение случайное, то энтропия максимальна.

это не так, способ сжатия определяется машиной, ясно что если вы станете сжимать все 2^50 возможных комбинаций только часть из них сожмется, остальные последовательности наоборот увеличатся в размере.
Что имено имено сожмется зависит от алгоритма-машины, поэтому такое определение энтропии условно - своего рода разбиение всех исходов на классы, причем условие разбиения определяется из "алгоритмических соображений" - не совсем понятно почему это должно иметь отношение случайности.

вот определение worm2 (2)

worm2 писал(а):

каждой последовательности из некоторого множества M можно сопоставить энтропию следующим образом:

1) Отсортируем всевозможные программы для Машины Тьюринга (МТ) в лексикографическом порядке (начиная от самых коротких);
2) Выкинем из полученной на предыдущем шаге последовательности (ПНПШП) некорректные и те, которые не останавливаются;
3) Выкинем из ПНПШП те, которые НЕ выдают в результате последовательности из множества M;
4) Из ПНПШП выкинем повторяющиеся элементы;
5) Каждому элементу ПНПШП сопоставим натуральное число, равное длине соответствующей программы для МТ.

В результате мы поставим каждому элементу из множества M длину минимальной программы для МТ, выдающей эту последовательность. Чем больше длина, тем более случайным можно считать число.

По-моему, это похоже на Колмогоровское определение энтропии, лень сверяться.

но мне кажется имеет смысл использовать статистическое определение энтропии.

http://www.sciteclibrary.ru/rus/catalog/pages/6374.html тут про "энтропию двоичного числа" : ) - один из подходов.

[epros]

Nxx писал(а):

Энтропия - это мера сжимаемости информации. Если строчку бит можно сжать, то там низкая энтропия. А если распределение случайное, то энтропия максимальна.

Что Вы имеете в виду, когда употебляете слово "распределение" в данном контексте?

[AD]

Присоединяюсь к вопросу eprosа. Вообще, хорошая мысль! Случайное распределение ... случайная мера ... случайная обобщенная функция ... на случайномерном пространстве ... ну или на случайном измеримом пространстве, или на случайном пространстве пробных функций ...

P. S. Так, все основные персонажи здесь - что, и тут на конструктивизм перейдем?

[Schraube]

AD писал(а):

Pi в сообщении #209493 писал(а):

А вот это хорошо известный математический факт, что цифры в числе $\pi$ совершенно случайны

Нормальность числа $\pi$ уже доказали? Когда?

Мне тоже интересно

Один из мифов, имхо.
Миф основан на вольной интерпретации статьи
↑ Bailey, D. and Crandall, R. On the random character of fundamental constant expansion. Experimental Mathematics, 10, 175—190, (2001)

Цитата:

В статье сказано следующее

В 2001 году Дэвид Бэйли (Lawrence Berkeley NL, Калифорния) и Ричард Крандалл (Reed College, Орегон) доказали, что число π — нормально, то есть его десятичное разложение содержит любую целочисленную строку[1].

Однако сами Bailey, D. and Crandall, R. пишут лишь

We propose a theory to explain random behavior for the digits in the expansions of fundamental mathematical constants. At the core of our approach is a general hypothesis concerning the distribution of the iterates generated by dynamical maps. On this main hypothesis, one obtains proofs of base-2 normality—namely bit randomness in a specific technical sense—for a collection of celebrated constants, including π and others.

цитирую по
http://ru.wikipedia.org/wiki/%D0%9E%D0% ... 0%BB%D0%BE)#cite_note-0

[Pi]

AlexNew в сообщении #209612 писал(а):

Nxx писал(а):
Энтропия - это мера сжимаемости информации. Если строчку бит можно сжать, то там низкая энтропия. А если распределение случайное, то энтропия максимальна.

это не так, способ сжатия определяется машиной, ясно что если вы станете сжимать все 2^50 возможных комбинаций только часть из них сожмется, остальные последовательности наоборот увеличатся в размере.
Что имено имено сожмется зависит от алгоритма-машины, поэтому такое определение энтропии условно - своего рода разбиение всех исходов на классы, причем условие разбиения определяется из "алгоритмических соображений" - не совсем понятно почему это должно иметь отношение случайности.

Совершенно верно. Если мы имеем права преобразовать входную строчку как нам заблагароссудится, то мы можем сжать любой класс сообщений компактно вне зависимости от его первоначальной сложности.
Но по условиям задачи это монетки, и все символы имеют вероятность 1/2.

Как не определяй энтропию, но здесь она не поможет.
А Колмогоровская сложность информации ни причем. Поскольку она именно зависит от системы комманд машины, мы можем выбрать можем выбрать паттерн как комманду, и получить меньшую сложность для определенного класса последовательностей.

Schraube в сообщении #209694 писал(а):

AD писал(а):
Pi в сообщении #209493 писал(а):
А вот это хорошо известный математический факт, что цифры в числе $\pi$ совершенно случайны
Нормальность числа $\pi$ уже доказали? Когда?


Мне тоже интересно Smile

Нормальности никто не требует. Нормальность это более сильное требование, чем просто случайность. В исходном тексте сообщения нет ни слова об требовании нормальности. Она здесь никому не нужна.