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

Ответ 1

Здесь вы можете найти тесты с жестким контролем и исходный код для разных операционных систем. Еще одна приятная ссылка может быть этот.

Ответ 2

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

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

Ответ 3

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

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 может найти самый широкий спектр предвзятостей быстрее всего (полное diclosure: я написал PractRand), а затем TestU01. Если у вас не так много бит, RaBiGeTe может сделать лучше. NIST STS и Dieharder обычно хуже.

Удобство интерфейса также не равно. PractRand и Dieharder настроены для автоматизации командной строки. PractRand и TestU01 имеют тенденцию иметь самый легкий выход для интерпретации, на мой взгляд. Dieharder не плохо в этом отношении. RaBiGeTe и NIST STS, ну... они оба способствуют тому, что мне кажется излишней и бесполезной визуализацией распределений результатов тестов.

Кроме того, у NIST STS и Dieharder есть ложные положительные проблемы.

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

Ответ 4

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

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

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

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

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

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

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

Ответ 5

Для вашего конкретного случая использования я рекомендую записать номера 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, который вы можете использовать для оценки качества вашего rng.

Обратите внимание, что эта программа не является официальным NIST. Кроме того, наши модификации тестового набора не прошли тестирование сторонних производителей; поэтому его AS-IS без каких-либо гарантий.

Ответ 6

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

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

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

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

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

Random.org - использовал подзаголовок для проведения некоторых тестов доморощенного для диссертации. И по существу подсчитайте количество 1 и 0. ENT делает подобное.

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

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

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

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

• преобразуйте файл темы в растровое изображение, чтобы посмотреть на него.
• сжимайте его с помощью 7z на настройке Ultra, чтобы увидеть, будет ли он меньше.
• возьмите Diehard, запустите его и найдите глупые ps и KS.

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

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

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

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

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

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

Ответ 10

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

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

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

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