Сколько состояний в PRNG (скажем, Mersenne Twister) и каково распределение по следующему состоянию?

Генераторы псевдослучайных чисел (PRNG) работают, применяя детерминированную функцию к текущему состоянию, чтобы определить следующее состояние, а затем проецируя это состояние на количество возвращаемых битов. Спрашивать, «каково распределение по следующему состоянию, если вы выходите в каком-то текущем состоянии», по сути, бессмысленно. Поскольку преобразование является детерминированным, из любого заданного состояния существует одно и только одно состояние, которое будет следующим. В конце концов вы неизбежно вернетесь к какому-то ранее наблюдаемому состоянию, и с этого момента состояния и соответствующие им выходные проекции будут повторяться в идентичном порядке, и мы говорим, что ваш ГПСЧ зациклился. Длина цикла определяется количеством уникальных состояний, достижимых из вашей начальной точки (исходное состояние), и ограничена, но не обязательно равна размеру пространства состояний. Например, есть функции, которые будут выдавать четные числа только в случае четного числа или нечетные числа в случае нечетного числа. Ни в одном из этих случаев перед повторением не будут получены все возможные целые числа.

Mersenne Twister достигает длины цикла 2¹⁹⁹³⁷-1, имея пространство состояний с 19937 битами. (Если я правильно помню, -1 означает, что состояние со всеми 0 недостижимо из любого другого ненулевого состояния.) Что касается вероятности перекрытия состояний в двух прогонах, забудьте об этом. Чтобы дать вам представление о величине 2¹⁹⁹³⁷-1, рассмотрим следующее. По оценкам физиков, их примерно 10⁸⁰ = 2²⁶⁶. субатомные частицы в известной Вселенной. Если вы запустили свои прогоны независимо, используя инициализацию полного состояния (например, прочитав 2,5 КБ из /dev/random в буфер байтов), даже если вы используете 10¹⁰ случайных чисел, вы запрашиваете эквивалентно вероятности того, что вы дважды выберете одну и ту же субатомную частицу из 2^19937–300 вселенных. Этого просто не произойдет.