Являются ли все генераторы псевдослучайных чисел в конечном итоге периодическими?

Являются ли все генераторы псевдослучайных чисел в конечном итоге периодическими? Или они вообще периодичны?

Под периодическим я подразумеваю, что, подобно рациональным числам, они в конце концов генерируют периодическую подпоследовательность ...

И псевдослучайный означает алгоритмическую / математическую генерацию случайных чисел ...

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

Однако продолжительность периода может быть огромной. Например, PRNG с криптографическим состоянием 128 битов может циклически повторяться один раз каждые битов вывода, и поэтому даже если выводить один бит каждую наносекунду, солнечная система будет мертвой до повторения PRNG.$2^{128}$

$\sqrt{2}$$\sqrt{2}$

PRNG - это конечные автоматы. Если они основаны только на внутреннем вводе (в отличие от Poker Stars RNG, представляющего собой комбинацию аппаратного и программного обеспечения, непрерывно выделяющегося из ... звуковых образцов), вы получите (C, S1, ...) где C текущее (или предыдущее) значение, а S1, ... может быть набором состояний:

Если есть возможные значения N (так как память ограничена) C, и вы повторяете N + 1 раз, вы получите одно и то же значение для C как минимум дважды. Если вы повторяете 2N + 1 раз, вы получите одно и то же значение для C как минимум 3 раза.

Пусть T = (Ct, S1t, S2t) - определенное состояние (текущее значение и другие состояния).
Пусть M = # {значения для S1} X {значения для S2} X {...} - кардинал возможных комбинаций состояний (опять же: поскольку память ограничена).

Если вы повторяете алгоритм NM + 1 раз, вы достигнете, по крайней мере, в два раза одного и того же состояния (Ct, S1t, S2t, ...), создавая, таким образом, такое же выходное значение и ту же последовательность следующих состояний, что и в первый раз, и так становится периодическим.

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

110111001011101111000...

(Добавьте «.» И это называется двоичной константой Champernowne .)

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

$\pi$$\sqrt{2}$

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

$2^{128}$

$2^{128}$