Тест последовательности на случайность

[sergey zhukov]

Dmitriy40 в сообщении #1428363 писал(а):

По моему как раз очевидно что любую структуру конечного размера вполне обработать алгоритмом конечной сложности

Как я понял, этот алгоритм как раз не должен быть способен описать все возможные подпоследовательности. Иначе он может выбрать, скажем, только нули. Такого алгоритма по определению случайной последовательности быть не должно. Мне понятно, что конечный алгоритм не описывает все подпоследовательности, но бесконечный - не очевидно.

[Dmitriy40]

sergey zhukov в сообщении #1428379 писал(а):

Мне понятно, что конечный алгоритм не описывает все подпоследовательности,

А вот мне понятно ровно наоборот, что описать все возможные подпоследовательности конечной длины вполне возможно конечным алгоритмом. Ведь их количество конечно.

sergey zhukov в сообщении #1428379 писал(а):

но бесконечный

А это вообще не алгоритм, см. главу 1.1 пункт 1) Конечность.

sergey zhukov в сообщении #1428379 писал(а):

Dmitriy40 в сообщении #1428363 писал(а):

По моему как раз очевидно что любую структуру конечного размера вполне обработать алгоритмом конечной сложности

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

Как-то ровно наоборот Вы поняли. В R6 прямо сказано, что если для любого эффективного (и конечного разумеется) алгоритма вычисления $s(n,X_1,X_2,...,X_n)=...$ результирующая выборка из последовательности $X_{i=1..N}$ подпоследовательность $X_{s_n}$ будет случайной в смысле R5, то и сама $X_{i=1..N}$ является случайной (в том же смысле). Поэтому ни для какого алгоритма вычисления $s()$ невозможно выбрать лишь нули из $X_{i=1..N}$ если она случайная. Даже если алгоритм учитывает все возможные подпоследовательности $X_{s_{i=1..n}}$ (разумеется конечной длины), что он вполне имеет право делать, ведь все они ему доступны как аргументы $s(n,X_1,...,X_n)$.
В том и суть, что для любого алгоритма из действительно случайной последовательности невозможно выбрать лишь нули (или любую другую структуру с заранее заданными свойствами кроме случайной), даже анализируя на каждом шаге полную историю - всегда будет получаться случайная (в смысле R5) последовательность.

[sergey zhukov]

Dmitriy40 в сообщении #1428393 писал(а):

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

С этим я согласен полностью. Мне не совсем понятны возможности алгоритма, берущего на вход всю собственную продукцию. Например, с одной стороны $\sqrt{2}$ не является случайной последовательностью, т.к. она может быть предсказана таким алгоритмом (или же не может? Возможно ли вычислять иррациональную последовательность цифра за цифрой так, чтобы каждая полученная цифра тут же становилась окончательной?). С другой стороны, она случайная, т.к. нет алгоритма, который сможет выбрать из этой последовательности, скажем, только нули.

[Dmitriy40]

sergey zhukov в сообщении #1428407 писал(а):

Возможно ли вычислять иррациональную последовательность цифра за цифрой так, чтобы каждая полученная цифра тут же становилась окончательной?

Вполне возможно, при этом цифра $k$ даёт приближение по недостатку или равенству, а цифра $k+1$ даёт приближение по избытку. Собственно это вроде как даже одно из определений действительных чисел ... Правда есть неоднозначность для чисел вида $...{,}...(9)$, но она устраняется "силовым методом".
Например для вашего $\sqrt{2}$ третью цифру можно предсказать точно: $1{,}41 \leqslant \sqrt{2} < 1{,}42$, т.е. третья цифра точно $1$. Аналогично и остальные цифры. И алгоритм проверки (вычисления) любой цифры по имеющимся предыдущим и её номеру вполне себе конечен.

sergey zhukov в сообщении #1428407 писал(а):

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

Почему нет, есть: для любого входного $n$ вычисляем цифры одну за другой и если натыкаемся $n$ раз на ноль, то выдаём позицию последнего полученного в качестве $s_n$. Алгоритм детерминирован, конечен для любого $n$ (если количество нулей в записи не меньше $n$ разумеется, это надо доказывать отдельно), выдаёт только нули, и даже $s_n$ строго возрастающая. Предыдущие $s_{1..n-1}$ не используются, ну так и не обязаны, лишь допустимы, хотя наверное можно и использовать для оптимизации алгоритма. И потому последовательность цифр в записи $\sqrt{2}$ не случайна.

[sergey zhukov]

Кнут правильно сказал: случайная последовательность должна пройти бесчисленное количество тестов на случайность, и после прохождения каждого теста вероятность, что она случайна, увеличивается. На практике невозможно доказать случайность некоторой последовательности. Можно лишь доказать ее не случайность.

[Dmitriy40]

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

[sergey zhukov]

А насколько состоятельно определение конечной случайной последовательности, как такой последовательности, которую невозможно записать короче, чем она сама? Насколько я понимаю, это определение по Колмогорову.

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

Похоже, что на практике мы получим следующее: в конце сжатия последовательность по прежнему сохраняет некоторые неслучайные элементы, но самое короткое правило, которое их описывает - это исключение из правила, т.е. приведение этих элементов в оригинальном виде.