Czy wszystkie generatory liczb pseudolosowych są ostatecznie okresowe?

Czy wszystkie generatory liczb pseudolosowych są ostatecznie okresowe? Czy w końcu są one okresowe?

Przez okresowe rozumiem, że podobnie jak liczby wymierne, ostatecznie generują okresowe podsekwencje ...

A pseudolosowe oznacza algorytmiczne / matematyczne generowanie liczb losowych ...

Wszystkie generatory pseudolosowe, które nie polegają na losowości z zewnątrz i używają ograniczonej ilości pamięci, są koniecznie ostatecznie okresowe, ponieważ mają stan skończony. Możesz myśleć o nich jak o ogromnych deterministycznych automatach skończonych, które mają specjalne stany „wyjściowe”, w których dają swoje wyniki. Wszystkie skończone automaty są ostatecznie okresowe, więc wszystkie generatory pseudolosowe generują ostatecznie okresowe dane wyjściowe.

Długość okresu może być jednak ogromna. Na przykład PRNG ze stanem kryptograficznym 128 bitów może cyklicznie tylko raz na bitów mocy wyjściowej, a więc nawet jeśli wysyłając jeden bit co nanosekundę, układ słoneczny będzie martwy, zanim PRNG się powtórzy.$2^{128}$

Jeśli PRNG może używać nieograniczonej ilości pamięci (co nie jest realistyczne), może na przykład wygenerować binarne rozszerzenie , o którym wiemy, że ostatecznie nie jest okresowe (od$\sqrt{2}$ jest irracjonalny).$\sqrt{2}$

PRNG są maszynami państwowymi. Jeśli są one oparte tylko na danych wewnętrznych (w przeciwieństwie do Poker Stars RNG, który jest połączeniem sprzętu i oprogramowania, wysiewającego się ciągle z ... próbek dźwięku), dostaniesz (C, S1, ...) gdzie C jest bieżącą (lub poprzednią) wartością, a S1, ... może być zbiorem stanów:

Jeśli możliwe są wartości N (ponieważ pamięć jest ograniczona) dla C i iterujesz N + 1 razy, co najmniej dwa razy osiągniesz tę samą wartość dla C. Jeśli powtórzysz 2N + 1 razy, uzyskasz tę samą wartość dla C co najmniej 3 razy.

Niech T = (Ct, S1t, S2t) będzie pewnym stanem (aktualna wartość i inne stany).
Niech M = # {wartości dla S1} X {wartości dla S2} X {...} będą kardynałem możliwych kombinacji stanów (ponownie: ponieważ pamięć jest ograniczona).

Jeśli iterujesz NM + 1 razy algorytm, osiągniesz co najmniej dwa razy ten sam stan (Ct, S1t, S2t, ...), generując w ten sposób tę samą wartość wyjściową i tę samą kolejność stanów niż za pierwszym razem, i tak staje się okresowe.

Prosty przykład pseudolosowej sekwencji, która nie jest okresowa: łącz binarne reprezentacje wszystkich liczb całkowitych dodatnich, w kolejności:

110111001011101111000...

(Przedrostek „.” I nazywa się to binarną stałą Champernowne .)

Oczywiście nie jest to bardzo wysoka jakość, jeśli chodzi o sekwencje pseudolosowe, ale pokazuje, że jest to możliwe bez użycia dużej ilości pamięci.

$\pi$$\sqrt{2}$

Wymagania dotyczące nieograniczonej pamięci nie stanowią problemu dla maszyny Turinga i prawdopodobnie nie jest to również problem w praktyce, ponieważ wzrost jest tak powolny, ale zależy to od tego, do czego zamierzasz użyć tej rzeczy.

$2^{128}$

$2^{128}$