Najlepszy sposób na wysianie N niezależnych generatorów liczb losowych od 1 wartości

10

W moim programie muszę uruchomić N osobnych wątków, każdy z własnym RNG, który służy do próbkowania dużego zestawu danych. Muszę być w stanie zaszczepić cały ten proces jedną wartością, aby móc odtwarzać wyniki.

Czy wystarczy po prostu sekwencyjnie zwiększać ziarno dla każdego indeksu?

Obecnie używam numpytych, RandomStatektóre korzystają z generatora liczb pseudolosowych Mersenne Twister.

Fragment kodu poniżej:

# If a random number generator seed exists
if self.random_generator_seed:
    # Create a new random number generator for this instance based on its
    # own index
    self.random_generator_seed += instance_index
    self.random_number_generator = RandomState(self.random_generator_seed)

Zasadniczo zaczynam od zarodka wprowadzonego przez użytkownika (jeśli istnieje) i dla każdej instancji / wątku kolejno dodaję indeks (od 0 do N-1) uruchomionej instancji. Nie wiem, czy to dobra praktyka, czy może jest na to lepszy sposób.

EricR
źródło
1
Czy wiesz z góry, ile pseudolosowych wartości użyje każdy wątek - a przynajmniej czy możesz uzyskać dobre oszacowanie górnej granicy?
whuber
Nie, nie mogę. Próbkuje regiony, które są sumowane aż do osiągnięcia progu. Rozmiary regionów mogą się znacznie różnić.
EricR

Odpowiedzi:

9

Z pewnością nie jest to świetna praktyka. Na przykład zastanów się, co się stanie, gdy wykonasz dwa przebiegi z nasionami root 12345 i 12346. Każdy bieg będzie miał N-1wspólne strumienie.

Implementacje Mersenne Twister (w tym numpy.randomi random) zwykle używają innego PRNG do rozszerzenia zarodka liczb całkowitych do dużego wektora stanu (624 32-bitowe liczby całkowite), którego używa MT; to jest tablica z RandomState.get_state(). Dobrym sposobem na zrobienie tego, co chcesz, jest uruchomienie tego PRNG, zaszczepionego jednorazową liczbą całkowitą, i uzyskanie z niego N*62432-bitowych liczb całkowitych. Podziel strumień na Nwektory stanu i użyj, RandomState.set_state()aby jawnie zainicjować każdą RandomStateinstancję. Być może trzeba będzie konsultować źródła C o numpy.randomlub _randomz biblioteki standardowej, aby ta PRNG (są takie same). Nie jestem pewien, czy ktoś zaimplementował samodzielną wersję tego PRNG dla Pythona.

Robert Kern
źródło
Myślę, że to może być najlepsze rozwiązanie, jakie do tej pory słyszałem. Nie wydaje mi się, żeby miało to znaczenie, jak podzielę strumień, choć poprawne? Wydaje się znacznie mniej prawdopodobne, aby sekwencja na 624 32-bitowych liczbach całkowitych między instancjami była zduplikowana, bez względu na to, jak są one wybierane z początkowego PRNG i materiału źródłowego.
EricR
1
Właściwie to trochę cofnę. Nie jest dla mnie jasne, że inicjalizator PRNG jest zaprojektowany tak, aby czerpać z niego dowolnie wiele wartości. Rozważ użycie innej jakości PRNG (najlepiej niezwiązanej z MT) do wygenerowania strumienia stanu. Można zaimplementować HMAC-DRBG (PRNG wykorzystujący HMAC jako prymityw kryptograficzny) przy użyciu tylko standardowej biblioteki stosunkowo prosto. Bezpieczeństwo kryptograficzne nie stanowi problemu; po prostu łatwość implementacji i jakość strumienia bitów. Będziesz musiał upewnić się, że żadne bardzo zerowe wektory nie zostaną stworzone, z bardzo rzadką szansą.
Robert Kern,
Lub po prostu użyj jednej z nowszych RandomStateimplementacji w rozwoju, która wykorzystuje algorytm z ustawialnymi strumieniami. Innymi słowy, inicjujesz każdą RandomStateinstancję przy użyciu tego samego materiału źródłowego i różnych identyfikatorów strumienia (tylko zwiększenie jest w porządku) i masz zagwarantowane niezależne strumienie. pypi.python.org/pypi/randomstate
Robert Kern
4

Rozwiązaniem stosowanym w przetwarzaniu równoległym jest użycie generatora losowegoΦ(u), gdzie u jest twoim nasieniem, przez N.partie:

  1. Generować Φ(u),ΦN.(u),Φ2)N.(u),...
  2. Generować Φ2)(u),Φ1+N.(u),Φ1+2)N.(u),...
  3. ...
  4. Generować ΦN.-1(u),ΦN.-1+N.(u),ΦN.-1+2)N.(u),...

gdzie Φn(u)=Φ(Φn-1(u)). W ten sposób używasz pojedynczego ziarna, a wszystkie sekwencje są jednolite i niezależne.

Xi'an
źródło
2

Istnieje teraz pakiet Python o nazwie RandomGen, który ma metody pozwalające to osiągnąć.

To wspiera niezależnych strumieni utworzonych z jednego materiału siewnego, a także protokołu narciarskie dla starszych generatorów liczb losowych, takich jak MT19937.

Praveen
źródło
0

Niektóre osoby twierdzą, że istnieją korelacje w liczbach losowych generowanych przez sekwencyjne nasiona. /programming/10900852/near-seeds-in-random-number-generation-may-give-similar-random-numbers Nie jestem pewien, czy to prawda.

Jeśli się tym martwisz, dlaczego nie użyć jednego generatora liczb losowych, aby wybrać nasiona dla wszystkich innych generatorów?

Aaron
źródło
Po prostu dlatego, że nie chcę mieć szansy na losowe wygenerowanie tego samego ziarna dla więcej niż 1 generatora. Oczywiście mógłbym trochę popracować nad programowaniem, aby temu zapobiec, ale nie wiem, jak to byłoby lepsze niż zbieranie nasion sekwencyjnie.
EricR
1
Najwyraźniej możliwe są korelacje z sekwencyjnymi ziarnami ... Jednak, jak pokazuje artykuł, do którego link znajduje się w odpowiedzi na blogu Johna D Cooka, użycie jednego RNG do wygenerowania nasion dla innych generatorów jest znacznie gorsze, ponieważ napotykasz problem urodzinowy! Mówi, że losowe wygenerowanie 1000 16-bitowych nasion bez znaku ma 99,95% szansy na nakładanie się!
Praveen