Obliczanie nielosowości wyspecjalizowanego generatora losowego?

Question

Właśnie przeczytałem this interesting question o generatorze liczb losowych, który nigdy nie generuje tej samej wartości trzy razy z rzędu. To wyraźnie sprawia, że ​​generator liczb losowych różni się od standardowego generatora liczb losowych, ale nie jestem pewien, jak ilościowo opisać, jak ten generator różni się od generatora, który nie ma tej właściwości.

Załóżmy, że przekazałeś mi dwa generatory liczb losowych, R i S, gdzie R jest generatorem liczb losowych, a S jest generatorem liczb losowych, który został zmodyfikowany tak, aby nigdy nie wytwarzał tej samej wartości trzy razy z rzędu. Gdybyś mi nie powiedział, który z nich jest R lub S, jedyny sposób, w jaki mogę to wykryć, to uruchomić generatory, dopóki jeden z nich nie wyprodukuje tej samej wartości trzy razy z rzędu.

Moje pytanie brzmi - czy istnieje lepszy algorytm do odróżniania dwóch generatorów? Czy ograniczenie nieuzyskania tej samej liczby trzykrotnie w jakiś sposób wpływa na obserwowalne zachowanie generatora w sposób inny niż zapobieganie pojawianiu się w rzędzie trzech takich samych wartości?

Answer 1

W konsekwencji Rice's Theorem istnieje żaden sposób powiedzieć, który jest który.

Dowód: Niech L będzie wyjściem normalnego RNG. Niech L będzie L, ale z usuniętymi wszystkimi ciągami o długości> = 3. Niektóre bazy TM rozpoznają L ', ale niektóre nie. Dlatego według twierdzenia Rice'a określenie, czy TM akceptuje L ', nie jest rozstrzygalne.

Jak zauważyli inni, może być w stanie dokonać stwierdzenie jak „to prowadzi do stepów N bez powtarzania trzy razy”, ale nigdy nie można zrobić skok do „Będzie nigdy powtarzać cyfra trzy razy ."Bardziej odpowiednio, istnieje co najmniej jedna maszyna, dla której nie można ustalić, czy spełnia ona to kryterium, czy nie,

Zastrzeżenie: jeśli miałbyś naprawdę losowy generator (np. Rozpad jądra), możliwe jest, że twierdzenie Rice'a nie stosuje Moja intuicja jest twierdzenie, że nadal trzyma na tych maszynach, ale nigdy nie słyszałem, że omawiane

EDIT... dowód wtórnej Załóżmy P(X) określa z dużym prawdopodobieństwem, czy X akceptuje L'. Możemy skonstruować (nieskończoną liczbę) programów F takich jak:

F(x): if x(F), then don't accept L' 
     else, accept L' 

P nie może określić zachowania się F(P). Co więcej, powiedzmy, że P poprawnie przewiduje zachowanie G. Możemy zbudować:

F'(x): if x(F'), then don't accept L' 
     else, run G(x) 

Tak więc dla każdego dobrego przypadku musi istnieć przynajmniej jeden zły przypadek.

Answer 2

Ponieważ zdefiniowałeś, że różnią się one tylko w odniesieniu do tej konkretnej właściwości, nie ma lepszego algorytmu do rozróżnienia tych dwóch.

Jeśli wykonasz potrojenie wartości randum, generator S będzie produkował wszystkie inne trójki nieco częściej niż R, aby zrekompensować brakujące trzyki (X,X,X). Ale aby uzyskać znaczący wynik, potrzebujesz więcej danych, niż za trzykrotne za pierwszym razem znalezienie wartości.

Answer 3

Jeśli S określa się oddalając od R, to sekwencja wytwarzać S będzie podciągiem ciągu wytwarzanego przez R. Na przykład, biorąc prostą zmienną losową X z jednakowym prawdopodobieństwem bycia 1 lub 0, to masz:

R = 0 1 1 0 0 0 1 0 1 
S = 0 1 1 0 0 1 0 1 

Jedynym sposobem na rozróżnienie tych dwóch jest patrzeć na smugi. Jeśli generujesz liczby binarne, to smugi są niezwykle powszechne (tak bardzo, że prawie zawsze można rozróżnić sekwencję losową na 100 cyfr od sekwencji, którą uczeń zapisuje próbując być losową). Jeśli liczby są pobierane od [0,1] równomiernie, to smugi są znacznie mniej powszechne.

Jest to łatwe ćwiczenie z prawdopodobieństwem, aby obliczyć szansę równości trzech kolejnych liczb, gdy znasz rozkład, lub nawet lepiej, oczekiwaną liczbę liczb potrzebną do tego, aby prawdopodobieństwo trzech kolejnych równych liczb było większe niż p ulubiony wybór p.

Answer 4

prawdopodobnie używać ENT (http://fourmilab.ch/random/)