Testowanie algorytmów generowania losowych zmiennych

Jakie metody są używane do testowania algorytmów generowania zmiennych losowych?

Diehard testowy Suite jest czymś blisko Złotego Standardu Badań losowe generatory liczb. Obejmuje szereg testów, w których dobry generator liczb losowych powinien dawać wyniki rozdzielone zgodnie z niektórymi znanymi rozkładami, z którymi następnie można porównać wynik za pomocą testowanego generatora.

EDYTOWAĆ

Muszę to zaktualizować, ponieważ nie miałem racji: Diehard może nadal być często używany, ale nie jest już utrzymywany i nie jest już najnowocześniejszy. Od tego czasu NIST opracował zestaw ulepszonych testów .

Aby dodać trochę do odpowiedzi honka , Diehard Test Suite (opracowany przez George'a Marsaglia) to standardowe testy dla PRNG.

Jest ładna biblioteka Diehard C, która daje dostęp do tych testów. Oprócz standardowych testów Dieharda zapewnia także funkcje dla kilku innych testów PRNG obejmujących (między innymi) sprawdzanie kolejności bitów. Istnieje również ułatwienie do testowania prędkości RNG i pisania własnych testów.

Istnieje interfejs R do biblioteki Dieharder, o nazwie RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

To pokazuje, że generator RANDU RNG nie przejdzie testu minimalnej odległości / 2 sfery.

Do testowania liczb generowanych przez generatory liczb losowych praktyczne są testy Dieharda . Ale testy te wydają się być arbitralne i można się zastanawiać, czy należy uwzględnić więcej, czy jest jakiś sposób, aby naprawdę sprawdzić losowość.

Najlepszym kandydatem do zdefiniowania losowej sekwencji wydaje się losowość Martina-Löfa . Główną ideą tego rodzaju losowości, pięknie opracowaną w Knuth, sekcja 3.5 , jest sprawdzenie jednolitości dla wszystkich typów podsekwencji sekwencji liczb losowych. Pierwsze, że wszystkie rodzaje podciągów definicji prawo okazało się być bardzo trudne, nawet jeśli ktoś używa pojęcia obliczalności.

Testy Dieharda to tylko niektóre z możliwych podsekwencji, które można rozważyć, a ich niepowodzenie wykluczałoby losowość Martina-Löfa.

Nie możesz udowodnić, ponieważ jest to niemożliwe; możesz tylko sprawdzić, czy nie występują zawstydzające autokorelacje lub zakłócenia dystrybucji, a Diehard jest w tym przypadku standardem. Dotyczy to statystyki / fizyki, kryptografowie sprawdzą także (między innymi), jak trudno jest dopasować generator do danych, aby uzyskać przyszłe wartości.

Mała poprawka do postu Colina: pakiet CRAN RDieHarder jest interfejsem do DieHarder , przerobu / rozszerzenia / przeglądu Dieharda dokonanego przez Roberta G. Browna (który uprzejmie wymienia mnie jako współautora opartego na moich opakowaniach RDieHarder) z ostatnim wkładem Davida Bauera.

DieHarder zawiera między innymi baterię testów NIST wymienionych w poście Marka, a także kilka nowych. To trwają badania i już od jakiegoś czasu. Wygłosiłem wykład w useR! 2007 o RDieHarder, który można uzyskać stąd .

Rzadko przydatne jest stwierdzenie, że w abstrakcie coś jest „losowe”. Częściej chcesz przetestować, czy ma on pewien rodzaj losowej struktury. Na przykład możesz chcieć sprawdzić, czy coś ma równomierny rozkład, przy czym wszystkie wartości w pewnym zakresie są jednakowo prawdopodobne. Możesz też sprawdzić, czy coś ma rozkład normalny itp. Aby sprawdzić, czy dane mają określony rozkład, możesz użyć testu dobroci dopasowania, takiego jak test chi-kwadrat lub test Kołmogorowa-Smirnowa.

Testowanie generatora liczb losowych składa się z dwóch części. Jeśli zajmujesz się tylko testowaniem jednolitego generatora, to tak, dobrym pomysłem jest coś takiego jak zestaw testowy DIEHARD.

Ale często trzeba przetestować transformację jednolitego generatora. Na przykład możesz użyć jednolitego generatora do tworzenia wykładniczych lub normalnie rozłożonych wartości. Możesz mieć wysokiej jakości jednolity generator - powiedzmy, że masz zaufaną implementację znanego algorytmu, takiego jak Mersenne Twister - ale musisz sprawdzić, czy transformowane wyjście ma odpowiedni rozkład. W takim przypadku musisz wykonać test dobroci dopasowania, taki jak Kołmogorow-Smirnov. Ale na początek możesz sprawdzić, czy średnia próbki i wariancja mają wartości, których oczekujesz.

Większość ludzi nie - i nie powinna - pisać od zera własnego jednolitego generatora liczb losowych. Trudno jest napisać dobry generator i łatwo oszukać się, myśląc, że napisałeś dobry, kiedy tego nie zrobiłeś. Na przykład Donald Knuth opowiada historię w 2 tomie TAOCP generatora liczb losowych, który napisał, który okazał się okropny. Ale ludzie często piszą własny kod, aby wygenerować losowe wartości z nowej dystrybucji.

NIST publikuje listę badań statystycznych z realizacji odniesienia w C.

Istnieje również TestU01 autorstwa niektórych inteligentnych ludzi, w tym szanowanego badacza PRNG, Pierre'a L'Ecuyera. Ponownie istnieje implementacja referencyjna w C.

Jak zauważyli inni komentatorzy, służą one do testowania generowania pseudolosowych bitów. Jeśli przekształcisz te bity w inną zmienną losową (np. Transformata Boxa-Mullera z jednolitej na normalną), będziesz potrzebować dodatkowych testów w celu potwierdzenia poprawności algorytmu transformacji.