stringtranslate.com

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

Тест на случайность (или тест на случайность ) в оценке данных — это тест, используемый для анализа распределения набора данных, чтобы увидеть, можно ли его описать как случайный (не имеющий закономерности). В стохастическом моделировании , как и в некоторых компьютерных симуляциях , ожидаемая случайность потенциальных входных данных может быть проверена с помощью формального теста на случайность, чтобы показать, что данные пригодны для использования в прогонах моделирования. В некоторых случаях данные показывают очевидную неслучайную закономерность, как в так называемых «прогонах в данных» (например, ожидание случайных 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] Тем не менее, Ван также продемонстрировал, что для случайных последовательностей Мартина-Лёфа сложность Колмогорова по сути такая же, как и линейная сложность.

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

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

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

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

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

Примечания

  1. ^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 975–976. ISBN 978-1-57955-008-0.
  2. ^ Вилли Мейер; Отмар Стаффельбах (1991). «Анализ псевдослучайных последовательностей, генерируемых клеточными автоматами». Достижения в криптологии — EUROCRYPT '91 . Конспект лекций по информатике. Том 547. С. 186–199. doi :10.1007/3-540-46416-6_17. ISBN 978-3-540-54620-7.
  3. ^ Моше Сиппер; Марко Томассини (1996), «Создание параллельных генераторов случайных чисел с помощью клеточного программирования», Международный журнал современной физики C , 7 (2): 181–190, Bibcode : 1996IJMPC...7..181S, CiteSeerX 10.1.1.21.870 , doi : 10.1142/S012918319600017X .
  4. ^ Юнге Ван. О разработке LIL-тестов для (псевдо)случайных генераторов и некоторых экспериментальных результатах, http://webpages.uncc.edu/yonwang/, 2014
  5. ^ Yongge Wang; Tony Nicol (2014), «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL», Esorics 2014, LNCS 8712 : 454–471
  6. ^ Терри Риттер, «Тесты случайности: обзор литературы», веб-страница: CBR-rand.
  7. ^ Бет, Т. и З.Д. Дай. 1989. О сложности псевдослучайных последовательностей -- или: Если вы можете описать последовательность, она не может быть случайной. Достижения в криптологии – EUROCRYPT '89. 533-543. Springer-Verlag
  8. ^ Yongge Wang 1999. Линейная сложность против псевдослучайности: о результате Бет и Дая. В: Proc. Asiacrypt 99, страницы 288--298. LNCS 1716, Springer Verlag
  9. ^ ENT: Программа тестирования последовательности псевдослучайных чисел, Fourmilab, 2008.
  10. ^ Статистический набор тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений, специальная публикация 800-22, редакция 1a, Национальный институт стандартов и технологий , 2010.
  11. ^ Реализация набора статистических тестов NIST

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