Matematyka.pl

Nie wiem od czego zacząć, żeby opis problemu nie był zbyt długi, ale postaram się w miarę streścić. Generatory liczb pseudolosowych możemy podzielić na 3 rodzaje:

1. Takie, które generują liczby w pewnym cyklu, którego długość znamy. Generator po pewnym czasie się zapętla i generuje jeszcze raz te same liczby w tej samej kolejności. Każde ziarno (seed) znajduje się w cyklu.

2. Takie które bazują na losowych permutacjach (patrz: random permutation statistics, wikipedia), funkcja, która jest w generatorze po wprowadzeniu do niej liczb \(\displaystyle{ 1,2,3,...}\) tworzy pewną permutację (pseudolosową). W przypadku takiego generatora, jeżeli zainicjujemy go jakimś ziarnem nie znamy długości cyklu, taka losowa permutacja ma bowiem kilka cykli o różnej długości i nie wiemy na jaki cykl trafimy. Możemy to natomiast szacować, potrafimy policzyć spodziewaną długość cyklu.

3. Takie, które bazują na tzw. random non-invertible mappings (czyli chyba możemy to przetłumaczyć jako losowe nieodwracalne odwzorowania - możemy generować liczby "w przód", a nie ma jednego sposobu w jaki możemy się cofać w generatorze, taki generator może bazować na nieodwracalnych arytmetycznie operacjach, jak np. mnożenie przez liczbę nieparzystą modulo \(\displaystyle{ 2^{n}}\)): W przypadku takiego generatora najczęściej generuje on pewną liczbę liczb (path to reach cycle), po czym wpada w cykl. Oczywiście może się zdarzyć, że zainicjujemy go w taki sposób, że od razu będziemy w cyklu, ale spodziewana długość ścieżki do cyklu nie jest zerowa, podobnie jak spodziewana długość cyklu, każda z nich wynosi \(\displaystyle{ \sqrt {\pi \cdot \frac {N}{8}}}\) (gdzie \(\displaystyle{ N}\) to wielkość stanu generatora). Ponownie możemy mówić tu tylko o wartościach oczekiwanych (statystyki pochodzą z publikacji "Random Mapping Statistics", Philippe Flajolet i Andrew M. Odlyzko).

Po to, żeby nie mieć problemu ze zbyt krótkimi cyklami generatorów PRNG niektórzy posłużyli się pewnym schematem. Historycznie bodajże pierwszy zrobił to George Marsaglia w "Xorshift RNGs". Do stanu generatora o pewnej długości cyklu \(\displaystyle{ 2^{n}-1}\) dodał on tzw. Weyl sequence. Weyl sequece to po prostu sekwencja liczb obliczania według wzoru:

\(\displaystyle{ w_{n+1} = w_{n} + s}\)

gdzie \(\displaystyle{ s}\) to jakaś stała. W praktyce ze względu na skończoną precyzję różnych typów zmiennych oblicza się:

\(\displaystyle{ w_{n+1} = (w_{n} + s) \mod 2^{m}}\)

I sekwencja ma cykl o długości \(\displaystyle{ 2^{m}}\). Jeżeli mamy jakiś generator, który oblicza stan \(\displaystyle{ x}\) za pomocą funkcji \(\displaystyle{ f(x)}\), to w kolejnym kroku dodajemy lub xorujemy weyl sequence z \(\displaystyle{ x}\):
Jeżeli oryginalny generator ma długość cyklu \(\displaystyle{ 2^{n}-1}\), to w ten sposób uzyskujemy długość cyklu takiego nowego generatora wynoszącą \(\displaystyle{ (2^{n}-1) \cdot 2^{m}}\). Podobne rozwiązanie zastosował Widynski w "Middle-Square Weyl Sequence RNG": Tyle, że wziął on generator Middle-Square, który działa właśnie jak non-invertible mapping. Autor pisze, że dodanie Weyl sequence gwarantuje, że przez pierwsze \(\displaystyle{ 2^{64}}\) iteracji generator się nie zapętli. Podaje tam też dowód jednorodności generatora.

Moje pytanie dotyczy tego ile wynosi długość ścieżki do cyklu i cyklu w tak zbudowanym generatorze? Moje doświadczenia z generatorem Middle-Square Weyl ze zmniejszonym stanem wskazują, że ścieżka do cyklu nadal wynosi \(\displaystyle{ \sqrt {\pi \cdot \frac {N}{8}}}\), natomiast sama długość cyklu, gdy generator już w niego wpadnie wynosi tyle co długość cyklu Weyl sequence. Ale, czy to na sens? Jak to udowodnić?

Mam też drugi problem. Mam jeszcze bardziej skomplikowany generator stworzony przeze mnie, działa on podobnie:
Mamy tu kolejną zmienną \(\displaystyle{ k}\), która jest dodawana do stanu generatora \(\displaystyle{ x}\), a samo \(\displaystyle{ x}\) również jest sumowanie z \(\displaystyle{ k}\). Taki generator według moich pomiarów również ma jakąś ścieżkę do cyklu, prawdopodobnie o oczekiwanej długości \(\displaystyle{ \sqrt {\pi \cdot \frac {N}{8}}}\) oraz cykl o oczekiwanej długości prawdopodobnie \(\displaystyle{ \lfloor \sqrt {\pi \cdot \frac {N}{8}} \rfloor \cdot 2^{n}}\), gdzie \(\displaystyle{ 2^{n}}\) to długość cyklu Weyl sequence. Nie wiem natomiast jak to wyznaczyć analitycznie.

Ponadto pytanie, czy, jeśli rozpatrzymy sobie zmodyfikowany generator Widynskiego:
gdzie \(\displaystyle{ k}\) to kolejna zmienna, która może być dowolnie zainicjowana, to nadal możemy udowodnić jego jednorodność i brak powtórzeń przez cały okres Weyl sequence? Wydaje mi się, że dowody z jego publikacji można dosłownie przepisać i będą tak samo aktualne.

Zapomniałem o jeszcze jednej sprawie. Nic nie stoi na przeszkodzie, aby generator Widynskiego zanim się zapętli zwracał te same liczby kilkukrotnie. Tak się zresztą dzieje. Ponieważ nie poruszamy się tu po cyklu, który opisałem w punkcie 1, zdaje się, że wobec tego nie musimy stosować się do zasady, aby używać tylko pierwiastka okresu generatora (ze względu na paradoks urodziny, patrz punkt 3.1): Jeżeli generator ma jeden cykl, w którym przebiega po wszystkim liczbach bez powtórzeń po kolei, to odbiega to od procedury generowania prawdziwie losowych liczb, gdzie mamy pewną szansę, że liczba powtórzy się i to szybciej, niż wynosi długość cyklu generatora. Ze względu na paradoks urodzinowy można się spodziewać, że takie powtórzenia wystąpią całkiem szybko, stąd zaleca się używać tylko pierwiastka okresu generatora, zwłaszcza do symulacji, Monte Carlo, etc. Ale wygląda na to, że generator taki jak Widynskiego nie powinien mieć takiego problemu, tam mogą zdarzać się powtórzenia i możemy używać jego całego okresu, gwarantowanego przez Weyl sequence.

Dodano po 35 minutach 22 sekundach:
Ostatni kod miał wyglądać tak: