Как проверить случайные числа?

Question

Я написал в matlab программу, которая генерирует случайные числа в диапазоне от 0 до 1. Я тестировал ее только с помощью прогона в Matlab, и в результате получается, что последовательность случайна. я тоже видел гистограммы, и у них есть бета-версия. Я хочу проверить этот тест с помощью другого теста, такого как diehard, ent или nist, но я не знаю как. Может кто-нибудь объяснить, как их использовать, или предложить мне другие тесты случайности. спасибо

Answer 1

В большинстве тестов вы можете предоставить большой файл случайных чисел (целых или с плавающей запятой) и запустить различные тесты для этого файла примера. DIEHARD работал таким образом, если я правильно помню, и некоторые другие тоже. Если вы действительно хотите увидеть, что ваш генератор вышел из строя, вы можете попробовать использовать TestU01 от Pierre L'Ecuyer, в котором достаточно тестов, чтобы позволить почти каждому генератору провалить хотя бы один тест: -)

Тем не менее, для большинства наборов тестов имеется обширная документация, по крайней мере, я знаю это для DIEHARD , набора тестов от NIST SP 800-22 , а также DieHarder и TestU01 (ссылки ведут в документы). Способы предоставления случайных чисел для проверки обычно различны, но упомянуты в соответствующей документации.

Answer 2

Доступны следующие тесты:

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, но не очень хорош в поиске предвзятости.

Answer 3

Есть много вещей, которые нужно проверить, если вы хотите проверить свой ГСЧ самостоятельно. Вот несколько основных функций, которые могут показать, что ваша последовательность чисел не является действительно случайной или, возможно, неотличимой от случайной?

Взгляните на:

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

2. Циклическое поведение - повторяется ли одна и та же последовательность снова и снова? Повторяющаяся последовательность может быть довольно длинной.

3. Вхождение дубликатов (... CBBAF F ...), триплетов (... CBAAA F ...) и т. Д. Статистически в последовательности случайных чисел у вас есть определенный вероятность дубликатов (одно и то же число, сгенерированное дважды в строке), триплетов и т. д. Вычислите эту вероятность и проверьте, имеет ли ваша последовательность псевдослучайных чисел одинаковую вероятность появления дубликатов?

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

Я предположил последовательность случайных чисел из целых чисел, которую легко исправить, умножив числа [0, 1] на соответствующую константу.

Answer 4

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

Обратите внимание, что последовательность должна быть длиной не менее 1000 символов для проверки STS.

При запуске не забудьте использовать флаг -F 'a', чтобы сообщить программе, что входной файл состоит из символов ASCII 0 и 1.

---

Я также рекомендую попробовать эту неофициальную версию набора статистических тестов NIST, где я поэкспериментировал с исходным исходным кодом 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. Кроме того, наши модификации комплекта тестов не проходили стороннее тестирование; так что все как есть, без каких-либо гарантий.

Answer 5

Я рассматривал эту проблему в течение последнего года и пришел к выводу, что в реальном мире не существует стандартного способа проверки на случайность. Я думаю, что это именно то, что вам удобно. Вы не можете доказать, что последовательность случайна, и вы не можете легко доказать, что последовательность не случайна.

(я исключаю случайные последовательности, которые действительно не случайны, как 0123456789 ... повторяющиеся.)

user3535668 перечисляет некоторые широко известные тесты и целый список проблем с ними. Я могу добавить других. Diehard - насколько большим должен быть входной файл, и он должен состоять только из 32-битных целых чисел? ЛОР - кажется подходящим только для грубых ошибок, но тест ци полезен. Руководство пользователя NIST> 100 страниц в длину - удачи. TestU01 - те же проблемы компиляции. И как только вы включили его в свой компьютер, он работает правильно? Как вы можете тогда доверять выводу? И как вы узнаете, что тест не прошел? Какой уровень p или KS считается слишком экстремальным?

Я бы также добавил, что вам следует рассмотреть вопрос о разработке наборов тестов случайности по отношению к реальной политике. В интересах академика разработать тесты, которые дискредитируют генераторы случайных чисел. В конце концов, вы не получаете никакого финансирования, дающего результаты, которые говорят: «Все в порядке, ничего не найдено, никаких дальнейших исследований не требуется».

Читатели не согласятся с этой предпосылкой, но я предлагаю вам подумать о том, что происходит в реальном мире, в котором мы живем, а не на книжной полке академика. Там нет стандартного теста. Рассмотрим: -

Random.org - использовал старшекурсника, чтобы провести домашние тесты для дипломной работы. И по существу посчитать количество 1 и 0. ЛОР делает подобное.

Hotbits - поборник упрощенной ENT и взломанной версии Dieharder, которую большинству людей будет сложно выполнить, не говоря уже о попытках понять множество инициализаторов теста.

Академические генераторные работы - много обращений к сочинениям Кнута и домотканым техникам. Некоторые используют некоторые из вышеперечисленных инструментов. Некоторые из них затем принимают ряд тестовых сбоев в этих комплектах.

Единственный пример, который я до сих пор обнаружил во вселенной этого человека, который, похоже, имеет какой-то реальный вес (т. Е. Если он потерпит неудачу, вы попадаете в тюрьму), это сертификация Playtech PLC, британского поставщика игрового программного обеспечения. Они поставляют некоторые из крупнейших компаний, занимающихся онлайн-пари, где реальные деньги переходят из рук в руки Тем не менее, они используют домашние тесты и тест Diehard.

Мне лично нравится: -

1. преобразовать файл темы в растровое изображение, чтобы посмотреть его
2. сожмите его с 7z на настройке Ultra, чтобы увидеть, станет ли оно меньше
3. Беги на него и смотри на глупые пс и КС.

Я думаю, что если файл пройдет мою личную 1 - 3, вам будет трудно доказать обратное. На мой взгляд, это хорошая отправная точка, как и любая другая ...

Answer 6

@ Анна У меня был такой же вопрос, как и у тебя, и я обнаружил Diehard благодаря некоторым другим ответам.

Ситуация с моим RNG заключается в том, что он создает 1 и 0 и сохраняет их в файле ASCII. При попытке загрузить этот файл в онлайн-тесты на случайность он не удался - скорее всего, потому что данные должны быть в двоичном формате.

И это действительно так с Дихардом. Если вы установите Diehard, вы найдете файл с именем DIEHARD.DOC, в котором рассказывается, как преобразовать файл ASCII в необходимые двоичные файлы (наряду с некоторыми другими изменениями, которые вам, возможно, придется внести в вашу программу). *

В любом случае, это мои первые шаги. Надеюсь, это кому-нибудь поможет.

Answer 7

Я на самом деле ищу похожий тест, надеялся найти его здесь, но не нашел. Я попробую math.stackoverflow.com, где я, вероятно, смогу спросить его, поскольку ответ является статистическим.

Мои статистические данные достаточно умеренные, чтобы знать, что вы ищете, не имея возможности предоставить точную информацию.

По сути, вы проводите регрессионный тест на соответствие ваших чисел равномерному распределению. Таким образом, мы можем создать модель хи-квадрат (я думаю). Это приведет к получению t-stat и p-значения. Более высокое значение t-stat и более низкое значение p означает, что оно не соответствует распределению (таким образом, мы отвергаем нулевую гипотезу). Значение p будет в диапазоне от 0 до 1. Если, скажем, 0,06, мы можем отклонить нулевую гипотезу с уверенностью 94%.

И чтобы ответить тем, кто говорит: «Мы не должны создавать случайные числа», возможно, это не фактические случайные числа, но мы можем получить данные и захотим проверить, соответствует ли оно равномерному распределению, и для программистов мы можем захотеть проверить если хеш-функция производит равномерное распределение по большому количеству случайных экземпляров объектов, которые мы хэшируем.

Что касается кода для тестирования NIST, то здесь он есть:

http://sourceforge.net/projects/randomanalysis/

что может дать вам то, что вы хотите.

Answer 8

Маршрут, по которому я бы, вероятно, пошел, - визуальный анализ результатов. Код для этого достаточно прост, как показано в следующем псевдокоде на основе t его статьи .

1. Create an image of size x by y
2. For ndx = 0 to x
  3. For ndy = 0 to y
    4. Let random be a random number between 0 and 1
    5. If random = 1, set the image point at ndx, ndy as black
6. Display the generated image

Кроме того, Random.org имеет дополнительную информацию о статистическом анализе алгоритмов, но они также используют вышеупомянутую статью в качестве примера визуального анализа.

Answer 9

Ограничьте результат определенным диапазоном (возможно, используя оператор мода), запустите свой код несколько миллионов раз и посчитайте, сколько раз вы видите каждое число в диапазоне. Убедитесь, что счетчики примерно одинаковы, и что у вас нет смещения для каких-либо конкретных значений.