Непреклонные тесты

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

История

Первоначальная батарея тестов случайности для ГСЧ была предложена в первом издании Искусство компьютерного программирования» « Дональда Кнута 1969 года (том 2, глава 3.3: Статистические тесты). Затем тесты Кнута были заменены Джорджа Марсальи тестами Дихарда (1995), состоящими из пятнадцати различных тестов. Невозможность изменять параметры теста или добавлять новые тесты привела к разработке библиотеки TestU01 , представленной в 2007 году Пьером Л'Экуйером и Ричардом Симардом из Университета Монреаля .

Обзор теста

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

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

Тест на интервалы между днями рождения: Выберите m дней рождения в году, состоящем из n дней. Укажите промежутки между днями рождения. Если $j$ — это количество значений, которые встречаются в этом списке более одного раза, то $j$ асимптотически распределяется по Пуассону со средним значением $m. 3 / (4 н)$ . Опыт показывает, что n должно быть довольно большим, скажем, n ≥ 2. ¹⁸, для сравнения результатов с распределением Пуассона с этим средним значением. В этом тесте используется n = 2 ²⁴ и м = 2 ⁹, так что основное распределение $j$ считается пуассоновским с $λ = 2 27 / 2 26 = 2$ . выборка длительностью 500 $Дж$ Берется , и критерий согласия хи-квадрат дает значение p . Первый тест использует биты 1–24 (считая слева) целых чисел в указанном файле. Затем файл закрывается и снова открывается. Далее биты 2–25 используются для указания дней рождения, затем биты 3–26 и так далее до битов 9–32. Каждый набор битов предоставляет значение p , а девять значений p предоставляют выборку для KSTEST.
Перекрывающийся тест с 5 перестановками: Это тест OPERM5. Он рассматривает последовательность из миллиона 32-битных случайных целых чисел. Каждый набор из пяти последовательных целых чисел может находиться в одном из 120 состояний, например 5! возможны заказы из пяти номеров. Таким образом, каждое из 5-го, 6-го, 7-го и... чисел обозначает состояние. Поскольку наблюдаются многие тысячи переходов между состояниями, производится совокупный подсчет количества появлений каждого состояния. Тогда квадратичная форма в слабой обратной форме ковариационной матрицы 120×120 дает тест, эквивалентный тесту отношения правдоподобия, согласно которому 120 подсчетов ячеек происходят из заданного (асимптотически) нормального распределения с указанной ковариационной матрицей 120×120 (с рангом 99). ). В этой версии дважды используется 1000000 целых чисел. В этом тесте могут быть неустраненные ошибки, приводящие к постоянно плохим значениям p. ^[4]
Тест двоичного ранга для матриц 31×31.: Крайние левые 31 бит 31 случайного целого числа из тестовой последовательности используются для формирования двоичной матрицы 31×31 над полем {0,1}. Ранг определен. Этот ранг может быть от 0 до 31, но ранги <28 встречаются редко, и их значения объединяются с числами для ранга 28. Ранги находятся для 40 000 таких случайных матриц, и для критерий хи-квадрат. чисел для рангов 31, 30 выполняется , 29 и ≤ 28.
Тест двоичного ранга для матриц 32×32.: Формируется случайная двоичная матрица размером 32×32, каждая строка представляет собой 32-битное случайное целое число. Ранг определен. Этот ранг может быть от 0 до 32, ранги ниже 29 встречаются редко, и их значения объединяются с числами для ранга 29. Ранги находятся для 40 000 таких случайных матриц и выполняется критерий хи-квадрат для счетчиков для рангов 32, 31, 30 и ≤ 29.
Тест двоичного ранга для матриц 6×8.: Из каждого из шести случайных 32-битных целых чисел тестируемого генератора выбирается указанный байт, и полученные шесть байтов образуют двоичную матрицу 6×8, ранг которой определяется. Этот ранг может быть от 0 до 6, но ранги 0, 1, 2, 3 встречаются редко; их подсчеты объединяются с подсчетами для ранга 4. Ранги находятся для 100 000 случайных матриц, и тест хи-квадрат выполняется для подсчетов для рангов 6, 5 и ≤ 4.
Тест битового потока: Тестируемый файл рассматривается как поток битов. Назовите их b ₁ , b ₂ , ... . Рассмотрим алфавит с двумя «буквами», 0 и 1, и представьте себе поток битов как последовательность перекрывающихся 20-буквенных «слов». Таким образом, первое слово — b ₁ b ₂ ...b ₂₀ , второе — b ₂ b ₃ ...b ₂₁ и так далее. Тест битового потока подсчитывает количество пропущенных 20-буквенных (20-битных) слов в строке из 2 ²¹ перекрывающиеся слова из 20 букв. Есть 2 ²⁰ возможные слова из 20 букв. Для действительно случайной строки из 2 ²¹ + 19 бит, количество пропущенных слов $j$ должно быть (очень близко к) нормально распределенным со средним значением 141 909 и сигмой 428. Таким образом, $(j -141909)/428$ должно быть стандартной нормальной переменной ( оценка z ), которая приводит к равномерному [ 0,1) значение р . Тест повторяется двадцать раз.
Тесты ОПСО, ОКСО и ДНК: OPSO означает редкую занятость перекрывающихся пар. Тест OPSO учитывает двухбуквенные слова из алфавита, состоящего из 1024 букв. Каждая буква определяется указанными десятью битами 32-битного целого числа в проверяемой последовательности. ОПСО генерирует 2 ²¹ (перекрывающиеся) слова из 2 букв (из 2 ²¹ + 1 «нажатие клавиши») и подсчитывает количество пропущенных слов – то есть двухбуквенных слов, которые не встречаются во всей последовательности. Это число должно быть очень близко к нормальному распределению со средним значением 141909, сигма 290. Таким образом, (missingwrds-141909)/290 должно быть стандартной нормальной переменной. Тест OPSO берет по 32 бита из тестового файла и использует назначенный набор из десяти последовательных битов. Затем он перезапускает файл для следующих назначенных 10 бит и так далее. OQSO означает перекрывающуюся четверку разреженной занятости. Тест OQSO аналогичен, за исключением того, что он рассматривает 4-буквенные слова из алфавита из 32 букв, каждая буква определяется назначенной строкой из 5 последовательных битов из тестового файла, элементами которого считаются 32-битные случайные целые числа. Среднее количество пропущенных слов в последовательности из 2 ²¹ четырехбуквенные слова (2 ²¹ + 3 «нажатия клавиш»), снова равно 141909, с сигмой = 295. Среднее значение основано на теории; сигма возникает в результате обширного моделирования. В тесте ДНК рассматривается алфавит из 4 букв C, G, A, T, определяемый двумя назначенными битами в проверяемой последовательности случайных целых чисел. Он учитывает слова из 10 букв, так что, как и в OPSO и OQSO, их 2. ²⁸ возможных слов и среднее количество пропущенных слов в строке из 2 ²¹ (перекрывающиеся) слова из 10 букв (2 ²¹ + 9 «нажатий клавиш») составляет 141909. Стандартное отклонение сигмы = 339 определялось, как и для OQSO, путем моделирования. (Сигма для ОПСО, 290, — это истинное значение (с точностью до трех знаков), не определяемое моделированием.
Тест на подсчет единиц в потоке байтов: Рассмотрим тестируемый файл как поток байтов (четыре на 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 ⁵ возможные 5-буквенные слова и из строки из 256 000 (перекрывающихся) 5-буквенных слов подсчитываются частоты для каждого слова. Квадратичная форма в слабой обратной ковариационной матрице количества ячеек обеспечивает критерий хи-квадрат Q5 – Q4, разницу наивных сумм Пирсона $(OBS-EXP) 2 / EXP$ по счетчикам для 5- и 4-буквенных ячеек.
Проверка подсчета единиц для определенных байтов: Рассмотрим тестируемый файл как поток 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. Всего 5 ⁵ возможные 5-буквенные слова и из строки из 256 000 (перекрывающихся) 5-буквенных слов подсчитываются частоты для каждого слова. Квадратичная форма в слабой обратной ковариационной матрице количества ячеек обеспечивает критерий хи-квадрат Q5 – Q4, разность наивных сумм Пирсона $(OBS - EXP) 2 / EXP$ по счетчикам для 5- и 4-буквенных ячеек.
Тест на парковке: В квадрате со стороной 100 случайным образом «припаркуйте» машину – круг радиуса 1. Затем попробуйте припарковать 2-ю, 3-ю и так далее, каждый раз паркуясь «на слух». То есть, если попытка припарковать автомобиль приводит к столкновению с уже припаркованным автомобилем, повторите попытку в новом случайном месте. (Чтобы избежать проблем с маршрутом, рассмотрите возможность парковки вертолетов, а не автомобилей.) Каждая попытка приводит либо к аварии, либо к успеху, за которым следует увеличение списка уже припаркованных автомобилей. Если мы построим график зависимости n : количества попыток от числа успешно припаркованных автомобилей , мы получим кривую, похожую на кривую, которую дает идеальный генератор случайных чисел. Теория поведения такой случайной кривой кажется недостижимой, и поскольку графические изображения для этой серии тестов недоступны, используется простая характеристика случайного эксперимента: k , количество автомобилей, успешно припаркованных после n = 12 000 попыток. Моделирование показывает, что k должно составлять в среднем 3523 с сигмой 21,9 и очень близко к нормальному распределению. Таким образом $(k - 3523)/21,9$ должна быть стандартной нормальной переменной, которая, преобразованная в универсальную переменную, предоставляет входные данные для KSTEST на основе выборки из 10.
Тест на минимальное расстояние: Он делает это 100 раз, выбирая n = 8000 случайных точек в квадрате со стороной 10000. Найдите d , минимальное расстояние между $(n 2 - n)/2$ пары точек. Если точки действительно независимы и равномерны, то $d 2$ , квадрат минимального расстояния должен быть (очень близок) экспоненциально распределен со средним значением 0,995. Таким образом, $1 - exp(- d 2 / 0,995)$ должно быть однородным на [0,1), а KSTEST для полученных 100 значений служит проверкой однородности для случайных точек в квадрате. Номера тестов = 0 по модулю 5 напечатаны, но KSTEST основан на полном наборе из 100 случайных выборов по 8000 точек в квадрате 10000×10000.
Тест 3D-сфер: Выберите 4000 случайных точек в кубе с ребром 1000. В каждой точке отцентрируйте сферу, достаточно большую, чтобы достичь следующей ближайшей точки. Тогда объем наименьшей такой сферы (очень близко) экспоненциально распределяется со средним значением 120 $π$ / 3. Таким образом, куб радиуса является экспоненциальным со средним значением 30. (Среднее значение получено путем обширного моделирования). Тест 3D-сфер генерирует 4000 таких сфер 20 раз. Каждый куб минимального радиуса приводит к однородной переменной посредством $1 - exp(- r 3 / 30)$ , то KSTEST выполняется для 20 p -значений.
Тест на сжатие: Случайные целые числа плавают, чтобы получить униформу на [0,1). Начиная с k = 2 ³¹ = 2147483648, тест находит $j$ — количество итераций, необходимых для уменьшения k до 1, используя сокращение k = потолок( k × U ), где U определяется целыми числами с плавающей запятой из тестируемого файла. Такие $j$ встречаются 100 000 раз, затем подсчитывается количество раз, когда $j$ было $\leq 6, 7, ..., 47, \geq 48,$ и используется для проверки хи-квадрат для частот ячеек.
Тест перекрывающихся сумм: Целые числа плавают, чтобы получить последовательность U (1), U (2), ... однородных [0,1) переменных. перекрывающиеся суммы S (1) = U (1)+...+ U (100), S (2) = U (2)+...+ U Тогда образуются (101),.... S . практически нормальны с определенной ковариационной матрицей Линейное преобразование S преобразует их в последовательность независимых стандартных нормалей, которые преобразуются в унифицированные переменные для KSTEST. Значения p из десяти KSTEST присваиваются еще одному KSTEST.
Тест на пробежках: Он подсчитывает пробежки вверх и вниз в последовательности однородных переменных [0,1), полученных путем плавания 32-битных целых чисел в указанном файле. В этом примере показано, как подсчитываются пробежки: 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 содержат восходящий пробег длиной 3, нисходящий пробег длиной 2 и восходящий пробег длиной (по крайней мере) 2, в зависимости от на следующих значениях. Ковариационные матрицы для возрастающих и падающих матриц хорошо известны, что позволяет использовать тесты хи-квадрат для квадратичных форм в слабых обратных ковариационных матрицах. Прогоны подсчитываются для последовательностей длиной 10000. Это делается десять раз. Потом повторил.
Тест на крэпс: Он играет 200 000 игр в кости, определяет количество побед и количество бросков, необходимое для завершения каждой игры. Количество побед должно быть (очень близким) к нормальному со средним значением 200 000 p и дисперсией $200 000 p (1 - p)$ , с $p = 244/495$ . Броски, необходимые для завершения игры, могут варьироваться от 1 до бесконечности, но количество бросков для всех > 21 суммируется с 21. Для подсчета клеток с количеством бросков проводится критерий хи-квадрат. Каждое 32-битное целое число из тестового файла дает значение для броска игральной кости путем плавания до [0,1), умножения на 6 и получения 1 плюс целая часть результата.

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