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

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

Фон

Проблема случайности - важный философский и теоретический вопрос. Тесты на случайность могут использоваться для определения того, имеет ли набор данных распознаваемый образец, который указывал бы на то, что процесс, который его сгенерировал, в значительной степени неслучайен. По большей части статистический анализ на практике был гораздо больше озабочен поиском закономерностей в данных, чем проверкой случайности. Однако за последнее столетие было предложено множество тестов на случайность, особенно в контексте азартных игр и их правил. Чаще всего тесты применяются не непосредственно к последовательностям нулей и единиц, а к числам, полученным из блоков по 8 элементов.[1]

Многие «генераторы случайных чисел», которые используются сегодня, представляют собой определенные алгоритмы, и на самом деле они псевдослучайный генераторы чисел. Создаваемые ими последовательности называются псевдослучайными последовательностями. Эти генераторы не всегда генерируют последовательности, которые являются достаточно случайными, но вместо этого могут создавать последовательности, содержащие шаблоны. Например, пресловутый РАНДУ рутина резко не выдерживает многих тестов на случайность, включая спектральный тест.

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc. стр.1084. ISBN  978-1-57955-008-0.
  2. ^ Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc., стр.975–976. ISBN  978-1-57955-008-0.
  3. ^ Вилли Мейер; Отмар Стаффельбах (1991), "Анализ псевдослучайных последовательностей, генерируемых клеточными автоматами", Успехи криптологии: Учеб. Семинар по теории и применению криптографических методов, EUROCRYPT '91. Конспект лекций по информатике 547: 186
  4. ^ Моше Сиппер; Марко Томассини (1996), "Генерация параллельных генераторов случайных чисел клеточным программированием", Международный журнал современной физики C, 7 (2): 181–190, CiteSeerX  10.1.1.21.870, Дои:10.1142 / S012918319600017X.
  5. ^ Юнге Ван. О разработке LIL-тестов для (псевдо) случайных генераторов и некоторых экспериментальных результатах, http://webpages.uncc.edu/yonwang/, 2014
  6. ^ Юнгге Ван; Тони Никол (2014), «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL», Esorics 2014, Lncs 8712: 454–471
  7. ^ Терри Риттер, «Тесты на случайность: обзор литературы», веб-страница: CBR-ранд.
  8. ^ Бет, Т. и З.-Д. Дай. 1989. О сложности псевдослучайных последовательностей - или: Если вы можете описать последовательность, она не может быть случайной. Достижения в криптологии - EUROCRYPT '89. 533-543. Springer-Verlag
  9. ^ Yongge Wang 1999. Линейная сложность против псевдослучайности: о результате Бет и Дая. В: Proc. Asiacrypt 99, страницы 288-298. LNCS 1716, Springer Verlag

внешняя ссылка