Czy wszystkie generatory liczb pseudolosowych są ostatecznie okresowe?

24

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 ...

randomness pseudo-random-generators

7

Jest to pedantyczny punkt do zrobienia, ale na komputerze ze skończoną pamięcią każdy program bez zatrzymywania jest ostatecznie okresowy. Możesz przeanalizować algorytm działający na maszynie Turinga, ale każdy PRNG, którego użycie pamięci jest nieograniczone w czasie, nie byłoby zbyt praktyczne.

— Peter

@ Peter twierdzi, że „każdy PRNG, którego użycie pamięci jest nieograniczone w czasie, nie byłoby zbyt praktyczne”. Może nie być praktyczne, gdy użycie pamięci jest kwadratowe lub liniowe w stosunku do czasu, ale co, jeśli jest tylko logarytmiczne? Zobacz moją odpowiedź.

— Don Hatch

39

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}$

— Yuval Filmus
źródło

Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .

— DW

Link do czatu jest uszkodzony. Czy nadal można zobaczyć dziennik dyskusji? : / @DW

— oink

@ cchan3141, przywróciłem go; Spróbuj teraz. Uważaj jednak, że komentarze mają charakter przejściowy i to samo dotyczy pokojów czatowych. Jeśli znajdziesz tam coś, co ma trwałą wartość dla innych, zachęcam do zasugerowania edycji odpowiedzi w celu włączenia tych informacji lub opublikowania własnej odpowiedzi. Dziękuję Ci!

— DW

7

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.

— Luis Masuelli
źródło

6

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}$

— Don Hatch
źródło