Jak udowodnić, że generator liczb losowych jest lepszy od drugiego?

Question

Jak udowodnisz, że jeden RNG jest lepszy od innego?

Nie mam na myśli czasu działania, ale raczej ilości entropii "wygenerowanej" - która również rzuca pojęcie periodyczności (niski okres = niska entropia).

Czy można udowodnić, że RNG jest optymalny? Czy jest to nieosiągalny cel? Optymalnie, każda sekwencja jest równie prawdopodobna i niezależna od przeszłych lub przyszłych wyników.

Jestem zainteresowany algorytmów, nie kosmiczne urządzenia do pobierania próbek tła lub innych źródeł fizycznego „przypadkowości” (jest to losowe lub po prostu skomplikowane?)

Answer 1

Stary Standard Badań używany być "testami Diehard". http://en.wikipedia.org/wiki/Diehard_tests Zostało to zastąpione przez testy NIST wskazane przez DKnight: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html. Artykuł wiki Dieharda daje dobry przegląd tego, na co patrzysz. Bit NIST będzie wymagał nieco więcej kopania.

Jak można stwierdzić, nie można potwierdzić optymalnego pseudo RNG (algorytmu). Wszystkie mają wartość początkową i zależą od danych wejściowych w celu wygenerowania wartości. Jeśli znasz ziarno i stan, znasz następną wartość. Na przykład sprawdź http://en.wikipedia.org/wiki/Mersenne_twister. Najbardziej podoba mi się to z powodu niesamowitej nazwy, ale artykuł dobrze sprawdza się w wyjaśnieniach zasad PRNG.

Answer 2

Zobacz http://www.random.org/analysis/

jeden i tylko optymalną RNG:

Answer 3

Generowanie sekwencji liczb, a następnie spróbuj je skompresować. Im bardziej losowe, tym mniej będzie kompresji. Czysta losowość jest nieściśliwa. Byłoby interesujące zobaczyć wyniki i jeśli będą różnice.

Answer 4

Narodowy Instytut Standardów i Technologii ma jakieś dobre informacje na ten temat:

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Wygląda na to, że jest to zestaw testów i dużo dobrego materiału referencyjnego

Answer 5

Istnieje obiektywna definicja z teorii złożoności obliczeniowej: asymptotyczna złożoność czasu wymagana do odróżnienia danych wyjściowych od danych losowych.

Dobry PRNG powinien zmusić sprzedawcę do poświęcenia znacznie więcej czasu w miarę wzrostu wielkości materiału siewnego lub w miarę wzrostu wymaganego poziomu pewności. (Z nasion stałym rozmiarze Przypuszczam, że jeśli spojrzeć na rzeczywisty czas pracy, jak i złożoności programu.)

• Dla porównania jeden PRNG przeciw drugiemu, jeden z mniejszych/szybszego Wyróżnikiem jest gorzej.
• Jednym z powszechnych założeń, chociaż nie zostało to udowodnione, jest to, że niektóre PRNG są nieodróżnialne od losowych w czasie wielomianowym. To jedno możliwe znaczenie dla "optymalnego".
• Testy statystyczne, takie jak diehard tests, to tylko proste wyróżniki.

Answer 6

Podstawy są w Knuth, The Art of Computer Programming Vol 2, "Algorytmy seminumeryczne".Chodzi o to, aby opracować testy przypadkowości, w których każdy test będzie próbował znaleźć nielosowe aspekty PRNG. Zauważ, że to, co może wydawać się przypadkowe dla istoty ludzkiej, nie jest. Na przykład, mamy tendencję do stwierdzenia, że ​​sekwencja "1,4,4,1" na przykład jest nie-losowa, podczas gdy może występować idealnie w większej losowej sekwencji.

więc podejście jest grubsza:

• znaleźć różne testy dla losowości, to zasadniczo zagorzałych i NIST grup testowych.
• Wykonaj wymienione testy na PRNG.
• Jeśli PRNG nie przejdzie jednego lub więcej testów, może być postrzegany jako słabszy PRNG niż te, które przeżyją.

Fajnym przykładem testu jest analiza fazy i przestrzeni. Tu jest link o to stracony kilka lat wstecz na generatorach TCP losowości dla różnych systemów operacyjnych:

http://lcamtuf.coredump.cx/oldtcp/tcpseq.html

Inne testy są klasyczne chi-kwadraty, Komolgorov-Smirnoff etc, wszystko wyjaśnione w Knuth. Dobre PRNG przetrwają każdy możliwy atak na nich.