Тест на случайность (или тест на случайность ) в оценке данных — это тест, используемый для анализа распределения набора данных, чтобы увидеть, можно ли его описать как случайный (не имеющий закономерности). В стохастическом моделировании , как и в некоторых компьютерных симуляциях , ожидаемая случайность потенциальных входных данных может быть проверена с помощью формального теста на случайность, чтобы показать, что данные пригодны для использования в прогонах моделирования. В некоторых случаях данные показывают очевидную неслучайную закономерность, как в так называемых «прогонах в данных» (например, ожидание случайных 0–9, но обнаружение «4 3 2 1 0 4 3 2 1...» и редкое превышение 4). Если выбранный набор данных не проходит тесты, то можно изменить параметры или использовать другие рандомизированные данные, которые проходят тесты на случайность.
Вопрос случайности является важным философским и теоретическим вопросом. Тесты на случайность могут использоваться для определения того, имеет ли набор данных узнаваемый шаблон, который будет указывать на то, что процесс, который его сгенерировал, в значительной степени не случаен. По большей части статистический анализ на практике был гораздо больше озабочен поиском закономерностей в данных, а не проверкой на случайность. Многие «генераторы случайных чисел», используемые сегодня, определяются алгоритмами и поэтому фактически являются генераторами псевдослучайных чисел. Последовательности, которые они производят, называются псевдослучайными последовательностями. Эти генераторы не всегда генерируют последовательности, которые являются достаточно случайными, но вместо этого могут производить последовательности, которые содержат шаблоны. Например, печально известная процедура RANDU резко проваливает многие тесты на случайность, включая спектральный тест .
Стивен Вольфрам использовал тесты случайности на выходе Правила 30 , чтобы изучить его потенциал для генерации случайных чисел, [1] хотя было показано, что он имеет эффективный размер ключа, намного меньший, чем его фактический размер [2] и плохо работает на тесте хи-квадрат . [3] Использование плохо продуманного генератора случайных чисел может поставить под сомнение обоснованность эксперимента, нарушив статистические предположения. Хотя существуют широко используемые статистические методы тестирования, такие как стандарты NIST, Юнге Ван показал, что стандарты NIST недостаточны. Кроме того, Юнге Ван [4] разработал методы тестирования, основанные на статистическом расстоянии и законе итерационного логарифма. Используя этот метод, Юнге Ван и Тони Никол [5] обнаружили слабость в широко используемых псевдослучайных генераторах, таких как хорошо известная версия псевдослучайного генератора OpenSSL для Debian, которая была исправлена в 2008 году.
На практике использовалось довольно небольшое количество различных типов генераторов (псевдо-)случайных чисел. Их можно найти в списке генераторов случайных чисел , и они включают:
Эти различные генераторы имеют разную степень успеха в прохождении принятых наборов тестов. Несколько широко используемых генераторов проваливают тесты более или менее плохо, в то время как другие «лучшие» и предыдущие генераторы (в том смысле, что они прошли все текущие батареи тестов и они уже существовали) были в значительной степени проигнорированы.
Существует множество практических мер случайности для двоичной последовательности . К ним относятся меры, основанные на статистических тестах , преобразованиях и сложности или их смеси. Хорошо известным и широко используемым набором тестов был Diehard Battery of Tests , представленный Марсальей; он был расширен до набора TestU01 Л'Экуайером и Симаром. Использование преобразования Адамара для измерения случайности было предложено С. Каком и далее развито Филлипсом, Юэном, Хопкинсом, Бет и Даем, Мундом, Марсальей и Заманом. [6]
Некоторые из этих тестов, имеющих линейную сложность, предоставляют спектральные меры случайности. Т. Бет и З. Д. Дай намеревались показать, что сложность Колмогорова и линейная сложность практически одинаковы, [7] хотя позже И. Ван показал, что их утверждения неверны. [8] Тем не менее, Ван также продемонстрировал, что для случайных последовательностей Мартина-Лёфа сложность Колмогорова по сути такая же, как и линейная сложность.
Эти практические тесты позволяют сравнивать случайность строк . По вероятностным основаниям, все строки заданной длины имеют одинаковую случайность. Однако разные строки имеют разную сложность Колмогорова. Например, рассмотрим следующие две строки.
01010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110Строка 1 допускает короткое лингвистическое описание: «32 повторения '01'». Это описание содержит 22 символа, и его можно эффективно построить из некоторых базисных последовательностей. [ необходимо разъяснение ] Строка 2 не имеет очевидного простого описания, кроме записи самой строки, которая содержит 64 символа, [ необходимо разъяснение ] и не имеет сравнительно эффективного представления базисной функции . Используя линейные спектральные тесты Адамара (см. преобразование Адамара ), будет обнаружено, что первая из этих последовательностей имеет гораздо меньшую случайность, чем вторая, что согласуется с интуицией.