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

[sergey zhukov]

Допустим, имеем бинарную последовательность. Достаточно ли равномерного распределения элементов этой последовательности независимо от того, что мы считаем ее элементом, чтобы последовательность была максимально случайной (вероятность предсказания следующего бита 0.5)?

Например, если за элемент последователбности взять бит, то 0 и 1 должны иметь равную частоту встречаемости. Если за элемент взять два бита, то элементы 00, 01, 10 и 11 должны иметь равную частоту встречаемости и т.д.

[arseniiv]

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

(вероятность предсказания следующего бита 0.5)

Это как? Последовательность у нас одна, и мы в принципе можем её просто заучить и выдавать в точности — как именно предполагается предсказывать?

Так понимаю, эта тема вызвана упомнанием мной статистических тестов случайности в другой. Если так, то сошлю на https://en.wikipedia.org/wiki/Randomness_tests или https://en.wikipedia.org/wiki/Statistical_randomness#Tests.

Ещё есть колмогоровская сложность последовательности.

[Dmitriy40]

А ещё есть последовательность де Брёйна, которая для элементов конечной длины $n$ содержит по одному их вхождению и равные количества вхождений элементов меньшей длины. Т.е. все элементы длины $n$ и менее - равновероятны, однако не случайны.

[sergey zhukov]

arseniiv в сообщении #1427257 писал(а):

Это как? Последовательность у нас одна, и мы в принципе можем её просто заучить и выдавать в точности — как именно предполагается предсказывать?

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

Как мне кажется, универсальный статистический алгоритм предсказания бита $x$ следующий:
1. Если частота единиц выше, чем частота нулей - предсказываем единицу (и наоборот);
2. Если они равны, рассматриваем пару предсказываемый $+$ последний бит (допустим, это $0x$) и находим частоту для пар 00, 01. Предсказываем ту пару, частота которой выше;
3. Если они равны, рассматриваем последнюю тройку бит (допустим, это $10x$) и находим частоту для троек 100 и 101. И т.д.

Этот алгоритм не позволяет ничего предсказывать, только если частоты всех элементов, пар, троек и т.д. равны. Как-то я написал такой алгоритм, он должен был угадать число (0 или 1), которое я загадываю. Он выигрывает.
Можно сказать шире: последовательность случайна, если при утрате любого ее элемента его правильное восстановление возможно только с вероятностью 0,5.

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

А ещё есть последовательность де Брёйна

Как я понял, эта последовательность имеет два параметра: число разных элементов $k$, из которых она будет состоять (например, 2 для бинарной последовательности) и размер $n$ подпоследовательности, все возможные варианты которой можно по одному разу обнаружить в этой последовательности. Это не совсем то, что нужно, т.к. случайная последовательность, по моему, должна быть последовательностью де Брёйна сразу для всех возможных $n$.

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

Объясняется ли это тем, что при попытке вычислить иррациональное число по известной формуле, мы будем вынуждены использовать алгоритм, который будет занимать в памяти места не меньше, чем уже вычисленная последовательность? (Он должен будет использовать уже вычисленный ряд цифр для продолжения вычислений). Т.е. эта компактная формула не так уж компактна, а под размером алгоритма нужно понимать не только саму формулу, но и объем данных, которыми она оперирует?

[arseniiv]

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

Как мне кажется, универсальный статистический алгоритм предсказания бита $x$ следующий:
1. Если частота единиц выше, чем частота нулей - предсказываем единицу (и наоборот);
2. Если они равны, рассматриваем пару предсказываемый $+$ последний бит (допустим, это $0x$) и находим частоту для пар 00, 01. Предсказываем ту пару, частота которой выше;
3. Если они равны, рассматриваем последнюю тройку бит (допустим, это $10x$) и находим частоту для троек 100 и 101. И т.д.

Этот алгоритм не позволяет ничего предсказывать, только если частоты всех элементов, пар, троек и т.д. равны. Как-то я написал такой алгоритм, он должен был угадать число (0 или 1), которое я загадываю. Он выигрывает.
Можно сказать шире: последовательность случайна, если при утрате любого ее элемента его правильное восстановление возможно только с вероятностью 0,5.

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

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

Существует ли способ при помощи статистического анализа последовательности понять, что перед нами, скажем, $\sqrt{2}$?

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

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

Объясняется ли это тем, что при попытке вычислить иррациональное число по известной формуле, мы будем вынуждены использовать алгоритм, который будет занимать в памяти места не меньше, чем уже вычисленная последовательность? (Он должен будет использовать уже вычисленный ряд цифр для продолжения вычислений). Т.е. эта компактная формула не так уж компактна, а под размером алгоритма нужно понимать не только саму формулу, но и объем данных, которыми она оперирует?

Что именно объясняется, не понял, но действительно известно, что если $S$ конечно, то последовательность $s, f(s), f(f(s)), \ldots$ для $s\in S$, $f\colon S\to S$ обязательно зациклится, и уж тем более последовательность $g(s), g(f(s)), g(f(f(s))), \ldots$, где $g$ например выдаёт очерендую цифру числа, а $S$ — множество состояний памяти, доступной алгоритму $f$. Так что памяти для вывода произвольной цифры некоторого иррационального числа потребуется действительно неограниченное количество. Но статистическая случайность с периодичностью связана не так уж вроде прямо.

[Someone]

sergey zhukov, Вы не пробовали читать Д. Кнута? Я имею в виду второй том его "Искусства программирования для ЭВМ". Там есть обсуждение вопроса о том, что такое случайная последовательность.

[Dmitriy40]

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

Это не совсем то, что нужно, т.к. случайная последовательность, по моему, должна быть последовательностью де Брёйна сразу для всех возможных $n$.

Вы не дочитали, я же сразу сказал что она является собой же и для всех меньших $n$. В смысле что все меньшие объекты тоже равновероятны, как Вы и хотели.
Я правда не полностью уверен что биты в ней строго детерменированы (особенно при $n \to +\infty$), но они явно не случайны, что и требовалось для контрпримера.

[sergey zhukov]

arseniiv в сообщении #1427385 писал(а):

Что именно объясняется, не понял,

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

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

Вы не пробовали читать Д. Кнута?

Интересная книга. Оказывается, все сложнее, чем я думал.
Кнут сначала рассматривает в качестве случайной двоичную последовательность, в которой все индивидуальные элементы, их пары, тройки и т.д. до $\infty$ имеют равномерное распределение ($\infty$-распределенная последовательность). Но если взять из такой последовательности только члены с определенными номерами (скажем, с номерами $n^2$), то составленная из них последовательность может не быть случайной, хотя нам ясно, что истинно случайная последовательность $A$ должна быть подобна любой своей подпоследовательности, члены которой набраны из $A$ при помощи любого алгоритма от $n$, (включая и зависимость от членов уже набранной последовательности).
Тогда предлагается считать последовательность случайной тогда, когда любая, набранная из нее произвольным способом другая последовательность $\infty$-распределена.
В таком случае, тест последовательности $A$ на случайность заключается в проверке на $\infty$-распределенность не только ее самой, но и всех возможных подпоследовательностей, составленных из членов, извлеченных из $A$ в любом порядке.

[Someone]

Могу порекомендовать ещё две книги.
Г.-Д. Эббинхауз, К. Якобс, Ф.-К. Ман, Г. Хермес. Машины Тьюринга и рекурсивные функции. "Мир", Москва, 1972.
Ф. Ю. Хренников. Неколмогоровские теории вероятностей и квантовая физика. Москва, Физматлит, 2003.

[sergey zhukov]

Хотел бы уточнить определение случайной последовательности, которое я извлек из Кнута.

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

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

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

[Dmitriy40]

sergey zhukov
Дайте точную ссылку (номер раздела и точные его слова или номер определения/теоремы/формулы) где Кнут это говорит. При беглом просмотре третьей главы я таких слов не нашёл.
По идее знание предыстории любой длины не влияет на следующий бит (карточку) и не должно смещать вероятности.

[sergey zhukov]

Глава 3.5 "Что такое случайная последовательность". Почти полностью посвящена тому, что я тут пересказал.

1. Определение R1 в качестве первого приближения берет за случайную последовательность просто $\infty$-распределенную. Далее замечается, что это слишком слабое определение. Можно сконструировать такие $\infty$-распределенные последовательности, подпоследовательности которых (выборки из нее, сделанные по определенному правилу) не только не $\infty$-распределенные, но даже и не случайные.
3. Определение R3 усиливает R1 тем, что требует, чтобы любая подпоследовательность исходной случайной последовательности была $\infty$-распределенна. Однако это явно невозможно: ведь из последовательности всегда можно выбрать одни только нули или одни только единицы.
4. Определение R4 уточняет, что "любая подпоследовательность" должна быть определена алгоритмом выборки, который сам по себе есть нечто ограниченное и конечное (эффективный алгоритм). Выборка одних только нулей или одних только единиц из случайной последовательности не описывается таким алгоритмом. Однако это определение допускает зависимость алгоритма выборки от всех элементов исходной последовательности, даже от тех, которые в итоге не войдут в набранную подпоследовательность (так я это понял, не уверен, что правильно).
5. Определение R5 (совместно с R6) уточняет, что этот алгоритм должен зависеть не от всех элементов исходной последовательности, а только от тех, которые в итоге войдут в определяемую подпоследовательность (перевернутые карточки). Определение R6 по сути определяет некоторую не монотонную выборку элементов и отсылает ее к R5, которое сформулировано так, что определяет только монотонные выборки (т.е. выбирает такие члены исходной последовательности, что их номера только возрастают). Совместно они определяют все возможные выборки.
6. Попутно выясняется, что достаточно потребовать от каждой такой подпоследовательности только 1-распределения вместо $\infty$-распределения. Если все такие подпоследовательности будут 1-распределены, то все они будут и $\infty$-распределены.

Все это можно свести к определению того, карточку с каким номером $S_n$ перевернуть следующей, если уже перевернуто $n-1$ карточек с номерами $S_0...S_{n-1}$ и на них имеются значения $M_0...M_S_{n-1}$. Здесь $n$ - номер члена исходной случайной последовательности.

[Dmitriy40]

Кнут тут говорит не "хорошо определён", а "эффективная процедура/алгоритм", в смысле вычислимости каждого шага за конечное время (см. п.1.1, пункт 5 Эффективность).
И в R6 функции определены лишь на конечном множестве уже открытых карточек.
Потому нет, Ваша интерпретация

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

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

неправильна, ведь именно так функция $s_n$ и определена и об этом прямо сказано. Просто $n$ может быть произвольно (неограниченно) большим, но обязательно конечным ($n < +\infty$), вот и всё.

Аналогия: функция $fib(n)=fib(n-1)+fib(n-2), fib(0)=0, fib(1)=1,\, 1<n \in \mathbb{N}$, задающая последовательность Фибоначчи, тоже эффективно задаёт бесконечную последовательность чисел, но зависит лишь от конечного числа "параметров" (предыдущих членов последовательности и $n$). Ровно как и в последовательности R6 у Кнута.

[sergey zhukov]

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

Просто $n$ может быть произвольно (неограниченно) большим, но обязательно конечным ($n < +\infty$)

Да, да. Верно. Я вначале так и думал, но меня сбило с толку, что в этом случае алгоритм получается неограничено сложным и не очевидно, что он не может охватить вообще все возможные подпоследовательности.

[Dmitriy40]

Ну неограниченно сложным, что ж тут такого, ведь всё равно конечной.
А количество всех возможных подпоследовательностей тоже конечно (для любого фиксированного $n$ разумеется). Так что нет теоретических препятствий их все учесть (о практике промолчим, там много нюансов). По моему как раз очевидно что любую структуру конечного размера вполне обработать алгоритмом конечной сложности, что как раз и заложено в $O()$ нотацию.