Критерии случайности

[Черный Евгений]

1) Есть числа рациональные (периодические дроби) и иррациональные (бесконечные апериодические дроби). Последовательность цифр любого иррационального числа случайна. Закон распределения одинаков для всех - он нормален.
2) "Уж сколько раз твердили миру" - не случайно значение ирр. числа. Что же касается последовательности цифр - то в ней вы не найдете закономерности, какими бы критериями на случайность ее не проверять.
3) Да, последовательность цифр числа ПИ мы получаем по алгоритму, но это алгоритм вычисления для ПИ, а не для отдельно взятой цифры. А разве генераторы случайных последовательностей работают без алгоритмов? А мы тем не менее ими успешно пользуемся.

[venco]

Черный Евгений в сообщении #413023 писал(а):

Последовательность цифр любого иррационального числа случайна.

Вы ошибаетесь. Случайность и периодичность не антонимы.

[age]

я проводил подобное исследование. Результаты здесь.

-- Вт фев 15, 2011 00:06:36 --

Цитата:

В числе $\pi$ с 16 млн. знаков:
Последовательность из 5 нулей - 106 раз
Последовательность из 6 нулей - 9 раз!
Последовательность из 7 нулей - 1 раз (по-прежнему).

Еще один забавный вывод: вероятность в случайном наборе пятизначных чисел, что встретятся ПЯТЬ НУЛЕЙ равна 0,00001.
В исследованном числе - 16 млн.знаков.
Находим расчетное количество встречаемых последовательностей ПЯТЬ НУЛЕЙ:
N = 16 млн. * 0,00001 = 160 раз.
Фактическое - 106 раз.

Аналогично 6 НУЛЕЙ - в десять раз меньше, т.е. 16 раз.
Фактическое - 9 раз (или почти в 10 раз меньше, чем ПЯТЬ НУЛЕЙ).
СЕМЬ НУЛЕЙ - еще в десять раз меньше, т.е. 1,6 раза.
Факт - 1 раз.

Т.е. 6 НУЛЕЙ встречаются в 11,7 раза меньше чем 5 НУЛЕЙ.
А 7 НУЛЕЙ - в 9 раз реже чем ШЕСТЬ НУЛЕЙ.

Как видим, оба числа ОЧЕНЬ БЛИЗКИ к 10. Что ПОЛНОСТЬЮ подтверждает сделанные выводы.

Окончательный вывод: для того, чтобы встретить в иррациональном (трансцедентном) числе СТО НУЛЕЙ с вероятностью, близкой к 1, необходимо взять не менее 10^100 значащих разрядов числа ПИ.

То же самое касается и других последовательностей: шестерок, троек, двоек и т.д. Качество "случайности" числа $\pi$ очень высоко. Практически - это нормальное распределение. Почти то же касается и числа $e$, но там исследования затрудняются отсутствием софта, генерирующего $e$ с точностью в несколько миллионов знаков.

-- Вт фев 15, 2011 00:30:40 --

P.S.
Самая интересная из всех случайных последовательностей, что я видел - это простые числа. я создал несколько "карт" простых чисел, где старался выбирать различные "модули" (т.е. длины строки), т.к. от длины строки рисунок может менять свою структуру, перекашиваться.

[zhoraster]

Намного интереснее рисовать простые числа не табличкой, а "прямоугольной спиралью". Сейчас поищу картинку.

-- Вт фев 15, 2011 00:31:12 --

Вот и нашел. Это Станислав Улам придумал.

Распределение на этих картинках кажется не слишком "случайным". Явно видны некие диагональные прямые.

[Коровьев]

(Оффтоп)

А это красота - простые числа Гаусса.
Гауссово число, норма которого есть простое натуральное число, называется простым гауссовым числом.

[Черный Евгений]

For Age.
1) Я проводил исследования на коротких цепочках. Но эти исследования самые емкие из всех возможных, поскольку сразу дают картину по всем возможным сочетаниям, а не по отдельно взятым (например, число подряд идущих пятерок, или девяток).
2) Суть в том, что мы одну и ту же последовательность разбиваем на цепочки в начале единичной длины, потом по два элемента, и т.д. После этого анализируем их на одинаковость присутствия например, 0 и 1, если последовательность двоичная. Затем, цепочки из 2-х элементов, на примерно одинаковое число сочетаний 0,0 0,1 1,0 1,1. Далее переходим к цепочкам по 3 элемента, и т.д.
3) Если все сочетания встречаются примерно одинаковое число раз, то случайность гарантирована. Это невозможно доказать, но легко проверить. Попутно легко считается закон распределения. Для этого достаточно подсчитать энергетическую емкость цепочки (для сочетаний 0,0 Е=0 для 0,1 и 1,0 Е=1 для 1,1 Е=2) и повторяемость (частота) этих энергий. В результате получаем треугольник Паскаля или нормальный закон.
4) Невозможно (по крайней мере для меня) показать в общем виде случайность любого иррационального числа. Но ухватиться есть за что - они апериодичны и "несовместны" или невыразимы конечной последовательностью цифр. Два этих условия неизбежно приводят к случайности. Возможно, кто то сможет доказать это.

[venco]

Черный Евгений в сообщении #413258 писал(а):

4) Невозможно (по крайней мере для меня) показать в общем виде случайность любого иррационального числа. Но ухватиться есть за что - они апериодичны и "несовместны" или невыразимы конечной последовательностью цифр. Два этих условия неизбежно приводят к случайности. Возможно, кто то сможет доказать это.

Вы, возможно, что-то своё понимаете под случайностью. Даже если Вы имеете в виду нормальность, то это всё равно не верно.
Рассмотрите, например, число, десятичная запись которого состоит из двоичных записей последовательных натуральных чисел:
0,1 10 11 100 101 110 111 1000 ...
Оно непериодично, следовательно - иррационально (и даже трансцендентно). Но цифры подчиняются довольно простому закону, а цифры 2-9 не появляются вообще, т.е. оно не является нормальным.
Случайным его можно назвать, только используя какое-то извращённое значение слова "случайный".

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

[age]

zhoraster в сообщении #413113 писал(а):

Вот и нашел. Это Станислав Улам придумал.

Ага, то, чего мне не удалось (на моих "картах" вообще как рассыпанное зерно), удалось Станиславу Уламу. В его спиралях действительно есть смысл. Действительно прослеживаются некие диагональные "рукава". Только вот с чем он связан. Например, "юго-восточный" луч от центра содержит точные квадраты нечётных натуральных чисел, "северо-западный" - чётных.
$4!$, $5!$ тоже лежат на одном диагональном луче (в общем, интересная штука).

-- Вт фев 15, 2011 21:09:55 --

Кажется понял: каждый последующий виток спирали окружает предыдущий и показывает новый "масштаб структуры" чисел по мере их удалённости от 0 (как в 4-, так и 6-угольном случае). Так вот практически все простые числа замечательно "масштабируются", т.е. на каждом очередном масштабном уровне очень хорошо согласовываются с предыдущим, сохраняют структуру (в большинстве лежат на одних и тех же диагоналях).

Видимо, если как-то "доизменить" структуру спирали (не обязательно и не только количеством углов), то все простые числа могут лечь на лучи, исходящие от центра. Беда в том, что простые числа на предыдущих витках "создают" новые составные числа в последующих, поэтому структура меняется (но это так уже мысли вслух)

P.S.
Да, интересный результат.

[Черный Евгений]

For Venco.
1) Ничего своего.
2) Для того, чтобы считать число иррациональным, необходимо а) показать, что оно представлено бесконечной последовательностью, и б) что эта последовательность апериодична. История математики знает как трудно далось доказательство иррациональность числа ПИ. А Вы написали несколько цифр и утверждаете иррациональность.
3) Возьмите несколько миллионов цифр и проверьте их известными Вам критериями на случайность, получите закон распределения. Если критерии выполняются, то неизбежно получится нормальный закон. А то, что Вам известен некий закон получения последовательности, не имеет никакого отношения к случайности.
4) Понять это также сложно, как и то, что нельзя отличить спирт, изготовленный из отборного зерна от спирта из опилок. Но все же попробую. Подбросьте монету много раз. Затем занумеруйте стороны через 0 и 1. Получится двоичная последовательность, которая всегда соответствует конкретному числу. Пока Вы не знали числа, последовательность была случайной. Как только узнали о двоичном исчислении - конец случайности?

[venco]

Черный Евгений в сообщении #413424 писал(а):

For Venco.
1) Ничего своего.

Тогда Вам придётся признать, что ни $\pi$, ни $e$, ни указанное мной число случайными не являются, т.к. вычисляются по вполне определённым формулам. То, что Вы имеете в виду, называется "нормальное" число, причём нормальность зависит от основания системы счисления. Например, приведённое мной число в десятичной системе точно не нормальное, т.к. в нём встречаются только цифры 0 и 1.
И постарайтесь впредь не использовать слово "случайное" как замену слову "нормальное".

Черный Евгений в сообщении #413424 писал(а):

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

Сложность доказательства наличия или отсутствия периода зависит от того, как задано число. В моём случае (кстати я не первый его придумал), доказательство очень просто.

[Черный Евгений]

For Venco (2)
1) Когда Вы поймете, что случайно не число, а последовательность цифр, из которых оно складывается, когда Вы поймете, что у случайной последовательности есть свои критерии, вне зависимости от того, как именно эта последовательность получена - тогда можно будет продолжить дискуссию.
2) Первым шагом к взаимопониманию мог бы стать ответ на вопрос. Я 1000 раз подбросил монету, занумеровав и записав двоичную последовательность. Потом сравнил это число с урезанным до этого же количества знаков числом ПИ. С ужасом обнаружил, что они совпадают. Что мне делать? Признать последовательность не случайной? А если бы я не знал о существовании числа Пи? И почему падение монеты, признанное всеми и везде случайным, вдруг Вами оспаривается только потому, что есть соответствие с числом Пи?

[venco]

Черный Евгений в сообщении #413802 писал(а):

For Venco (2)
1) Когда Вы поймете, что случайно не число, а последовательность цифр, из которых оно складывается, когда Вы поймете, что у случайной последовательности есть свои критерии, вне зависимости от того, как именно эта последовательность получена - тогда можно будет продолжить дискуссию.

Дык, в том-то и дело, что последовательность цифр числа $\pi$ не случайна.

Черный Евгений в сообщении #413802 писал(а):

2) Первым шагом к взаимопониманию мог бы стать ответ на вопрос. Я 1000 раз подбросил монету, занумеровав и записав двоичную последовательность. Потом сравнил это число с урезанным до этого же количества знаков числом ПИ. С ужасом обнаружил, что они совпадают. Что мне делать? Признать последовательность не случайной? А если бы я не знал о существовании числа Пи? И почему падение монеты, признанное всеми и везде случайным, вдруг Вами оспаривается только потому, что есть соответствие с числом Пи?

Даже если последовательность бросаний монеты совпадёт с другой, заранее написанной на бумажке (независимо от того, совпадает эта последовательность с $\pi$ или с каким-либо другим известным числом), я заподозрю неладное в этой монете. Случайную последовательность предсказать нельзя. А если можно, то она не случаная.

[_hum_]

Может, все-таки стоило бы ознакомиться с предметом, например, по статье "Может ли (индивидуальная) последовательность нулей и единиц быть случной" http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1990_UMN_Can_sequence_random.pdf, чтобы не спорить попусту.

[svv]

venco писал(а):

Даже если последовательность бросаний монеты совпадёт с другой, заранее написанной на бумажке (независимо от того, совпадает эта последовательность с $\pi$ или с каким-либо другим известным числом), я заподозрю неладное в этой монете. Случайную последовательность предсказать нельзя. А если можно, то она не случаная.

Я бы тоже заподозрил неладное. Но что делать в общем случае? Допустим, у меня на столе стоит генератор числовых последовательностей. Он может выдавать как истинно случайные последовательности (это ведь реализуемо технически?), так и сгенерированные по одному из множества записанных в него алгоритмов. Это зависит от того, какой включен режим работы. Вот генератор выдает какую-то последовательность. Как по ней узнать, включен ли "случайный" режим, или же "алгоритмический"? Наверняка задача "по данной последовательности установить, существует ли порождающий её алгоритм" (="определить, является ли бесконечная дробь записью вычислимого числа") алгоритмически неразрешима -- ведь для ответа недостаточно анализа никакой конечной части последовательности.

Но допустим даже, что нам под силу сравнивать последовательности "в целом". С этой точки зрения неплохо было бы знать наизусть для нескольких сотен самых общеизвестных математических констант всё их разложение в бесконечную дробь : иногда можно эффектно схватить лже-ГСЧ за руку. Но по своей "неслучайности" эти константы ничем не лучше остального счетного множества безымянных вычислимых (т.е. столь же неслучайных) последовательностей. А со всеми не сравнишь...

Что означает "последовательность можно/нельзя предсказать"?
Я объявляю несколько первых цифр: 31415926 и говорю: "А дальше Вы, пожалуйста".
Вы говорите "535".
Я говорю "Хм, верно! А дальше?"
Вы: "897".
Я: "А вот и нет!".
Оказывается, я коварным образом заменил в последовательности некоторые цифры из разложения $\pi$ на цифры из разложения $e$. Да, по некоторому алгоритму. Но легче ли Вам от этого? Вы же не станете заявлять: "Да, я мог бы предсказать эту последовательность, только... скажите мне, какой у Вас там алгоритм замены?"

[Андрей АK]

svv в сообщении #413993 писал(а):

Наверняка задача "по данной последовательности установить, существует ли порождающий её алгоритм" (="определить, является ли бесконечная дробь записью вычислимого числа") алгоритмически неразрешима -- ведь для ответа недостаточно анализа никакой конечной части последовательности.

Многие криптографы тоже так думали ... пока все их шифры ,в конце концов, не взломали.
Еще один пример - перевод чисел из одной системы счисления в другую - конечные числа в одной, превращаются в бесконечные последовательности в другой, но ,тем не менее, мы всегда можем установить (по длине периода повторения) из какой системы счисления было взято число ну и догадаться, что был использован этот ,конкретный, алгоритм.

Значит, если генерирующий алгоритм недостаточно сложен, то определить его можно, а вот чуть чуть посложнее - и уже "алгоритмически неразрешима"?

Может мы просто чего-то не понимаем?