Несгибаемые испытания - Diehard tests

В стойкие испытания являются батареей статистические тесты для измерения качества генератор случайных чисел. Они были разработаны Джордж Марсалья в течение нескольких лет и впервые опубликовано в 1995 г. CD-ROM случайных чисел.[1]

Обзор теста

  • Дни рождения: Выбирайте случайные точки на большом интервале. Расстояние между точками должно быть асимптотически экспоненциально распределенный.[2] Название основано на парадокс дня рождения.
  • Перекрывающиеся перестановки: Анализировать последовательности из пяти последовательных случайных чисел. 120 возможных порядков должны произойти со статистически равной вероятностью.
  • Ранги матриц: Выберите некоторое количество битов из некоторого количества случайных чисел, чтобы сформировать матрицу по {0,1}, затем определите классифицировать матрицы. Посчитайте ряды.
  • Обезьяньи тесты: Рассматривать последовательности из некоторого количества бит как "слова". Подсчитайте перекрывающиеся слова в потоке. Количество «слов», которые не появляются, должно соответствовать известному распределению. Название основано на теорема о бесконечной обезьяне.
  • Подсчитайте единицы: Подсчитать 1 бит в каждом из последовательных или выбранных байтов. Преобразуйте счетчики в «буквы» и подсчитайте количество появлений пятибуквенных «слов».
  • Тест на парковке: Случайным образом разместите единичные круги в квадрате 100 × 100. Круг успешно припаркован, если он не перекрывает существующий, успешно припаркованный. После 12000 попыток количество успешно припаркованных кругов должно соответствовать определенному нормальное распределение.
  • Тест на минимальное расстояние: Случайным образом разместите 8000 точек в квадрате размером 10000 × 10000, затем найдите минимальное расстояние между парами. Квадрат этого расстояния должен быть экспоненциально распределенный с определенным средним значением.
  • Тест случайных сфер: Случайным образом выберите 4000 точек в кубе с ребром 1000. Центрируйте сферу в каждой точке, радиус которой является минимальным расстоянием до другой точки. Объем наименьшей сферы должен быть экспоненциально распределен с некоторым средним значением.
  • Тест на сжатие: Умножьте 2³¹ на случайные числа с плавающей запятой на (0,1), пока не получите 1. Повторите это 100000 раз. Количество чисел с плавающей запятой, необходимое для достижения 1, должно соответствовать определенному распределению.
  • Тест на перекрывающиеся суммы: Генерировать длинную последовательность случайных чисел с плавающей запятой на (0,1). Добавьте последовательности из 100 последовательных чисел с плавающей запятой. Суммы должны быть нормально распределены с характерным средним и дисперсией.
  • Запускает тест: Генерировать длинную последовательность случайных чисел с плавающей запятой на (0,1). Считайте восходящие и нисходящие пробеги. Подсчеты должны следовать определенному распределению.
  • Крэпс-тест: Сыграть 200000 игр кости, считая выигрыши и количество бросков за игру. Каждый счет должен соответствовать определенному распределению.

Описание тестов

  • Тест на расстояние между днями рождения: Выбирать м дни рождения в год п дней. Перечислите интервалы между днями рождения. Если j это количество значений, которые встречаются в этом списке более одного раза, тогда j асимптотически распределена Пуассона со средним м3 ÷ (4п). Опыт показывает, что n должно быть довольно большим, скажем п ≥ 218, для сравнения результатов с распределением Пуассона с этим средним значением. Этот тест использует п = 224 и м = 29, так что основное распределение для j в качестве пуассоновского с λ = 227 ÷ 226 = 2. Выборка 500 js, и критерий согласия по хи-квадрат дает п ценить. Первый тест использует биты 1–24 (считая слева) целых чисел в указанном файле. Затем файл закрывается и открывается снова. Затем биты 2–25 используются для указания дней рождения, затем биты 3–26 и так далее до битов 9–32. Каждый набор бит обеспечивает п-значение, а девять п-значения предоставляют образец для KSTEST.
  • Тест на перекрывающиеся 5 перестановок: Это тест OPERM5. Он смотрит на последовательность из миллиона 32-битных случайных целых чисел. Каждый набор из пяти последовательных целых чисел может находиться в одном из 120 состояний для 5! возможны заказы пяти номеров. Таким образом, каждое 5-е, 6-е, 7-е, ... числа обозначают состояние. Поскольку наблюдаются многие тысячи переходов между состояниями, выполняется совокупный подсчет количества появлений каждого состояния. Затем квадратичная форма в слабом инверсии ковариационной матрицы 120 × 120 дает тест, эквивалентный тесту отношения правдоподобия, что количество 120 ячеек было получено из указанного (асимптотически) нормального распределения с указанной ковариационной матрицей 120 × 120 (с рангом 99). ). Эта версия использует 1000000 целых чисел дважды. В этом тесте могут быть нерешенные ошибки, приводящие к неизменно низким p-значениям.[3]
  • Бинарный ранговый тест для матриц 31 × 31: Крайний левый 31 бит 31 случайного целого числа из тестовой последовательности используется для формирования двоичной матрицы 31 × 31 над полем {0,1}. Ранг определяется. Этот ранг может быть от 0 до 31, но ранги <28 редки, и их количество суммируется с рангом 28. Ранги найдены для 40000 таких случайных матриц и критерий хи-квадрат проводится по счетам для рангов 31, 30, 29 и ≤ 28.
  • Бинарный ранговый тест для матриц 32 × 32: Формируется случайная двоичная матрица 32 × 32, каждая строка представляет собой 32-битное случайное целое число. Ранг определяется. Этот ранг может быть от 0 до 32, ранги меньше 29 редки, и их подсчеты объединяются с рангами для ранга 29. Ранги находятся для 40000 таких случайных матриц, и выполняется проверка хи-квадрат для подсчетов для рангов 32, 31, 30 и ≤ 29.
  • Бинарный ранговый тест для матриц 6 × 8: Из каждого из шести случайных 32-битных целых чисел из тестируемого генератора выбирается указанный байт, а полученные шесть байтов образуют двоичную матрицу 6 × 8, ранг которой определяется. Этот ранг может быть от 0 до 6, но ранги 0, 1, 2, 3 встречаются редко; их подсчеты суммируются с подсчетами для ранга 4. Ранги находятся для 100000 случайных матриц, и тест хи-квадрат выполняется для подсчетов для рангов 6, 5 и ≤ 4.
  • Тест битового потока: Тестируемый файл рассматривается как поток битов. Назовите их б1, б2,…. Рассмотрим алфавит с двумя «буквами», 0 и 1, и представьте поток битов как последовательность перекрывающихся 20-буквенных «слов». Таким образом, первое слово - b1б2… Б20, второй - b2б3… Б21, и так далее. Тест битового потока подсчитывает количество пропущенных 20-буквенных (20-битных) слов в строке из 221 перекрывающиеся 20-буквенные слова. Есть 220 возможные 20-буквенные слова. Для действительно случайной строки из 221 + 19 бит, количество пропущенных слов j должно быть (очень близко к) нормально распределенным со средним значением 141 909 и сигмой 428. Таким образом (j-141909) ÷ 428 должна быть стандартной нормальной вариацией (z оценка), что приводит к равномерному [0,1) п ценить. Тест повторяется двадцать раз.
  • Тесты OPSO, OQSO и ДНК: OPSO означает перекрывающиеся пары-разреженная-занятость. Тест OPSO рассматривает двухбуквенные слова из 1024 букв алфавита. Каждая буква определяется указанными десятью битами из 32-битного целого числа в проверяемой последовательности. OPSO генерирует 221 (перекрытие) 2-хбуквенные слова (от 221 + 1 «нажатий клавиш») и подсчитывает количество пропущенных слов - то есть двухбуквенных слов, которые не появляются во всей последовательности. Это количество должно быть очень близко к нормально распределенному со средним значением 141909, сигма 290. Таким образом, (missingwrds-141909) ÷ 290 должно быть стандартной нормальной переменной. Тест OPSO берет 32 бита из тестового файла за раз и использует назначенный набор из десяти последовательных битов. Затем он перезапускает файл для следующих 10 бит и так далее. OQSO означает частичное перекрытие-учетверение-разреженность. Тестовый OQSO аналогичен, за исключением того, что он рассматривает 4-буквенные слова из 32-х буквенного алфавита, каждая буква определяется назначенной строкой из 5 последовательных битов из тестового файла, элементы которого предполагаются 32-битными случайными целыми числами. Среднее количество пропущенных слов в последовательности из 221 четырехбуквенные слова, (221 + 3 «нажатия клавиш»), снова 141909, с сигмой = 295. Среднее значение основано на теории; сигма происходит от обширного моделирования. В тесте ДНК рассматривается алфавит из 4 букв C, G, A, T, определяемый двумя обозначенными битами в проверяемой последовательности случайных целых чисел. Он учитывает 10-буквенные слова, так что, как и в OPSO и OQSO, есть 228 возможные слова и среднее количество пропущенных слов в строке из 221 (перекрытие) 10-буквенные слова (221 + 9 «нажатий клавиш») составляет 141909. Стандартное отклонение sigma = 339 было определено, как для OQSO, путем моделирования. (Сигма для OPSO, 290, является истинным значением (до трех разрядов), не определенным моделированием.
  • Тест count-the-1 на потоке байтов: Рассматривайте тестируемый файл как поток байтов (четыре на 32-битное целое число). Каждый байт может содержать от нуля до восьми единиц с вероятностями 1, 8, 28, 56, 70, 56, 28, 8, 1 больше 256. Теперь пусть поток байтов предоставляет строку перекрывающихся 5-буквенных слов, каждое из которых " буква "принимает значения A, B, C, D, E. Буквы определяются количеством единиц в байте 0, 1 или 2, что дает A, 3 дает B, 4 дает C, 5 дает D и 6, 7 или 8 дают E. Таким образом, мы видим, что обезьяна у пишущей машинки нажимает пять клавиш с различной вероятностью (37, 56, 70, 56, 37 больше 256). Существует 5⁵ возможных пятибуквенных слов, и из строки из 256000 (перекрывающихся) пятибуквенных слов подсчет производится по частотам для каждого слова. Квадратичная форма слабой обратной матрицы ковариационной матрицы количества клеток обеспечивает критерий хи-квадрат Q5 – Q4, разность наивных сумм Пирсона (OBS-EXP)2 ÷ ОПЫТ по подсчету 5- и 4-буквенных ячеек.
  • Тест count-the-1 для определенных байтов: Рассмотрим тестируемый файл как поток 32-битных целых чисел. Из каждого целого числа выбирается определенный байт, скажем, крайние левые биты от 1 до 8. Каждый байт может содержать от 0 до 8 единиц с вероятностями от 1, 8, 28, 56, 70, 56, 28, 8, 1 больше 256. Теперь пусть указанные байты из последовательных целых чисел предоставляют строку (перекрывающихся) 5-буквенных слов, каждая «буква» принимает значения A, B, C, D, E. Буквы определяются количеством единиц в этом байте 0 , 1 или 2 → A, 3 → B, 4 → C, 5 → D и 6, 7 или 8 → E. Таким образом, у нас есть обезьяна у пишущей машинки, нажимающей пять клавиш с различной вероятностью 37, 56, 70, 56 , 37 из 256. Всего 55 возможных 5-буквенных слов, а из строки из 256000 (перекрывающихся) 5-буквенных слов подсчет производится по частотам для каждого слова. Квадратичная форма слабой обратной матрицы ковариационной матрицы количества клеток обеспечивает критерий хи-квадрат Q5 - Q4, разность наивных сумм Пирсона (OBS - EXP)2 ÷ ОПЫТ по подсчету 5- и 4-буквенных ячеек.
  • Тест на парковке: В квадрате со стороной 100 случайным образом «припаркуйте» машину - круг радиуса 1. Затем попробуйте припарковать вторую, третью и так далее, каждый раз паркуясь «на слух». То есть, если попытка припарковать автомобиль вызывает аварию с уже припаркованным, попробуйте еще раз в новом случайном месте. (Чтобы избежать проблем с маршрутом, подумайте о парковке вертолетов, а не автомобилей.) Каждая попытка приводит либо к аварии, либо к успеху, после чего следует приращение к списку уже припаркованных автомобилей. Если мы построим п: количество попыток по сравнению с k После того, как номер успешно припаркован, мы получим кривую, которая должна быть похожей на те, которые дает идеальный генератор случайных чисел. Теория поведения такой случайной кривой кажется недостижимой, и поскольку графические дисплеи недоступны для этой серии тестов, используется простая характеристика случайного эксперимента: k, количество автомобилей, успешно припаркованных после п = 12000 попыток. Моделирование показывает, что k должно усреднить 3523 с сигмой 21,9 и очень близко к нормально распределенному. Таким образом (k - 3523) ÷ 21.9 должна быть стандартной нормальной переменной, которая, преобразованная в универсальную переменную, обеспечивает ввод в KSTEST на основе выборки из 10.
  • Тест на минимальное расстояние: Он делает это 100 раз выбирает п = 8000 случайных точек в квадрате со стороной 10000. Найти d, минимальное расстояние между (п2 − п) ÷ 2 пары точек. Если точки действительно независимые однородные, то d2, квадрат минимального расстояния должен быть (очень близок) экспоненциально распределен со средним значением 0,995. Таким образом 1 - exp (-d2 ÷ 0.995) должен быть однородным на [0,1), и KSTEST для полученных 100 значений служит проверкой однородности для случайных точек в квадрате. Напечатаны номера тестов = 0 mod 5, но KSTEST основан на полном наборе из 100 случайных выборов из 8000 точек в квадрате 10000 × 10000.
  • Тест 3D-сфер: Выберите 4000 случайных точек в кубе с ребром 1000. В каждой точке центрируйте сферу, достаточно большую, чтобы достичь следующей ближайшей точки. Тогда объем наименьшей такой сферы (очень близок к) распределен экспоненциально со средним значением 120π ÷ 3. Таким образом, радиус в кубе является экспоненциальным со средним значением 30. (Среднее значение получено путем обширного моделирования). Тест 3D-сфер генерирует 4000 таких сфер 20 раз. Каждый кубик минимального радиуса приводит к однородной переменной с помощью 1 - exp (-р3 ÷ 30), то 20-го числа выполняется KSTEST. п-значения.
  • Тест на сжатие: Случайные целые числа перемещаются, чтобы получить униформу на [0,1). Начиная с k = 231 = 2147483648, тест обнаруживает j, количество итераций, необходимых для уменьшения k к 1, используя сокращение k = потолок (k×U), с U предоставляется целыми числами с плавающей запятой из тестируемого файла. Такой js найдены 100000 раз, затем подсчитывается количество раз j was ≤ 6, 7, ..., 47, ≥ 48 используются для проверки хи-квадрат для частот ячеек.
  • Тест перекрывающихся сумм: Целые числа перемещаются, чтобы получить последовательность U(1), U(2), ... равномерных [0,1) переменных. Затем перекрывающиеся суммы, S(1) = U(1) + ... + U(100), S(2) = U(2) + ... + U(101), ... формируются. В Ss практически нормальны с определенной ковариационной матрицей. Линейное преобразование Ss преобразует их в последовательность независимых стандартных нормалей, которые преобразуются в универсальные переменные для KSTEST. В п-значения из десяти KSTEST даны еще одному KSTEST.
  • Тест пробежек: Он считает пробеги вверх и вниз в последовательности однородных [0,1) переменных, полученных с помощью плавающих 32-битных целых чисел в указанном файле. В этом примере показано, как подсчитываются прогоны: 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 содержат пробег длиной 3, пробег вниз длиной 2 и пробег вверх (как минимум) 2, в зависимости от на следующие значения. Ковариационные матрицы для увеличения и уменьшения хорошо известны, что приводит к критериям хи-квадрат для квадратичных форм в слабых инверсиях ковариационных матриц. Подсчитываются прогоны для последовательностей длиной 10000. Это делается десять раз. Потом повторил.
  • Крэпс-тест: Он играет 200000 игр в кости, находит количество побед и количество бросков, необходимых для завершения каждой игры. Количество побед должно быть (очень близко) к нормальному со средним значением 200000п и дисперсия 200000п(1 − п), с п = 244 ÷ 495. Броски, необходимые для завершения игры, могут варьироваться от 1 до бесконечности, но счет для всех> 21 суммируется с 21. Проверка количества бросков проводится по количеству ячеек. Каждое 32-битное целое число из тестового файла обеспечивает значение для броска игральной кости путем плавания до [0,1), умножения на 6 и взятия 1 плюс целая часть результата.

Большинство тестов в DIEHARD возвращают п-значение, которое должно быть одинаковым на [0,1), если входной файл содержит действительно независимые случайные биты. Те п-значения получены п = F(Икс), куда F - предполагаемое распределение выборочной случайной величины Икс - часто нормально. Но это предполагало F это просто асимптотическое приближение, для которого соответствие будет худшим в хвосте. Поэтому не стоит удивляться случайным п-значения около 0 или 1, например 0,0012 или 0,9983. Когда битовый поток действительно НЕУДАЕТ БОЛЬШОЙ, вы получите пs от 0 или от 1 до шести или более мест. Поскольку существует множество тестов, вполне вероятно, что п <0,025 или п > 0,975 означает, что ГСЧ «не прошел тест на уровне 0,05». Мы ожидаем ряд таких мероприятий пОни происходят среди сотен событий, производимых DIEHARD, даже при условии, что генератор случайных чисел идеален.

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

Примечания

  1. ^ "Компакт-диск случайных чисел Marsaglia, включающий стойкую батарею тестов на случайность". Университет штата Флорида. 1995. Архивировано с оригинал на 2016-01-25.
  2. ^ Реньи, 1953, стр.194
  3. ^ https://webhome.phy.duke.edu/~rgb/General/dieharder.php

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