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

Question

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Примечание о тестировании генератора случайных чисел: На самом деле нам не нужно слишком много тестов на ГСЧ, потому что многие «включают» друг друга.

Тем не менее, здесь описан простой эффективный новый Испытание упорядоченной частоты для битов. Этот тест включает в себя любой частотный тест, который ожидает 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 (т) поделить на 1 для 98-2 предыдущего умножить на 99 (т-1) разделить на 2 за 97-3 предыдущий умножить на 98 (т-2) разделить на 3 ... пропускать ... для 51-49 предыдущего умножить на 52 (т-48) разделить на 49 для 50-50 предыдущих, умноженных на 51 (t-49), делим на 50, затем снова делим на 2.

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

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

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

Шаг 4: значения p подаются на тест Колмогорова-Смирнова по прямой 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 очень прост. Он также довольно эффективен.

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

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

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

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

1. LCG 134775813x + 1 мод 2 ^ 31 семян = 11111: Старший бит: OFT KS: 0.0841 Pass. LOR KS: 0,04786 Pass. Монобит первых 200 000: -189 Pass. Бит 16: OFT KS: 0,5477 Fail. Монобит первого прохода 200 000: 114. Все биты от 0 до 15 не проходят OFT, но проходят тест Monobit.

2. Часто клеветнический 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.

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

4. LCG 3141592653x + 2718281829 мод 2 ^ 35 семян = 11111: Старший бит: OFT KS: 0,02868 LOR KS: 0,06117 Монобит 200 000: -69 Бит 16: OFT KS: 0,240 Монобит 200 000: -13 Все биты от 0 до 15 не проходят OFT.

5. LCG 23x + 0 мод 2 ^ 27 семян = 11111: Старший бит: OFT KS: 0,5368 Монобит 200 000: -235 Все биты не соответствуют OFT.

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

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

LWAP

Answer 4

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

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

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

См. Раздел исследования Charmaine Kenny для более подробной информации о тестах, которые вы могли бы выполнить.

Answer 5

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

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

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

Answer 6

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

Answer 7

Вы не можете гарантировать, что числа случайные, просто потому, что случайные числа, ну, в общем, случайные .

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

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

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

Answer 8

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

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

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

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

dieharder -a -g 202 -f random.txt

Answer 9

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

Answer 10

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

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