Определить, является ли последовательность чисел случайна

[germ9c]

Здравствуйте, подскажите пожалуйста, нужно определить, является ли последовательность чисел случайна (т.е нерегулярные данные)
Интересует теоретическая и практическая часть
Может названия тестов есть

p.s последовательность состоящая из 1,2,3,4 чисел, последовательность например - 12343241.., это задание не используется в криптографии

[Someone]

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

[demolishka]

Есть доступные видеолекции В. И. Арнольда на эту тему.

[ozheredov]

demolishka

Посмотрел внимательно лекцию. Вопрос по колмогоровскому критерию (таймкод 1:08): это вроде как супремум отклонения считающей ф-ции от ТЕОРЕТИЧЕСКОГО распределения, и распределение этого супремума в пределе не зависит от этого теор. распределения. Но сам то супремум зависит, что бы его посчитать нужно распределение иксов. Откуда его брать???

[iifat]

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

[Евгений Машеров]

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

[demolishka]

ozheredov в сообщении #1320502 писал(а):

Посмотрел внимательно лекцию. Вопрос по колмогоровскому критерию (таймкод 1:08): это вроде как супремум отклонения считающей ф-ции от ТЕОРЕТИЧЕСКОГО распределения, и распределение этого супремума в пределе не зависит от этого теор. распределения. Но сам то супремум зависит, что бы его посчитать нужно распределение иксов. Откуда его брать???

Во второй лекции (таймкод 31м 40с) упоминается эта проблема. Предлагается брать две выборки и брать разность между соответствующими реализациями.

Если у Вас есть конкретная задача, то все же сформулируйте ее. Будет легче помочь.

[GAA]

На мой взгляд, случайность чаще всего понимают в двух смыслах:
1. Элементы выборки независимые и одинаково распределённые случайные величины.
2. (Для случая дискретных случайных величин. Частный случай пред.) Элементы выборки независимые и одинаково полиномиально распределённые случайные, вероятности всех значений случайной величины равны. *)

Если известно, что элементы выборки независимые и одинаково распределённые случайные величины, то для проверки гипотезы о равенстве вероятностей (каждого значения всех значений) можно использовать критерий $\chi^2$. Для малых объёмов выборки распределение статистики легко вычислить, а при больших объёмах можно воспользоваться асимптотическим распределением. Т.е. для «смысла 2» имеется, по крайней мере, один широко известный критерий.

А какие имеются критерии для «смысла 1» в случае дискретных распределений?
Вроде бы критерии в основном разрабатывались для непрерывных распределений. [В Лемешко Б.Ю., Веретельникова И.В. «Критерии проверки гипотез о случайности и отсутствии тренда» (pdf) можно найти список большого числа критериев, анализ и ссылки.]

________________
*) Примеры двух ближайших аналогов для случая непрерывной случайной величины.

Элементы выборки независимые и одинаково равномерно распределённые на некотором промежутке («отрезке») случайные величины. Если промежуток задан (простая гипотеза) — то можно применить критерий согласия Колмогорова (одновыборочный критерий Колмогорова — Смирнова). В первой лекции В. И. Арнольда, возможно об этом идёт речь. Если отрезок не задан (не известны параметры, сложная гипотеза), то — модификацию критерия Колмогорова.

Критерий же однородности Колмогорова — Смирнова (двухвыборочный критерий Колмлгорова — Смирнова) предполагает, что обе выборки {$X_i$, $i =1,\ldots, n$, $Y_j$, $j = 1, \ldots, m$} — это независимые и одинаково распределённые случайные величины, а основная гипотеза состоит в том, что функции распределения $X_1$ и $Y_1$ совпадают (по-другому: случайные величины $X_1$ и $Y_1$ имеют одинаковое распределение). Т.е. это к «смыслу 2» слабо подходит.

Другой пример из области непрерывных случайных величин рассмотрен в первом томе книги Феллера «Введение в теорию вероятностей и её приложения», § Примеры схем, приводящие к распределению Пуассона: «Разрывы самолётов-снарядов в Лондоне». Предположение о том, что число падений на участки с одинаковой площадью имеют распределение Пуассона и использование критерия $\chi^2$ позволило сделать вывод: «точки падения были совершенно случайными, все участки равноправные».

[ozheredov]

Евгений Машеров

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

[Евгений Машеров]

Я бы сказал, что есть действительно два понимания "случайности", но не совсем такие. Это либо "непредсказуемость", особо важная, скажем, в криптографии, либо свойственные случайным величинам статистические свойства (некоррелированность, равномерная распределённость и т.п.), что важнее для Монте-Карло. Причём эти два критерия, выполняясь оба на бесконечных выборках случайных величин, на конечных выборках могут противоречить друг другу.

[GAA]

Евгений Машеров, о названиях спорить не буду. Если интересно, то термин гипотеза случайности можно найти, например в
Ивченко Г.И., Медведев Ю.И. Математическая статистика, 1984.
Ивченко Г.И., Медведев Ю.И. Введение в математическую статистику, 2010.
(И многих других книгах, например Химмельблау «Анализ процессов статистическими методами», 1970).

В §4.5 Критерии случайности «Введения.. » Ивченко и Медведева есть п. 2 «Проблема датчиков и обобщённый хи-квадрат». Вот там описан критерий, который, видимо, подойдёт автору вопроса.
Я этот критерий не пробовал.

-- Mon 18.06.2018 15:45:52 --

Это к было к смыслу 1. А смысл 2..., ну жаргон конечно. И понятно когда он уместен --- когда заранее известно, что случайные величины независимы и одинаково распределены, а нужно проверить только равновозможность всех значений.

-- Mon 18.06.2018 15:58:21 --

А о "непредсказуемости" я вообще не думал (криптографии и т.п.) и об этом не писал, поскольку ТС в начальном сообщении это исключил.