Как проверить случайные числа?
Я написал в matlab программу, которая генерирует случайные числа в диапазоне от 0 до 1. Я тестировал ее только с тестами в matlab, и в результате получается случайная последовательность. я тоже видел гистограммы, и у них есть бета-версия. я хочу проверить этот тест с помощью другого теста, такого как diehard, ent или nist, но я не знаю как. Может кто-нибудь объяснить, как их использовать, или предложить мне другие тесты случайности. благодарю вас
9 ответов
Здесь вы можете найти несложные тестовые программы и исходный код для разных операционных систем. Еще одна приятная ссылка может быть этой.
В большинстве тестов вы можете предоставить большой файл случайных чисел (целых или с плавающей запятой) и запустить различные тесты для этого файла примера. DIEHARD работал таким образом, если я правильно помню, и некоторые другие тоже. Если вы действительно хотите, чтобы ваш генератор вышел из строя, вы можете попробовать использовать TestU01 от Pierre L'Ecuyer, в котором достаточно тестов, чтобы почти каждый генератор мог провалить хотя бы один тест:-)
Тем не менее, для большинства наборов тестов имеется обширная документация, по крайней мере, я знаю это для DIEHARD, набора тестов от NIST SP 800-22, а также от DieHarder и TestU01 (ссылки ведут на документы). Способы предоставления случайных чисел для проверки обычно различны, но упомянуты в соответствующей документации.
Доступны следующие тесты:
Dieharder - http://www.phy.duke.edu/~rgb/General/dieharder.php
TestU01 - http://simul.iro.umontreal.ca/testu01/tu01.html
RaBiGeTe - http://cristianopi.altervista.org/RaBiGeTe_MT/
NIST STS - http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
PractRand - http://pracrand.sourceforge.net/
Любой из них может проверять биты из файла. Некоторые (PractRand, Dieharder, не уверены в TestU01) могут тестировать данные, передаваемые по стандартному вводу. Некоторые также поддерживают привязку вашего PRNG непосредственно к набору тестов, динамически (только RaBiGeTe предлагает реальную поддержку для динамического связывания вашего PRNG с ним) или статически.
Качество не равно. Если у вас есть много битов вывода PRNG, PractRand может найти самые разнообразные смещения быстрее всего (полное изложение: я написал PractRand), а затем TestU01. Если у вас нет много битов, RaBiGeTe может быть лучше. NIST STS и Dieharder в целом уступают.
Удобство интерфейса тоже не равное. PractRand и Dieharder настроены для автоматизации командной строки. PractRand и TestU01, как мне кажется, имеют самый простой выход для интерпретации. Dieharder неплох в этом отношении. RaBiGeTe и NIST STS, ну... они оба продвигают то, что мне кажется, как чрезмерно сложную и бесполезную визуализацию распределений результатов испытаний.
Кроме того, у NIST STS и Dieharder есть ложноположительные проблемы.
Также есть ENT, на данный момент не могу найти ссылку на него... он имеет довольно удобный интерфейс IIRC, но не очень хорош в поиске предвзятости.
Есть много вещей, чтобы проверить, если вы хотите проверить свой RNG самостоятельно. Вот несколько основных функций, которые могут показать, что ваша последовательность чисел не является действительно случайной или, возможно, неотличимой от случайной?
Взгляни на:
Распределение - вы уже провели некоторый анализ своего распространения. Вы хотите, чтобы каждое возможное число имело одинаковую вероятность появления.
Циклическое поведение - повторяется ли одна и та же последовательность снова и снова? Повторяющаяся последовательность может быть довольно длинной.
Наличие дубликатов (...C B B A F F...), триплетов (...C B A A A F...) и т. Д. Статистически в последовательности случайных чисел имеется определенная вероятность дубликатов (одно и то же число, сгенерированное дважды в строке).), триплеты и т. д. Рассчитайте эту вероятность и проверьте, имеет ли ваша последовательность псевдослучайных чисел такую же вероятность появления дубликатов?
Обратите внимание, что для большинства этих тестов вам нужно иметь довольно длинные последовательности случайных чисел, чтобы иметь возможность получать разумные и точные результаты статистического анализа.
Я предположил peudo последовательности случайных чисел целых чисел, которые легко исправить, умножив ваши [0, 1] числа на соответствующую константу.
Я рассматривал эту проблему в течение последнего года и пришел к выводу, что в реальном мире не существует стандартного способа проверки на случайность. Я думаю, это как раз то, что вам удобно. Вы не можете доказать, что последовательность случайна, и вы не можете легко доказать, что последовательность не случайна.
(Я исключаю случайные последовательности, которые на самом деле не случайны, как 0123456789... повторяю.)
user3535668 перечисляет некоторые широко известные тесты и целый список проблем с ними. Я могу добавить других. Diehard - насколько большим должен быть входной файл, и он должен состоять только из 32-битных целых чисел? ЛОР - кажется подходящим только для грубых ошибок, но тест ци полезен. Руководство пользователя NIST составляет>100 страниц - удачи. TestU01 - те же проблемы компиляции. И как только вы включили его в свой компьютер, он работает правильно? Как вы можете доверять результату? И как вы узнаете, что тест не прошел? Какой уровень p или KS считается слишком экстремальным?
Кроме того, я бы добавил, что вам следует рассмотреть возможность разработки тестовых наборов случайности по сравнению с реальной политикой. В интересах академика разработать тесты, которые дискредитируют генераторы случайных чисел. В конце концов, вы не получаете никакого финансирования, дающего результаты, которые говорят: "Все в порядке, ничего не найдено, никаких дополнительных исследований не требуется".
Читатели не согласятся с этой предпосылкой, но я предлагаю вам рассмотреть то, что происходит в реальном мире, в котором мы живем, а не на книжной полке академика. Там нет стандартного теста. Рассматривать:-
Random.org - использовал старшекурсника, чтобы провести домашние тесты для дипломной работы. И, по сути, посчитать количество 1 и 0. Лор делает подобное.
Hotbits - поборник упрощенного ENT и взломанной версии Dieharder, которую большинству людей будет сложно выполнить, не говоря уже о попытках понять множество инициализаторов тестов.
Публикации академического генератора - большая часть писем Кнута и техник домотканой работы. Некоторые используют некоторые из вышеперечисленных инструментов. Некоторые затем принимают ряд тестовых сбоев в этих комплектах.
Единственный пример, который я до сих пор нашел во вселенной этого человека, который, похоже, имеет какой-то реальный вес (т. Е. Если он потерпит неудачу, вы попадаете в тюрьму типа веса), - это сертификация Playtech PLC, британского поставщика игрового программного обеспечения. Они поставляют некоторые из крупнейших компаний, занимающихся онлайн-пари, где реальные деньги переходят из рук в руки Тем не менее, они используют домашние тесты и тест Diehard.
Мне лично нравится: -
- преобразовать файл темы в растровое изображение, чтобы посмотреть на него
- сожмите его с 7z на настройке Ultra, чтобы увидеть, станет ли он меньше
- возьмите Diehard и найдите глупые PS и KS.
Я думаю, что если файл пройдет мою личную 1 - 3, вам будет трудно доказать обратное. Кажется мне, как хорошая отправная точка, как и любой...
Для вашего конкретного случая использования я рекомендую записать 0 а также 1 числа, сгенерированные вашим rng как символы для файла, а затем использовать этот файл в качестве входных данных для программы набора тестов.
Обратите внимание, что последовательность должна быть длиной не менее 1000 символов для проверки STS.
Когда вы запустите его, не забудьте использовать флаг -F 'a', чтобы сообщить программе, что входной файл сделан из ASCII 0 а также 1 символы.
Я также рекомендую попробовать эту неофициальную версию NIST Statistical Test Suite, где я поэкспериментировал с исходным исходным кодом NIST и попытался оптимизировать его.
Для вашего удобства вот команда, которую я бы посоветовал вам использовать для запуска тестов с ней (после компиляции программы из исходников с $ make):
$ ./sts -v 1 -i 32 -I 1 -w . -F 'a' /path/to/input/file
Возможно, вы захотите увеличить количество протестированных битовых потоков (обозначенных -i флаг) к большему, чтобы использовать больше данных из ввода. Например, вы можете выбрать:
number of bitstreams = (number of 1 and 0 bits you generated) / 1048576
Как только все тесты будут выполнены, программа сгенерирует отчет в файле с именем result.txt, что вы можете использовать для оценки качества вашего рн.
Обратите внимание, что эта программа не является официальной NIST. Кроме того, наши модификации комплекта тестов не проходили стороннее тестирование; так что это как есть без каких-либо гарантий.
Я на самом деле ищу подобный тест, надеялся найти его здесь, но не нашел. Я попробую math.stackru.com, где я, вероятно, смогу спросить его, поскольку ответ является статистическим.
Мои статистические знания достаточно умеренные, чтобы знать, что вы ищете, не имея возможности предоставить точную информацию.
По сути, вы проводите регрессионный тест на предмет соответствия ваших чисел равномерному распределению. Таким образом, мы можем создать модель хи-квадрат (я думаю). Это приведет к получению t-stat и p-значения. Более высокое значение t-stat и более низкое значение p означает, что оно не соответствует распределению (таким образом, мы отвергаем нулевую гипотезу). Значение p будет между 0 и 1. Если это скажем 0,06, то мы можем отклонить нулевую гипотезу с уверенностью 94%.
И ответить тем, кто говорит: "Мы не должны создавать случайные числа", возможно, не фактические случайные числа, но мы можем получить данные и захотим проверить, соответствует ли они равномерному распределению, а для программистов мы можем захотеть проверить, есть ли хеш -функция производит равномерное распределение по большому количеству случайных экземпляров объектов, которые мы хэшируем.
Что касается кода для тестирования NIST, то здесь он есть:
http://sourceforge.net/projects/randomanalysis/
что может дать вам то, что вы хотите.
Вероятно, я бы выбрал способ визуального анализа результатов. Код для этого достаточно прост, как показано в следующем псевдокоде, основанном на его статье.
1. Создайте изображение размером х у
2. Для ndx = 0 до x
3. Для ndy = 0 до y
4. Пусть random будет случайным числом от 0 до 1
5. Если случайный = 1, установите точку изображения на ndx, ndy как черный
6. Показать сгенерированное изображение
Кроме того, Random.org имеет больше информации о статистическом анализе алгоритмов, но они также используют вышеупомянутую статью в качестве примера визуального анализа.
Ограничьте результат определенным диапазоном (возможно, используя оператор мода), запустите свой код несколько миллионов раз и посчитайте, сколько раз вы видите каждое число в диапазоне. Убедитесь, что счетчики примерно одинаковы, и что у вас нет смещения для каких-либо конкретных значений.
@ Анна, у меня был такой же вопрос, как и у тебя, и теперь я обнаружил Дихарда благодаря некоторым другим ответам.
Ситуация с моим RNG заключается в том, что он создает 1 и 0 и сохраняет их в файле ASCII. При попытке загрузить этот файл в онлайн-тесты на случайность он не удался - скорее всего потому, что данные должны быть в двоичном формате.
И это действительно так с Дихардом. Если вы установите Diehard, вы найдете файл с именем DIEHARD.DOC в котором рассказывается, как преобразовать файл ASCII в необходимые двоичные файлы (наряду с некоторыми другими изменениями, которые вам, возможно, придется внести в свою программу).
Во всяком случае, это мои первые шаги. Надеюсь, это кому-нибудь поможет.