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

Ответ 1

Используйте чи-квадратное тестирование. На каком языке вы используете? Я могу предложить пример на С++. В основном

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

Ответ 2

В любом случае вы можете тестировать статистическую случайность, и это не доказывает криптографически сильную последовательность чисел. Статистически тестирование PRNG требует довольно много (10 или даже 100 Гбайт) сгенерированных битов.

Dieharder - очень хороший набор тестов.

http://www.phy.duke.edu/~rgb/General/dieharder.php

И TestU01 также хорошо известен.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

Ответ 3

Это очень сложная вещь.

Вы можете попробовать ENT из Fourmilab и сравните его с результатами против их RNG, HotBits. Вы также можете просмотреть Random.org.

Это также выглядит интересно: Diehard tests (я не работал с ним, хотя).

Ответ 4

Как убедиться, что генерируемые числа являются случайными.

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

Итак, если невозможно окончательно доказать случайность, что мы можем сделать вместо этого? Прагматический подход состоит в том, чтобы взять много последовательностей случайных чисел от данного генератора и подвергнуть их батарее статистических испытаний. Поскольку последовательности проходят больше тестов, уверенность в случайности чисел увеличивается, а также уверенность в генераторе. Однако, поскольку мы ожидаем, что некоторые последовательности появятся неслучайными (например, десять рулонов по шесть на нашей матрице), мы должны ожидать, что некоторые из последовательностей не пройдут, по крайней мере, некоторые из тестов. Однако, если многие последовательности не проходят тесты, мы должны быть подозрительными. Это также способ интуитивно протестировать кубик, чтобы увидеть, загружена ли она: прокручивайте его много раз, и если вы видите слишком много последовательностей с одинаковым значением, вы должны быть подозрительными.

Подробнее о тестах, которые вы можете запустить, см. в разделе Charmaine Kenny.

Ответ 5

Вот подробное объяснение того, как начать. Предварительным испытанием для любого RNG является тест Monobit, используемый NIST, который просто подсчитывает количество 1s и 0s. http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html

Примечание о тестировании генератора случайных чисел: На самом деле нам не нужно слишком много тестов RNG, потому что многие "подсоединяются" друг к другу.

Таким образом, описанный здесь представляет собой простой эффективный новый Упорядоченный частотный тест для бит. Этот тест включает любой частотный тест, ожидающий 50-50, потому что он более строгий.

Определения: t = тезисы/испытания b = бит/урны s = сеансы переходов n = наборы сеансов

Так как монеты, как правило, не 50-50, этот новый тест можно использовать с большой эффективностью, используя пул из 40 000 000 бит.

Когда монеты переворачиваются 100 раз, ожидаемые значения составляют 53.9795 из одного и 46.0205 другого, иногда больше голов, иногда больше хвостов. 50-50 не является ожидаемым значением упорядоченных бункеров, поэтому этот тест превосходит любой частотный тест, который вместо этого ожидает 50-50.

Шаг 1: Выбор размера выборки: 100 томов/бит.

Шаг 2: Выбор количества сеансов: 50 сеансов никогда не бывает достаточным, даже с огромными размерами выборки в миллионах. 400, как правило, достаточно. 2000 сходится хорошо, поэтому используются 2000 различных выборок 100 томов. Минимальное усиление происходит выше 2000 года.

Ожидаемые значения для 2000 сеансов из 100 бросков: 50-50 159.1784748 (Обратите внимание, что 50-50 составляет всего 7,96% времени). 51-49 312.1146564 52-48 294,1080416 53-47 266,362 54-46 231,8335926 55-45 193,8971865 56-44 155,8102392 57-43 120,2745706 58-42 89,16907819 59-41 63,47629295 60-40 43.37546685 61-39 28.4429291 62-38 17,89152 63-37 10,79171042 64-36; 6.238957586 65-35 3.455422663
66-34 1.832421109 67 или более 1.747439674

Уравнение для получения точных процентов для бункеров b = 2 и томов t = 100: Для 100-0 коэффициенты равны 1/(2 ^ 99) = 1/(2 ^ (t-1)) Затем, построив оттуда, для 99-1 предыдущего умножено на 100 (t) делить на 1 для 98-2 предыдущего умножается на 99 (t-1) делить на 2 для 97-3 предыдущего умножено на 98 (t-2) делить на 3 ... пропускать... для 51-49 предыдущего умножено на 52 (t-48) делить на 49 для 50-50 предыдущих умноженных на 51 (t-49) разделите на 50, затем снова разделите на 2.

Это уравнение работает с любым количеством бросков.

Шаг 3: Хи-квадрат берется по этим 18 значениям с 17 степенями свободы, дающими результирующее значение p.

p выше 0,999 близки к совершенству. Может ли RNG слишком близко к совершенству слишком часто? Да, слишком предсказуемо. Менее 0,001 - это когда обычно возникают определенные проблемы. Один тестовый набор считает 300 нулей справа от десятичной дроби как бесконечно плохую и 10-14 в ряд как довольно плохую. Некоторые считают 6 нулей достаточно плохими, чтобы квалифицироваться как явный явный провал. Некоторые, ради безопасности, считают достаточно 1 или 2 нулей, и они ошибаются. Таким образом, вместо одного значения p для одного набора, иногда предоставляющего значение p ниже 0,01 для отличного RNG, выполняется множество наборов сеансов.

Шаг 4: значения р подаются на тест линии Колмогорова-Смирнова 0-1.0. Различные эксперты рекомендуют, чтобы количество входов в тест K-S составляло от 10 до 1000. 100 недостаточно. 200 в порядке. 500 немного агрессивен.

Здесь псевдокод, чтобы получить максимальную разность K-S:

Set low := 0;  Set n := 200;  
Set ansForward := 0; Set ansBack := 0;

sort( pval [n] );
for (j := 0; j < n; j := j+1)   
 {  Set Kback := pval [ j ] - low;
    Set low := low +1 / n;    { Ranges from 0 to 1 }
    Set Kforward := low - pval [ j ];  
    if (Kforward > ansForward) Set ansForward := Kforward;
    if (Kback > ansBack) Set ansBack := Kback;
   }
{ Separate analysis can perhaps be made here on ansForward and ansBack.  Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
      return ansForward;
else
      return ansBack;   ∎

Ответ K-S не является значением p и не должен превышать 0.115 для значений 200 p. 0,03-0,08 является нормальным для хорошего RNG. От 0,115 до 0,13 является подозрительным.

Тест K-S очень прост. Он также довольно эффективен.

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

OFTest не включает тест LOR. Рекомендуемый тест длины пробега с размером выборки 200 000 с 15 степенями свободы, поданным в тест K-S 200 раз. (Обратите внимание, что ожидаемое общее количество наименьшего лога LOR для "больше j" равно j-му биту.)

И что тогда? Для многих игр эти два теста - все, что вам нужно. Есть склонность выбора от NIST, Diehard, Dieharder, Crusher. (Примечание: тест Diehard Overlapping Sums является как неполным, так и ошибочным, а не точной интерпретацией оригинального кода Fortran от Marsaglia.)

Результаты нескольких RNG с n = 200.

• LCG 134775813x + 1 mod 2 ^ 31 seed = 11111: Высокий бит: OFT KS: 0.0841 Пасс. LOR KS: 0.04786 Пасс. Монобит первых 200 000: -189 Пасс. Бит 16: OFT KS: 0,5477 Сбой. Монобит первых 200 000: 114 проходов. Все биты от 0 до 15 выходят из строя OFT, но проходят тест Monobit.

• Отдельный злокачественный LCG Randu: 65539x + 0 mod 2 ^ 31 seed = 11111:
  Высокий бит: OFT KS: 0,03567 LOR KS: 0,07709. Монобит первых 200 000: -165 Бит 18: OFT KS: 0,15143 Монобит первых 200 000: +204 Все биты от 0 до 17 вызывают OFT.

• LCG 69069x + 1 mod 2 ^ 32 seed = 11111: Высокий бит: OFT KS: 0,0547 LOR KS: 0,0456 Монобит 200 000: -290 Бит 17: OFT KS: 0,1467 Монобит 200 000: -193 Все биты от 0 до 13 вызывают OFT.

• LCG 3141592653x + 2718281829 mod 2 ^ 35 seed = 11111: Высокий бит: OFT KS: 0.02868 LOR KS: 0.06117 Monobit 200 000: -69 Бит 16: OFT KS: 0,240 Монобит 200 000: -13 Все биты от 0 до 15 вызывают OFT.

• LCG 23x + 0 mod 2 ^ 27 seed = 11111: Высокий бит: OFT KS: 0,5368 Monobit 200 000: -235 Все биты терпят неудачу OFT.

Обратите внимание, что низкие бит любого и каждого LCG должны быть отброшены из возвращаемого результата.

Примечание о 2 ^ 35: Это минимальный период и значение для любого RNG, потому что монеты переворачиваются и дерьмо запускаются, и такие вещи могут происходить 30 раз подряд, но 35, как ожидается, не произойдет. Период 2 ^ 32 недостаточен, слишком мал для реальных жизненных ситуаций.

LWAP

Ответ 6

Вы не можете гарантировать, что цифры являются случайными, просто потому, что случайные числа, ну, случайные.

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

На достаточно большом образце они должны быть примерно одинаковыми.

Еще одна возможность - проверить на неповторимость. В идеале случайные числа не должны зависеть от числа, которое было раньше. Очень простые (линейные конгруэнтные) PRNG, скорее всего, дадут вам одну и ту же последовательность чисел в конце концов, но на достаточно большом наборе, который вам, вероятно, не понравится (если вы не серьезно относитесь к случайности).

Ответ 7

Покажите это в комнате, полной разработчиков.

Ответ 8

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

Ответ 9

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

http://burtleburtle.net/bob/rand/testsfor.html

Ответ 10

Это зависит от того, насколько серьезно ваше требование к случайности. Если он не слишком суровый, то я делаю, генерируя большое количество случайных чисел, нахожу их частоты, а затем использую частоты для построения графика с использованием метода распространения, такого как Open Office. Если распределение выглядит нормально, тогда я готов идти.

Ответ 11

Если у вас нет доступа к генератору случайных чисел и вы можете использовать его для генерации чисел по желанию, вы не можете проверить, является ли последовательность чисел случайной. Подумайте об этом: у вас есть генератор случайных чисел. Пусть говорят, что это равномерный генератор случайных чисел, порождающий случайные целые числа в диапазоне [0,9]. Учитывая последовательность:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

можете ли вы сказать, является ли это случайным? Существует конечная вероятность 10 ^{& minus; 10} что наш равномерный генератор случайных чисел будет генерировать эту точную последовательность. Фактически, при любой последовательности длиной -10, мы имеем ту же вероятность нашего равномерного генератора случайных чисел, порождающего эту последовательность. Следовательно, по определению вы не можете определить, является ли данная последовательность случайной.

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

Ответ 12

Вы не можете генерировать истинную случайность любым алгоритмом, таким образом, попытайтесь визуализировать свои результаты и проверить свои шаблоны своими глазами. Ни один случайный генератор (по алгоритму) не создавал бы некоторые шаблоны, которые вы можете судить сами. Вот одна из демонстраций этой идеи: http://www.alife.co.uk/nonrandom/

Ответ 13

Есть хороший инструмент для этого puprose: http://www.phy.duke.edu/~rgb/General/dieharder.php

например, вы можете проверить встроенный urandom

cat /dev/random | dieharder -a -g 200

Или напишите свой собственный script, который создаст файл со случайными номерами

dieharder -a -g 202 -f random.txt