Как доказать, что один генератор случайных чисел лучше другого?

Question

Как вы докажете, что один ГСЧ лучше другого?

Я имею в виду не время выполнения, а количество «генерируемой» энтропии, которое также сворачивается в понятие периодичности (низкий период = низкая энтропия).

Может ли ГСЧ быть доказуемо оптимальным? Или это недостижимая цель? Под оптимальным я подразумеваю, что любая последовательность одинаково вероятна и не зависит от прошлых или будущих результатов.

Меня интересуют алгоритмы, а не устройства космической выборки фона или другие источники физической "случайности" (это случайно или просто сложно?)

Answer 1

См. http://www.random.org/analysis/

Один и единственный оптимальный RNG:

Answer 2

У Национального института стандартов и технологий есть хорошая информация по этому вопросу:

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Похоже, что есть набор тестов и много хороших справочных материалов

Answer 3

Существует объективное определение из теории вычислительной сложности: асимптотическая временная сложность, необходимая для различения выходных данных от случайных данных.

Хороший PRNG должен заставлять различающего тратить намного больше времени в качестве размера начального числаувеличивается или по мере повышения требуемого уровня достоверности.(С семенами фиксированного размера, я полагаю, вы бы посмотрели как на фактическое время выполнения, так и на сложность программы.)

• Для сравнения одного PRNG с другим, тот, у кого меньший / более быстрый отличитель, хуже.
• Одно распространенное предположение, хотя оно и не было доказано, состоит в том, что некоторые PRNG неотличимы от случайных в полиномиальное время.Это одно из возможных значений слова «оптимальный».
• Статистические тесты, такие как твердолобый тест , являются просто простыми отличительными признаками.

Answer 4

Раньше старым стандартом для испытаний были «твердые испытания». http://en.wikipedia.org/wiki/Diehard_tests Это было заменено тестами NIST, на которые указал DKnight: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html. Статья в вики Diehard дает вам хороший обзор того, на что смотрят. Бит NIST займет немного больше копания.

Как вы утверждаете, ни один псевдо-ГСЧ (алгоритм) не может быть признан оптимальным. Все они имеют начальное значение и зависят от входных данных для генерации значения. Если вы знаете семя и состояние, вы знаете следующее значение. В качестве примера, посмотрите http://en.wikipedia.org/wiki/Mersenne_twister. Мне нравится это в основном из-за удивительного названия, но статья хорошо объясняет принципы PRNG.

Answer 5

Основы из книги Кнут, «Искусство компьютерного программирования», том 2, «Получисленные алгоритмы». Идея состоит в том, чтобы разработать тесты случайности, где каждый тест будет пытаться найти неслучайные аспекты PRNG. Обратите внимание, что то, что может показаться человеку случайным, не является таковым. Например, мы склонны говорить, что последовательность '1,4,4,1', например, не является случайной, тогда как она может происходить идеально на большей случайной последовательности.

Итак, подход примерно такой:

• Найдите различные тесты на случайность, это по существу группы тестирования DieHard и NIST.
• Выполнить указанные тесты на PRNG.
• Если PRNG не проходит один или несколько тестов, его можно воспринимать как более слабый PRNG, чем выживший.

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

http://lcamtuf.coredump.cx/oldtcp/tcpseq.html

Другими классическими тестами являются хи-квадраты, Комолгорова-Смирнова и т. Д., Все объясненные в Кнуте. Хорошие PRNG выживают при любой возможной атаке на них.

Answer 6

Создайте последовательности чисел, а затем попытайтесь сжать их.Более случайные из них будут сжиматься меньше.Чистая случайность несжимаема.Было бы интересно увидеть результаты, и если будут различия.