Тест на случайность - Randomness test

Не путать с рандомизированным тестом .

Тест на случайность (или тест на случайность ) при оценке данных - это тест, используемый для анализа распределения набора данных, чтобы увидеть, можно ли его описать как случайное (без шаблонов). В стохастическом моделировании , как и в некоторых компьютерных моделированиях , ожидаемая случайность потенциальных входных данных может быть проверена с помощью формального теста на случайность, чтобы показать, что данные действительны для использования в прогонах моделирования. В некоторых случаях данные обнаруживают очевидную неслучайную закономерность, как в случае так называемых «прогонов в данных» (например, ожидание случайных значений 0–9, но обнаружение «4 3 2 1 0 4 3 2 1 ...» и редко выше 4). Если выбранный набор данных не проходит тесты, можно изменить параметры или использовать другие рандомизированные данные, которые проходят тесты на случайность.

Фон

Проблема случайности - важный философский и теоретический вопрос. Тесты на случайность могут использоваться, чтобы определить, имеет ли набор данных распознаваемый образец, который указывал бы на то, что процесс, который его сгенерировал, в значительной степени неслучайен. По большей части статистический анализ на практике был гораздо больше озабочен поиском закономерностей в данных, чем проверкой случайности. Многие «генераторы случайных чисел», используемые сегодня, определяются алгоритмами, и поэтому фактически являются генераторами псевдослучайных чисел. Создаваемые ими последовательности называются псевдослучайными последовательностями. Эти генераторы не всегда генерируют последовательности, которые являются достаточно случайными, но вместо этого могут создавать последовательности, содержащие шаблоны. Например, печально известная процедура RANDU резко терпит неудачу во многих тестах на случайность, включая спектральный тест.

Стивен Вольфрам использовал тесты случайности на выходе правила 30, чтобы изучить его потенциал для генерации случайных чисел, хотя было показано, что эффективный размер ключа намного меньше, чем его фактический размер, и плохо справляется с тестом хи-квадрат . Использование непродуманного генератора случайных чисел может поставить под сомнение достоверность эксперимента, нарушив статистические допущения. Хотя существуют широко используемые методы статистического тестирования, такие как стандарты NIST, Юнгге Ван показал, что стандартов NIST недостаточно. Кроме того, Юнгге Ван разработал методы тестирования, основанные на статистических расстояниях и законах повторного логарифма. Используя эту технику, Юнгге Ван и Тони Никол обнаружили слабые места в часто используемых генераторах псевдослучайных ситуаций, таких как хорошо известная версия Debian генератора псевдослучайных ошибок OpenSSL, которая была исправлена ​​в 2008 году.

Специальные тесты на случайность

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

Эти разные генераторы с разной степенью успешности проходят принятые наборы тестов. Несколько широко используемых генераторов более или менее плохо проходят тесты, в то время как другие «лучшие» и предшествующие генераторы (в том смысле, что они прошли все текущие тесты и уже существовали) в значительной степени игнорировались.

Есть много практических мер случайности для двоичной последовательности . К ним относятся меры, основанные на статистических тестах , преобразованиях и сложности, или на их сочетании. Хорошо известным и широко используемым сборником тестов была «Батарея жестких тестов» , представленная Марсалья; это было расширено до TestU01 Suite L'Ecuyer и Simard. Использование преобразования Адамара для измерения случайности было предложено С.Каком и развито в дальнейшем Филлипсом, Юэном, Хопкинсом, Бет и Дай, Мундом и Марсаглия и Заман.

Некоторые из этих тестов, которые имеют линейную сложность, обеспечивают спектральные меры случайности. T. Beth и ZD. Дай стремился показать, что сложность Колмогорова и линейная сложность практически одинаковы, хотя Ю. Ван позже показал, что их утверждения неверны. Тем не менее Ван также продемонстрировал, что для случайных последовательностей Мартина-Лёфа колмогоровская сложность по существу такая же, как и линейная сложность.

Эти практические тесты позволяют сравнивать случайность строк . С точки зрения вероятности, все строки заданной длины имеют одинаковую случайность. Однако разные струны имеют разную колмогоровскую сложность. Например, рассмотрим следующие две строки.

Строка 1: 01010101010101010101010101010101010101010101010101010101010101
Строка 2: 1100100001100001110111101110110011111010010000100101011110010110

Строка 1 допускает краткое лингвистическое описание: «32 повторения '01'». Это описание состоит из 22 символов и может быть эффективно построено из некоторых базовых последовательностей. Строка 2 не имеет очевидного простого описания, кроме записи самой строки, которая состоит из 64 символов, и не имеет сравнительно эффективного представления базовой функции . Используя линейные спектральные тесты Адамара (см. Преобразование Адамара ), будет обнаружено, что первая из этих последовательностей имеет гораздо меньшую случайность, чем вторая, что согласуется с интуицией.

Известные реализации программного обеспечения

  • Живучи
  • TestU01
  • Утилита ent от Fourmilab
  • Набор статистических тестов NIST (специальная публикация 800-22, редакция 1a)

Смотрите также

Примечания

внешние ссылки