Эти несгибаемые испытания являются батареи статистических тестов для измерения качество генератора случайных чисел . Они были разработаны Джорджем Марсалья в течение нескольких лет и впервые опубликованы в 1995 году на компакт-диске со случайными числами. [1]
Обзор теста
- Интервалы дней рождения : выбирайте случайные точки на большом интервале. Расстояние между точками должно быть асимптотически экспоненциально распределено . [2] Название основано на парадоксе дня рождения .
- Перекрывающиеся перестановки : анализируйте последовательности из пяти последовательных случайных чисел. 120 возможных порядков должны произойти со статистически равной вероятностью.
- Ранги матриц : выберите некоторое количество битов из некоторого количества случайных чисел, чтобы сформировать матрицу по {0,1}, затем определите ранг матрицы. Посчитайте ряды.
- Обезьяньи тесты : обрабатывайте последовательности из некоторого количества бит как «слова». Подсчитайте перекрывающиеся слова в потоке. Количество «слов», которые не появляются, должно соответствовать известному распределению. Название основано на теореме о бесконечной обезьяне .
- Подсчитайте единицы : подсчитайте 1 бит в каждом из последовательных или выбранных байтов. Преобразуйте счетчики в «буквы» и подсчитайте количество появлений пятибуквенных «слов».
- Тест на парковке : случайным образом разместите единичные круги в квадрате 100 × 100. Круг успешно припаркован, если он не перекрывает существующий, успешно припаркованный. После 12000 попыток количество успешно припаркованных кругов должно соответствовать определенному нормальному распределению .
- Тест минимального расстояния : случайным образом разместите 8000 точек в квадрате 10000 × 10000, затем найдите минимальное расстояние между парами. Квадрат этого расстояния должен быть экспоненциально распределен с некоторым средним значением.
- Тест случайных сфер : случайным образом выберите 4000 точек в кубе с ребром 1000. Центрируйте сферу в каждой точке, радиус которой является минимальным расстоянием до другой точки. Объем наименьшей сферы должен быть экспоненциально распределен с некоторым средним значением.
- Тест на сжатие : умножьте 2 31 на случайные числа с плавающей запятой (0,1), пока не дойдете до 1. Повторите это 100000 раз. Количество чисел с плавающей запятой, необходимое для достижения 1, должно соответствовать определенному распределению.
- Тест перекрывающихся сумм : сгенерируйте длинную последовательность случайных чисел с плавающей запятой на (0,1). Добавьте последовательности из 100 последовательных чисел с плавающей запятой. Суммы должны быть нормально распределены с характерным средним значением и дисперсией.
- Запускает тест : генерирует длинную последовательность случайных чисел с плавающей запятой на (0,1). Считайте восходящие и нисходящие пробеги. Подсчеты должны следовать определенному распределению.
- Тест в кости : сыграйте 200000 игр в кости , считая выигрыши и количество бросков за игру. Каждый счет должен соответствовать определенному распределению.
Описание тестов
- Тест расстояния между днями рождения : выберите m дней рождения в году, состоящем из n дней. Перечислите интервалы между днями рождения. Если j - количество значений, которые встречаются в этом списке более одного раза, то j асимптотически распределено по Пуассону со средним значением m 3 ÷ (4 n ). Опыт показывает, что n должно быть довольно большим, скажем n ≥ 2 18 , для сравнения результатов с распределением Пуассона с этим средним значением. В этом тесте используется n = 2 24 и m = 2 9 , так что базовое распределение для 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-значениям. [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.
- Тест битового потока : тестируемый файл рассматривается как поток битов. Назовите их b 1 , b 2 , .... Рассмотрим алфавит с двумя «буквами», 0 и 1, и представьте поток битов как последовательность перекрывающихся 20-буквенных «слов». Таким образом, первое слово - это b 1 b 2 ... b 20 , второе - b 2 b 3 ... b 21 и так далее. Тест битового потока подсчитывает количество пропущенных 20-буквенных (20-битных) слов в строке из 2 21 перекрывающихся 20-буквенных слов. Есть 2 20 возможных 20-буквенных слов. Для действительно случайной строки из 2 21 + 19 бит количество пропущенных слов j должно быть (очень близко к) нормально распределенным со средним значением 141 909 и сигмой 428. Таким образом ( j -141909) ÷ 428 должно быть стандартной нормальной переменной ( z оценка), что приводит к равномерному значению [0,1) p . Тест повторяется двадцать раз.
- Тесты OPSO, OQSO и DNA : OPSO означает перекрывающиеся пары-разреженная занятость. Тест OPSO рассматривает двухбуквенные слова из 1024 букв алфавита. Каждая буква определяется указанными десятью битами из 32-битного целого числа в проверяемой последовательности. OPSO генерирует 2 21 (перекрывающихся) двухбуквенных слова (из 2 21 + 1 «нажатий клавиш») и подсчитывает количество пропущенных слов - то есть двухбуквенных слов, которые не появляются во всей последовательности. Это количество должно быть очень близко к нормально распределенному со средним значением 141909, сигма 290. Таким образом, (missingwrds-141909) ÷ 290 должно быть стандартной нормальной переменной. Тест OPSO берет 32 бита из тестового файла за раз и использует назначенный набор из десяти последовательных битов. Затем он перезапускает файл для следующих 10 бит и так далее. OQSO означает перекрытие-учетверенное-разреженное-заполнение. Тестовый OQSO аналогичен, за исключением того, что он рассматривает 4-буквенные слова из 32-х буквенного алфавита, каждая буква определяется заданной строкой из 5 последовательных битов из тестового файла, элементы которого предполагаются 32-битными случайными целыми числами. Среднее количество пропущенных слов в последовательности из 2 21 четырехбуквенных слов (2 21 + 3 «нажатия клавиш») снова составляет 141909 с сигмой = 295. Среднее значение основано на теории; сигма происходит от обширного моделирования. В тесте ДНК рассматривается алфавит из 4 букв C, G, A, T, определяемый двумя обозначенными битами в проверяемой последовательности случайных целых чисел. Он учитывает 10-буквенные слова, так что, как и в OPSO и OQSO, существует 2 28 возможных слов и среднее количество пропущенных слов в строке из 2 21 (перекрывающихся) 10-буквенных слов (2 21 + 9 "нажатий клавиш" ) составляет 141909. Стандартное отклонение sigma = 339 было определено, как и для OQSO, путем моделирования. (Сигма для OPSO, 290, это истинное значение (до трех разрядов), не определенное моделированием.
- Тест «подсчет единиц» в потоке байтов : рассматривайте тестируемый файл как поток байтов (четыре на 32-битное целое число). Каждый байт может содержать от нуля до восьми единиц с вероятностями 1, 8, 28, 56, 70, 56, 28, 8, 1 больше 256. Теперь пусть поток байтов предоставляет строку перекрывающихся пятибуквенных слов, каждое из которых " буква "принимает значения 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 возможных пятибуквенных слов, и из строки из 256000 (перекрывающихся) пятибуквенных слов подсчет производится по частотам для каждого слова. Квадратичная форма в слабой инверсии ковариационной матрицы количества ячеек обеспечивает критерий chisquare 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 возможных 5-буквенных слов, и из строки из 256 000 (перекрывающихся) 5-буквенных слов подсчет производится по частотам для каждого слова. Квадратичная форма в слабой инверсии ковариационной матрицы количества ячеек обеспечивает критерий chisquare Q5 - Q4, разность наивных сумм Пирсона (OBS - EXP) 2 ÷ EXP по счетам для 5- и 4-буквенного подсчета ячеек. .
- Тест на парковке : в квадрате со стороной 100 случайным образом «припаркуйте» машину - круг радиуса 1. Затем попробуйте припарковать вторую, третью и так далее, каждый раз паркуясь «на слух». То есть, если попытка припарковать автомобиль вызывает аварию с уже припаркованным, попробуйте еще раз в новом случайном месте. (Чтобы избежать проблем с маршрутом, подумайте о парковке вертолетов, а не автомобилей.) Каждая попытка приводит либо к аварии, либо к успеху, после чего следует приращение к списку уже припаркованных автомобилей. Если мы построим график n : количество попыток по сравнению с k числом успешно припаркованных, мы получим кривую, которая должна быть похожа на кривую, предоставляемую генератором идеальных случайных чисел. Теория поведения такой случайной кривой кажется недостижимой, и, поскольку графические дисплеи недоступны для этой серии тестов, используется простая характеристика случайного эксперимента: k , количество автомобилей, успешно припаркованных после n = 12000 попыток. Моделирование показывает, что 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 mod 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 31 = 2147483648, тест находит j , количество итераций, необходимых для уменьшения k до 1, используя сокращение k = потолок ( k × U ), с U, предоставленным целыми числами с плавающей запятой из проверяемого файла. Такие j s обнаруживаются 100000 раз, затем подсчеты того, сколько раз j было ≤ 6, 7, ..., 47, ≥ 48, используются для обеспечения теста хи-квадрат для частот ячеек.
- Проверка перекрывающихся сумм : целые числа перемещаются, чтобы получить последовательность U (1), U (2), ... однородных [0,1) переменных. Затем формируются перекрывающиеся суммы: S (1) = U (1) + ... + U (100), S (2) = U (2) + ... + U (101), .... В S с практически нормальным с определенной ковариационной матрицей. Линейное преобразование 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. Это делается десять раз. Потом повторил.
- Тест крэпса : он играет 200000 игр в крэпс, определяет количество побед и количество бросков, необходимых для завершения каждой игры. Количество побед должно быть (очень близко к) нормальным со средним значением 200000 p и дисперсией 200000 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. Когда битовый поток действительно НЕУДАЧЕН, вы получите p s от 0 или 1 до шести или более разрядов. Поскольку существует множество тестов, вполне вероятно, что p <0,025 или p > 0,975 означает, что ГСЧ «не прошел тест на уровне 0,05». Мы ожидаем, что количество таких событий p s произойдет среди сотен событий, производимых DIEHARD, даже при условии, что генератор случайных чисел идеален.
Смотрите также
Заметки
- ^ "The Marsaglia Random Number CDROM включая несгибаемую батарею испытаний случайности" . Государственный университет Флориды . 1995. Архивировано из оригинала на 2016-01-25. CS1 maint: обескураженный параметр ( ссылка )
- ^ Рение, 1953, Р194
- ^ https://webhome.phy.duke.edu/~rgb/General/dieharder.php
Внешние ссылки
- "CDROM случайных чисел Marsaglia, включающий стойкую батарею тестов на случайность" . Государственный университет Флориды . 1995. Архивировано из оригинала на 2016-01-25. CS1 maint: обескураженный параметр ( ссылка )
- Роберт Г. Браун. «Несгибаемый: набор тестов на случайные числа» .
- Реньи, Альфред (1953). «К теории порядковой статистики». Acta Mathematica Academiae Scientiarum Hungaricae . Acta Mathematica Hungarica. 4 (3–4): 191–231. DOI : 10.1007 / BF02127580 . hdl : 10338.dmlcz / 102650 . CS1 maint: обескураженный параметр ( ссылка )