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

[Lesobrod]

Допустим, имеются последовательности из конечного набора элементов. Меня интересуют цифры числа $\pi$, остатки от деления простых на данное число и т.п. Какие существуют критерии случайности данной последовательности? Известно, что понятие "случайный" требует осторожного подхода. Но ведь ясно, что цифры числа $\pi$ более случайны, чем последовательность $dig \equiv 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,...$. Сам я начал с простой вещи - относительных частот появления данного элемента $p_i(n)$. Здесь $n$ - длина анализируемой последовательности. Необходимым условием "случайности" является

$$\forall(i) \lim_{n \to \infty}p_i(n)=c$$

Однако, видно, что и $dig$ после второго же периода будет удовлетворять этому критерию! Решил разобраться в информационной энтропии Информационная_энтропия
Пусть

$$ h(n)=-\sum_{i=1}^mp_i(n)\log_2 p_i(n)$$

, где $m$ - количество возможных состояний, для цифр $m=10$. Однако для больших $n$ энтропии $\pi$ и $dig$ становятся одинаковыми! Последнее, что пришло мне в голову - это анализировать появление пар, троек и других сочетаний элементов. Формула остаётся той же (???), только $i$ уже означает номер одного из возможных сочетаний (пар цифр, скажем, 100 ).
Смоделировал это на Wolfram. Убедился, что $h(n)$ растёт с ростом $n$. Но если её определять для пар, то энтропия примитивной последовательности заметно отстаёт от энтропии $\pi$ ; для троек - ещё заметнее.
Правильно ли я сформулировал критерий? Как ещё можно анализировать случайность цифровых последовательностей?

[hurtsy]

Lesobrod в сообщении #396627 писал(а):

Как ещё можно анализировать случайность цифровых последовательностей?

Объекты Ваших исследований не являются случайными последовательностями. Элементы случайности могут внести вычисления. Ваша формулировка критерия ... , а где она? С уважением,

[Lesobrod]

Хотя это не доказано, но большинство математиков уверено, что $\pi$
является нормальным http://mathworld.wolfram.com/NormalNumber.html
Повторюсь, я понимаю, что понятие "случайный" трудно сформулировать корректно.
Но, с другой стороны, Вы утверждаете, что цифры $\pi$
не являются случайной последовательностью. Что это в точности означает?
На данный момент мой критерий случайности таков (для некоторой последовательности десятичных цифр).
Пусть $p_{1i}(n)$ - относительная частота появления одной данной цифры на отрезке длинной $n$;
$p_{2i}(n)$ - то же, но для данной пары идущих подряд цифр и т.д. Последовательность случайна, если

$$\forall(k,i) \lim_{n \to \infty}p_{ki}(n)=1/N(k)$$

, где $N(k)$ - количество возможных цифр ($N(1)=10$) ,пар,троек и т.д.

[Someone]

Lesobrod в сообщении #396639 писал(а):

Хотя это не доказано, но большинство математиков уверено, что $\pi$
является нормальным

Нормальность и случайность - разные понятия.

Lesobrod в сообщении #396639 писал(а):

Вы утверждаете, что цифры $\pi$
не являются случайной последовательностью. Что это в точности означает?

Это означает что цифры числа $\pi$ вычисляются с помощью алгоритма.

Д.Кнут. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы. "Мир", Москва, 1977.

§ 3.5 так и называется: "Что такое случайная последовательность?"
Прежде, чем изобретать своё определение, разберитесь в том, что сделано до Вас.

[Руст]

Лично для меня настоящие случайные последовательности это те, что создаются по некоторому закону. Что касается цифр числа $\pi$, то думаю, что это действительно случайная последовательность, только мы не умеем доказывать. Тут только конечное число исходов. Соответственно последовательность из них назовем случайным, если для любой последовательности цифр длины $k$ $a=x_1x_2...x_k$
среди последовательности N цифр после $N_1$ цифр (т.е. среди цифр с номерами от $N_1+1$ до $N_1+N$ количество встреч такой последовательности a находится в интервале
$(M-s,M+s)$ где $M=Np_1p_2...p_k, s=\sqrt{N}(ln(N_1+N)+C)$. В случае равномерности появления цифр $p_1...p_k=10^{-k}.$

[bot]

А правду говорят, что неизвестно, встречается ли девятка в записи числа $\pi$ конечное или бесконечное число раз?Если вдруг окажется число вхождений девятки конечным, то какая же это случайная последовательность?

[В.О.]

Если случайность понимать в Колмогоровском смысле, то последовательность чисел можно назвать случайной, если она является реализацией случайной величины в бесконечной последовательности независимых испытаний. В частности, в пределе частота появления по соседству любой пары чисел должна быть равна произведению вероятностей появления каждого из чисел (для последовательности dig не выполняется) и т.п. Должны выполняться закон больших чисел, ЦПТ и т.д.

[Someone]

Руст в сообщении #396695 писал(а):

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

Например, последовательность цифр в числе 0,(1234567890).

Вопрос гораздо сложнее, чем кажется на первый взгляд. Существует множество тестов случайности. Для начала можно почитать Кнута, а потом поискать в Интернете.

[Руст]

Someone в сообщении #396765 писал(а):

Руст в сообщении #396695 писал(а):

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

Например, последовательность цифр в числе 0,(1234567890).

Вопрос гораздо сложнее, чем кажется на первый взгляд. Существует множество тестов случайности. Для начала можно почитать Кнута, а потом поискать в Интернете.

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

[В.О.]

Руст в сообщении #396695 писал(а):

последовательность из них назовем случайным, если для любой последовательности цифр длины
среди последовательности N цифр после цифр (т.е. среди цифр с номерами от до количество встреч такой последовательности a находится в интервале
где . В случае равномерности появления цифр

Это и есть закон больших чисел с некоторой оценкой точности.

[Lesobrod]

Так. Во-первых, разобрался в нормальности и понял, что мой критерий -
это критерий абсолютной нормальности, а не случайности.
Кнутом займусь.
Но какие в результате критерии (не)случайности предложила почтенная публика?
1. Вычислимость с помощью алгоритма$\equiv$ неслучайность. Честно говоря,я и сам так думал, но что-то здесь не то.
Ведь программа, вычисляющая $\pi$, скажем, в 30 раз больше проги, генерирующей числа Фибоначчи.
Т.е. последние в 30 раз менее случайны, чем цифры $\pi$?
2. Выполнение закона больших чисел, ЦПТ. Проверим, в смысле и для $\pi$,и для псевдослучайных.
Ну а как же всё-таки энтропия? Неужели она здесь не при делах?
И, может, кто-нибудь выскажет мнение насчёт такой последовательности:
Остатки от деления простых чисел на данное простое.
Если делителем брать, скажем, 17, а простые начинать после 1000, получается завораживающе случайная(? ) последовательность. Есть ли какие-то строгие результаты по ней?

[Руст]

Lesobrod в сообщении #396910 писал(а):

Так.
Остатки от деления простых чисел на данное простое.
Если делителем брать, скажем, 17, а простые начинать после 1000, получается завораживающе случайная(? ) последовательность. Есть ли какие-то строгие результаты по ней?

Если брать остатки при делении на $m$, то случайность эквивалентна обобщенной гипотезе Римана - пока не доказанный факт, но вполне правдаподобное утверждение.

[Lesobrod]

О, йес. Книга Дербишира "Простая одержимость"
считается попсовой, однако, если отбросить лирику, вопрос вычисления простых чисел там доведен до конца. Вы согласны, Руст, что
Случайность(?какая?) распределения нетривиальных корней Дзета-функции $\Rightarrow$ Случайность(такая же) в поведении простых ?
И здесь есть одна тонкость. И корни, и простые числа имеют тренды - неслучайные закономерности (всё большая разреженность, например).
Вот мне очень интересно, насколько операция деления с остатком
убирает эти тренды, оставляя случайность простых чисел в чистом, так сказать, виде?

[hurtsy]

Руст в сообщении #396695 писал(а):

Что касается цифр числа $\pi$, то думаю, что это действительно случайная последовательность, только мы не умеем доказывать.

Умеем, не умеем тут не в этом дело. Существует вероятностный(случайный) алгоритм, которым морские капитаны определяли число $\pi$, бросание иголки на палубу. Он правда медленно сходится. Тем не менее $\pi$ всего навсего константа хоть и трансцендентная. Для случайной величины мощность пространства елементарных событий может быть равной 2. С уважением,

[Lesobrod]

Ну, очень похоже, что наша Вселенная - это всего навсего пузырёк в кипящем вакууме. То что в простой константе скрыто много чего интересного, по моему скромному мнению, совсем не удивительно.