Тест на случайность (или тест на случайность ) при оценке данных - это тест, используемый для анализа распределения набора данных, чтобы увидеть, можно ли его описать как случайное (без шаблонов). В стохастическом моделировании , как и в некоторых компьютерных симуляциях, ожидаемая случайность потенциальных входных данных может быть проверена с помощью формального теста на случайность, чтобы показать, что данные пригодны для использования в прогонах моделирования. В некоторых случаях данные обнаруживают очевидный неслучайный паттерн, как в случае так называемых «прогонов в данных» (например, ожидание случайных значений 0–9, но обнаружение «4 3 2 1 0 4 3 2 1 ...» и редко выше 4). Если выбранный набор данных не проходит тесты, можно изменить параметры или использовать другие рандомизированные данные, которые проходят тесты на случайность.
Задний план
Проблема случайности - важный философский и теоретический вопрос. Тесты на случайность могут использоваться для определения того, имеет ли набор данных распознаваемый образец, который указывал бы на то, что процесс, который его сгенерировал, в значительной степени неслучайен. По большей части статистический анализ на практике был гораздо больше озабочен поиском закономерностей в данных, чем проверкой случайности. Многие «генераторы случайных чисел», используемые сегодня, определяются алгоритмами, и поэтому фактически являются генераторами псевдослучайных чисел. Создаваемые ими последовательности называются псевдослучайными последовательностями. Эти генераторы не всегда генерируют последовательности, которые являются достаточно случайными, но вместо этого могут создавать последовательности, содержащие шаблоны. Например, печально известная процедура RANDU резко не выдерживает многих тестов на случайность, включая спектральный тест.
Стивен Вольфрам использовал тесты случайности на выходе правила 30, чтобы изучить его потенциал для генерации случайных чисел [1], хотя было показано, что эффективный размер ключа намного меньше его фактического размера [2], и он плохо справляется с задачей. квадратный тест . [3] Использование непродуманного генератора случайных чисел может поставить под сомнение достоверность эксперимента, нарушив статистические допущения. Хотя существуют широко используемые методы статистического тестирования, такие как стандарты NIST, Юнгге Ван показал, что стандартов NIST недостаточно. Кроме того, Юнгге Ван [4] разработал методы тестирования, основанные на статистических расстояниях и законах повторного логарифма. Используя эту технику, Юнгге Ван и Тони Никол [5] обнаружили слабые места в часто используемых генераторах псевдослучайных ситуаций, таких как хорошо известная версия Debian генератора псевдослучайных ошибок OpenSSL, которая была исправлена в 2008 году.
Специальные тесты на случайность
На практике используется довольно небольшое количество различных типов генераторов (псевдо) случайных чисел. Их можно найти в списке генераторов случайных чисел , и они включают:
- Линейный конгруэнтный генератор и регистр сдвига с линейной обратной связью
- Обобщенный генератор Фибоначчи
- Криптографические генераторы
- Квадратичный конгруэнтный генератор
- Генераторы клеточных автоматов
- Псевдослучайная двоичная последовательность
Эти разные генераторы с разной степенью успешности проходят принятые наборы тестов. Несколько широко используемых генераторов более или менее плохо проходят тесты, в то время как другие «лучшие» и предшествующие генераторы (в том смысле, что они прошли все текущие тесты и уже существовали) в значительной степени игнорировались.
Есть много практических мер случайности для двоичной последовательности . К ним относятся меры, основанные на статистических тестах , преобразованиях и сложности, или на их сочетании. Хорошо известным и широко используемым сборником тестов была «Батарея тестов несгибаемости» , представленная Марсалья; это было расширено до пакета TestU01 L'Ecuyer и Simard. Использование преобразования Адамара для измерения случайности было предложено С.Каком и развито в дальнейшем Филлипсом, Юэном, Хопкинсом, Бет и Дай, Мундом, Марсаглия и Заман. [6]
Некоторые из этих тестов, которые имеют линейную сложность, обеспечивают спектральные меры случайности. T. Beth и ZD. Дай стремился показать, что сложность Колмогорова и линейная сложность практически одинаковы, [7] хотя Ю. Ван позже показал, что их утверждения неверны. [8] Тем не менее, Ван также продемонстрировал, что для случайных последовательностей Мартина-Лёфа колмогоровская сложность по существу такая же, как и линейная сложность.
Эти практические тесты позволяют сравнивать случайность строк . С точки зрения вероятности, все строки заданной длины имеют одинаковую случайность. Однако разные струны имеют разную колмогоровскую сложность. Например, рассмотрим следующие две строки.
- Строка 1: 01010101010101010101010101010101010101010101010101010101010101
- Строка 2: 1100100001100001110111101110110011111010010000100101011110010110
Строка 1 допускает краткое лингвистическое описание: «32 повторения '01'». Это описание состоит из 22 символов и может быть эффективно построено из некоторых базовых последовательностей. [ требуется пояснение ] Строка 2 не имеет очевидного простого описания, кроме записи самой строки, которая состоит из 64 символов [ требуется пояснение ], и у нее нет сравнительно эффективного представления базовой функции . Используя линейные спектральные тесты Адамара (см. Преобразование Адамара ), будет обнаружено, что первая из этих последовательностей имеет гораздо меньшую случайность, чем вторая, что согласуется с интуицией.
Известные реализации программного обеспечения
Смотрите также
Заметки
- ^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc., стр. 975–976 . ISBN 978-1-57955-008-0.
- ^ Вилли Мейер; Отмар Стаффельбах (1991), "Анализ псевдослучайных последовательностей, генерируемых клеточными автоматами", Успехи в криптологии: Proc. Семинар по теории и применению криптографических методов, EUROCRYPT '91. Конспект лекций по информатике 547 : 186
- ^ Моше Сиппер; Марко Томассини (1996), «Генерация параллельных генераторов случайных чисел с помощью клеточного программирования», Международный журнал современной физики C , 7 (2): 181–190, CiteSeerX 10.1.1.21.870 , doi : 10.1142 / S012918319600017X.
- ^ Yongge Ван. О дизайне LIL-тестов для (псевдо) случайных генераторов и некоторых экспериментальных результатах, http://webpages.uncc.edu/yonwang/ , 2014
- ^ Юнгге Ван; Тони Никол (2014), «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL», Esorics 2014, Lncs 8712 : 454–471
- ^ Терри Риттер, «Тесты на случайность: обзор литературы», веб-страница: CBR-rand .
- ^ Бет, Т. и З.Д. Дай. 1989. О сложности псевдослучайных последовательностей - или: Если вы можете описать последовательность, она не может быть случайной. Достижения в криптологии - EUROCRYPT '89. 533-543. Springer-Verlag
- ^ Yongge Wang 1999. Линейная сложность против псевдослучайности: по результату Бет и Дая. В: Proc. Asiacrypt 99, страницы 288-298. LNCS 1716, Springer Verlag
Внешние ссылки
- Тесты на случайность, включенные в Cryptographic Toolkit от NIST
- Джордж Марсалья , Вай Ван Цанг (2002), « Некоторые труднопроходимые тесты на случайность », Журнал статистического программного обеспечения , том 7, выпуск 3
- DieHarder: набор тестов на случайные числа , Роберт Г. Браун, Университет Дьюка
- Онлайн-анализ генератора случайных чисел от CAcert.org