Тестирование алгоритмов генерации случайных величин

Какие методы используются для тестирования алгоритмов генерации случайных величин?

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

РЕДАКТИРОВАТЬ

Я должен обновить это, так как я был не совсем прав: Diehard все еще мог бы использоваться много, но он больше не поддерживается и больше не является современным. С тех пор NIST предлагает набор улучшенных тестов .

Чтобы еще немного добавить ответ Хонка, набор тестов Diehard (разработанный Джорджем Марсалья) является стандартным тестом для PRNG.

Есть хорошая библиотека Diehard C, которая дает вам доступ к этим тестам. Наряду со стандартными тестами Diehard он также предоставляет функции для нескольких других тестов PRNG, включая (среди прочего) проверку порядка битов. Существует также возможность проверить скорость ГСЧ и написать свои собственные тесты.

Существует интерфейс R для библиотеки Dieharder, который называется RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

Это показывает, что генератор RANDU RNG не прошел тест минимального расстояния / 2dsphere.

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

Лучшим кандидатом для определения случайной последовательности представляется случайность Мартина-Лёфа . Основная идея такого рода случайности, прекрасно развитая в разделе 3.5 Кнута, состоит в проверке однородности для всех типов подпоследовательностей последовательности случайных чисел. Получить правильное определение всех типов подпоследовательностей оказалось очень сложно, даже если использовать понятия вычислимости.

Тесты Диарда - это лишь некоторые из возможных подпоследовательностей, которые можно рассмотреть, и их неудача исключает случайность Мартина-Лёфа.

Вы не можете доказать, потому что это невозможно; Вы можете только проверить, нет ли каких-либо неловких автокорреляций или нарушений распределения, и действительно, Diehard является стандартом для этого. Это для статистики / физики, криптографы также будут в основном проверять (среди прочего), насколько сложно приспособить генератор к данным для получения будущих значений.

Небольшое исправление к посту Колина: пакет CRAN RDieHarder - это интерфейс к DieHarder , переписывание / расширение / переработка Diehard, выполненная Робертом Брауном (который любезно перечисляет меня в качестве соавтора на основе моих упаковщиков RDieHarder) с недавним вкладом Дэвида Бауэра.

Среди прочего, DieHarder включает в себя батарею NIST тестов, упомянутых в посте Марка, а также некоторые новые. Это постоянное исследование, которое проводилось какое-то время. Я прочитал доклад на useR! 2007 о RDieHarder, который вы можете получить здесь .

Редко полезно сделать вывод, что что-то «случайно» в абстрактном. Чаще вы хотите проверить, имеет ли он определенную случайную структуру. Например, вы можете проверить, имеет ли что-то равномерное распределение, причем все значения в определенном диапазоне одинаково вероятны. Или вы можете захотеть проверить, имеет ли что-то нормальное распределение, и т. Д. Чтобы проверить, есть ли у данных конкретное распределение, вы можете использовать критерий достоверности соответствия, такой как критерий хи-квадрат или критерий Колмогорова-Смирнова.

Тестирование генератора случайных чисел состоит из двух частей. Если вас интересует только тестирование унифицированного генератора, тогда да, что-то вроде набора тестов DIEHARD - хорошая идея.

Но часто вам нужно проверить преобразование равномерного генератора. Например, вы можете использовать унифицированный генератор для создания экспоненциально или нормально распределенных значений. У вас может быть высококачественный унифицированный генератор - скажем, у вас есть надежная реализация хорошо известного алгоритма, такого как Mersenne Twister - но вам нужно проверить, имеет ли преобразованный выход правильное распределение. В этом случае вам нужно сделать какой-нибудь тест на пригодность, такой как Колмогоров-Смирнов. Но для начала вы можете убедиться, что выборочное среднее и дисперсия имеют ожидаемые значения.

Большинство людей не пишут и не должны писать свой собственный генератор случайных чисел с нуля. Трудно написать хороший генератор и легко обмануть себя, думая, что вы написали хороший генератор, когда у вас его нет. Например, Дональд Кнут рассказывает во втором томе TAOCP историю о генераторе случайных чисел, который он написал, который оказался ужасным. Но людям часто приходится писать свой собственный код для получения случайных значений из нового дистрибутива.

NIST публикует перечень статистических испытаний с эталонной реализацией в C.

Существует также TestU01 от некоторых умных людей, в том числе уважаемый исследователь PRNG Пьер Л'Экуайер. Опять же, есть эталонная реализация на C.

Как отмечают другие комментаторы, они предназначены для проверки генерации псевдослучайных битов. Если вы преобразуете эти биты в другую случайную переменную (например, преобразование Бокса-Мюллера из равномерного в нормальное), вам понадобятся дополнительные тесты для подтверждения правильности алгоритма преобразования.