2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Определить, является ли последовательность чисел случайна
Сообщение16.06.2018, 17:46 


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

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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение16.06.2018, 17:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение16.06.2018, 18:50 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение17.06.2018, 05:42 


10/03/16
3995
Aeroport
demolishka

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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение17.06.2018, 06:44 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение17.06.2018, 10:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение17.06.2018, 18:17 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение17.06.2018, 21:25 
Заслуженный участник


12/07/07
4448
На мой взгляд, случайность чаще всего понимают в двух смыслах:
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$ позволило сделать вывод: «точки падения были совершенно случайными, все участки равноправные».

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение18.06.2018, 00:15 


10/03/16
3995
Aeroport
Евгений Машеров

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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение18.06.2018, 09:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Определить, является ли последовательность чисел случайна
Сообщение18.06.2018, 16:42 
Заслуженный участник


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

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

-- Mon 18.06.2018 15:45:52 --

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

-- Mon 18.06.2018 15:58:21 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group