Test losowości

Nie mylić z testem z randomizacją .

Test losowości (lub test losowości ) w ocenie danych to test używany do analizy rozkładu zbioru danych w celu sprawdzenia, czy można go określić jako losowy (bez wzorca). W modelowaniu stochastycznym , podobnie jak w niektórych symulacjach komputerowych , oczekiwaną losowość potencjalnych danych wejściowych można zweryfikować za pomocą formalnego testu losowości, aby wykazać, że dane nadają się do wykorzystania w przebiegach symulacji. W niektórych przypadkach dane ujawniają oczywisty nielosowy wzorzec, jak w przypadku tak zwanych „przebiegów w danych” (takich jak oczekiwanie losowego 0–9, ale znalezienie „4 3 2 1 0 4 3 2 1…” i rzadko powyżej 4). Jeśli wybrany zestaw danych nie przejdzie testów, można zmienić parametry lub użyć innych losowych danych, które przejdą testy losowości.

Tło

Kwestia losowości jest ważnym zagadnieniem filozoficznym i teoretycznym. Testy losowości można wykorzystać do określenia, czy zbiór danych ma rozpoznawalny wzorzec, który wskazywałby, że proces, który go wygenerował, jest znacząco nielosowy. W przeważającej części analiza statystyczna w praktyce bardziej dotyczyła znajdowania regularności w danych niż testowania losowości. Wiele używanych obecnie „generatorów liczb losowych” jest zdefiniowanych przez algorytmy, a więc w rzeczywistości są one pseudolosowe generatory liczb. Sekwencje, które wytwarzają, nazywane są sekwencjami pseudolosowymi. Te generatory nie zawsze generują sekwencje, które są wystarczająco losowe, ale zamiast tego mogą generować sekwencje zawierające wzorce. Na przykład niesławna RANDU dramatycznie zawodzi w wielu testach losowości, w tym w teście widmowym.

Stephen Wolfram wykorzystał testy losowości na wyjściu Reguły 30 , aby zbadać jej potencjał do generowania liczb losowych, chociaż wykazano, że ma ona efektywny rozmiar klucza znacznie mniejszy niż jego rzeczywisty rozmiar i słabo radzi sobie w teście chi-kwadrat . Użycie nieprzemyślanego generatora liczb losowych może podważyć ważność eksperymentu, naruszając założenia statystyczne. Chociaż istnieją powszechnie stosowane techniki testów statystycznych, takie jak standardy NIST, Yongge Wang wykazał, że standardy NIST nie są wystarczające. Ponadto Yongge Wang zaprojektował techniki testowania oparte na statystyce odległości i prawie iterowanego logarytmu. Używając tej techniki, Yongge Wang i Tony Nicol wykryli słabość powszechnie używanych generatorów pseudolosowych, takich jak dobrze znany Debianowa wersja generatora pseudolosowości OpenSSL , która została naprawiona w 2008 roku.

Specyficzne testy losowości

W praktyce stosowano dość niewielką liczbę różnych typów generatorów (pseudo) liczb losowych. Można je znaleźć na liście generatorów liczb losowych i obejmowały:

Te różne generatory mają różne stopnie sukcesu w przejściu akceptowanych zestawów testów. Kilka powszechnie używanych generatorów nie przeszło testów mniej lub bardziej źle, podczas gdy inne „lepsze” i wcześniejsze generatory (w tym sensie, że przeszły wszystkie obecne baterie testów i już istniały) zostały w dużej mierze zignorowane.

Istnieje wiele praktycznych miar losowości sekwencji binarnej . Obejmują one miary oparte na testach statystycznych , transformacjach i złożoności lub ich kombinacji. Dobrze znanym i szeroko stosowanym zbiorem testów była Diehard Battery of Tests , wprowadzona przez firmę Marsaglia; zostało to rozszerzone na TestU01 przez L'Ecuyer i Simard. Zastosowanie transformaty Hadamarda do pomiaru losowości zaproponował S. Kak i rozwinięty dalej przez Phillipsa, Yuena, Hopkinsa, Beth i Dai, Munda oraz Marsaglię i Zamana.

Kilka z tych testów, które mają złożoność liniową, zapewnia widmowe miary losowości. T. Beth i ZD. Dai rzekomo wykazał, że złożoność Kołmogorowa i złożoność liniowa są praktycznie takie same, chociaż Y. Wang później wykazał, że ich twierdzenia są błędne. Niemniej jednak Wang wykazał również, że w przypadku losowych sekwencji Martina-Löfa złożoność Kołmogorowa jest zasadniczo taka sama jak złożoność liniowa.

Te praktyczne testy umożliwiają porównanie losowości ciągów znaków . Ze względów probabilistycznych wszystkie ciągi o danej długości mają taką samą losowość. Jednak różne struny mają różną złożoność Kołmogorowa. Rozważmy na przykład następujące dwa ciągi.

Ciąg 1: 0101010101010101010101010101010101010101010101010101010101010101
Ciąg 2: 1100100001100001110111110111011001111101001000010 0101011110010110

Ciąg 1 dopuszcza krótki opis językowy: „32 powtórzenia„ 01 ””. Ten opis ma 22 znaki i można go wydajnie zbudować z kilku podstawowych sekwencji. [ potrzebne wyjaśnienie ] Łańcuch 2 nie ma oczywistego prostego opisu innego niż zapisanie samego ciągu, który ma 64 znaki, [ potrzebne wyjaśnienie ] i nie ma porównywalnie wydajnej reprezentacji funkcji bazowej . Używając liniowych testów spektralnych Hadamarda (patrz Transformacja Hadamarda ), okaże się, że pierwsza z tych sekwencji jest znacznie mniej przypadkowa niż druga, co jest zgodne z intuicją.

Godne uwagi implementacje oprogramowania

Zobacz też

Notatki

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Randomness_test&oldid=1138278565 ”