Dam temu szansę, ponieważ wystarczająco niepokoi mnie rada zawarta w niektórych innych odpowiedziach.
Niech będą nieskończonymi sekwencjami bitowymi generowanymi przez dwa RNG (niekoniecznie PRNG, które są deterministyczne po poznaniu stanu początkowego), i rozważamy możliwość użycia sekwencji z nadzieją na poprawę zachowania w pewnym sensie. Istnieje wiele różnych sposobów, w których można uznać za lepsze lub gorsze w porównaniu do każdego z i ; oto garstka, które moim zdaniem są znaczące, użyteczne i zgodne z normalnym użyciem słów „lepiej” i „gorzej”:X⃗ ,Y⃗ X⃗ ⊕Y⃗ X⃗ ⊕Y⃗ X⃗ Y⃗
- (0) Prawdopodobieństwo prawdziwej losowości sekwencji wzrasta lub maleje
- (1) Prawdopodobieństwo zwiększenia lub zmniejszenia obserwowalnego braku losowości (prawdopodobnie w odniesieniu do niektórych obserwatorów stosujących pewną określoną kontrolę)
- (2) Nasilenie / oczywistość obserwowalnej nieprzypadkowości wzrasta lub maleje.
Najpierw zastanówmy się nad (0), który jest jedynym z trzech, który ma nadzieję, że zostanie sprecyzowany. Zauważ, że jeśli w rzeczywistości jeden z dwóch wejściowych RNG jest naprawdę losowy, bezstronny i niezależny od drugiego, wynik XOR będzie również naprawdę losowy i bezstronny. Mając to na uwadze, rozważ przypadek, w którym uważasz, że jest naprawdę przypadkowym, bezstronnym, izolowanym strumieniem bitów, ale nie jesteś całkowicie pewien. Jeśli są odpowiednimi prawdopodobieństwami, że mylisz się co do każdego z nich, wówczas prawdopodobieństwo, że nie jest tak naprawdę losowy, to
, w rzeczywistości znacznie mniej odX⃗ ,Y⃗ εX,εYX⃗ ⊕Y⃗ ≤εXεY<min{εX,εY}εX,εY przyjmuje się, że są bardzo bliskie zeru („uważasz, że są naprawdę przypadkowe”). I w rzeczywistości jest nawet lepsze, gdy weźmiemy również pod uwagę możliwość, że będzie naprawdę niezależny, nawet jeśli żadne z nich nie jest naprawdę losowe:
Dlatego możemy stwierdzić, że w sensie (0) XOR nie może zaszkodzić i może potencjalnie bardzo pomóc.X⃗ ,Y⃗
Pr(X⃗ ⊕Y⃗ not truly random)≤min{Pr(X⃗ not truly random),Pr(Y⃗ not truly random),Pr(X⃗ ,Y⃗ dependent)}.
Jednak (0) nie jest interesujące dla PRNG, ponieważ w przypadku PRNG żadna z omawianych sekwencji nie ma szans na bycie naprawdę losową.
Dlatego w przypadku tego pytania, które w rzeczywistości dotyczy PRNG, musimy mówić o czymś takim jak (1) lub (2). Ponieważ są to właściwości i ilości, takie jak „obserwowalne”, „surowe”, „oczywiste”, „pozorne”, mówimy teraz o złożoności Kołmogorowa i nie zamierzam tego wyjaśniać. Ale posunę się tak daleko, aby uczynić, miejmy nadzieję, kontrowersyjną tezę, że według takiego środka „01100110 ...” (okres = 4) jest gorszy niż „01010101 ...” (okres = 2), który jest gorszy niż „ 00000000 ... ”(stała).
Teraz można się domyślać, że (1) i (2) będą podążać tą samą tendencją co (0), i dlatego wniosek „XOR nie może zranić” nadal może się utrzymywać. Zwróć jednak uwagę na znaczącą możliwość, że ani ani było zauważalnie nieprzypadkowe, ale że korelacje między nimi powodują, że jest zauważalnie nieprzypadkowy. Najcięższym przypadkiem tego jest oczywiście sytuacja, gdy (lub ), w którym to przypadku jest stały, najgorszy ze wszystkich możliwych wyników; ogólnie łatwo zauważyć, że niezależnie od tego, jak dobre są i ,X⃗ Y⃗ X⃗ ⊕Y⃗ X⃗ =Y⃗ X⃗ =not(Y⃗ )X⃗ ⊕Y⃗ X⃗ Y⃗ X⃗ i muszą być „bliskie” niezależności, aby ich xor nie był zauważalnie nielosowy. W rzeczywistości brak zależności, którą można zaobserwować, można rozsądnie zdefiniować jako która nie jest zauważalnie nieprzypadkowa.Y⃗ X⃗ ⊕Y⃗
Taka zależność od niespodzianek okazuje się naprawdę dużym problemem.
Przykład tego, co idzie nie tak
Pytanie brzmi: „Wykluczam wspólny przykład kilku rejestrów przesuwnych z liniowym sprzężeniem zwrotnym pracujących razem, ponieważ pochodzą one z tej samej rodziny”. Ale na razie wykluczę to wyłączenie, aby dać bardzo prosty, jasny przykład z życia rzeczy, które mogą się nie udać w XORing.
Moim przykładem będzie stara implementacja rand (), która była w jakiejś wersji Uniksa około 1983 roku. IIRC, ta implementacja funkcji rand () miała następujące właściwości:
- wartość każdego wywołania funkcji rand () wynosiła 15 pseudolosowych bitów, to jest liczb całkowitych z zakresu [0, 32767).
- kolejne zwracane wartości na przemian parzyste-nieparzyste-parzyste-nieparzyste; to znaczy najmniej zmienny bit na przemian 0-1-0-1 ...
- bit najmniej znaczący miał okres 4, następny miał okres 8, ... więc bit najwyższego rzędu miał okres .215
- dlatego sekwencja 15-bitowych wartości zwracanych przez rand () była okresowa z okresem .215
Nie udało mi się znaleźć oryginalnego kodu źródłowego, ale zgaduję, że poskładałem kilka postów z https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A tego zrobił dokładnie to (kod C), co zgadza się z moją pamięcią powyższych właściwości:
#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
next = next * 1103515245 + 12345;
return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
next = seed;
}
Jak można sobie wyobrazić, próba użycia tego rand () na różne sposoby doprowadziła do szeregu rozczarowań.
Na przykład w pewnym momencie próbowałem symulować sekwencję losowych rzutów monetą, wielokrotnie wykonując:
rand() & 1
czyli najmniej znaczący bit. Wynik był prosty naprzemiennie głowice-ogony-głowice-ogony. Na początku trudno było w to uwierzyć (to musi być błąd w moim programie!), Ale po tym, jak przekonałem się, że to prawda, spróbowałem użyć następnego najmniej znaczącego bitu. Nie jest to o wiele lepsze, jak zauważono wcześniej - ten bit jest okresowy z okresem 4. Dalsze badanie kolejnych wyższych bitów ujawniło wzór, który zauważyłem wcześniej: to znaczy, że każdy następny bit wyższego rzędu miał dwa razy większy okres niż poprzedni, więc w pod tym względem bit najwyższego rzędu był najbardziej przydatny ze wszystkich. Zauważ jednak, że nie było czarno-białego progu „bit jest przydatny, bit nie jest użyteczny” tutaj; wszystko, co możemy naprawdę powiedzieć, to to, że numerowane pozycje bitów miały różny stopień przydatności / bezużyteczności.ii−1
Próbowałem także dalej mieszać wyniki lub XORing razem wartości zwracane z wielu wywołań funkcji rand (). XORing par kolejnych wartości rand () był oczywiście katastrofą - spowodował wszystkie nieparzyste liczby! Dla moich celów (mianowicie wytwarzanie „pozornie losowej” sekwencji rzutów monetą) wynik XOR o stałej parzystości był nawet gorszy niż naprzemienne zachowanie parzyste i nieparzyste oryginału.
Niewielka odmiana umieszcza to w oryginalnym frameworku: niech będzie sekwencją 15-bitowych wartości zwróconych przez rand () z danym ziarnem , a sekwencją z innego ziarna . Ponownie, będzie sekwencją liczb parzystych lub nieparzystych, co jest gorsze niż pierwotne zachowanie na przemian parzystych / nieparzystych.X⃗ sXY⃗ sYX⃗ ⊕Y⃗
Innymi słowy, jest to przykład, w którym XOR pogorszył sytuację w sensie (1) i (2), przy jakiejkolwiek rozsądnej interpretacji. Gorzej jest również na kilka innych sposobów:
- (3) Bit najmniej znaczący XOR jest oczywiście stronniczy, tj. Ma nierówne częstotliwości zer i jedynek, w przeciwieństwie do jakiejkolwiek numerowanej pozycji bitu na którymkolwiek z wejść, które są całkowicie niezależne.
- (4) W rzeczywistości dla każdej pozycji bitu istnieją pary nasion, dla których ta pozycja bitu jest tendencyjna w wyniku XOR, a dla każdej pary nasion istnieją (co najmniej 5) pozycje bitu, które są tendencyjne w XOR wynik.
- (5) Okres całej sekwencji 15-bitowych wartości w wyniku XOR wynosi 1 lub , w porównaniu do dla oryginałów.214215
Żaden z (3), (4), (5) nie jest oczywisty, ale wszystkie można łatwo zweryfikować.
Na koniec zastanówmy się nad ponownym wprowadzeniem zakazu PRNG z tej samej rodziny. Problem w tym, jak sądzę, polega na tym, że nigdy tak naprawdę nie jest jasne, czy dwa PRNG są „z tej samej rodziny”, dopóki / chyba że ktoś zacznie używać XOR i zauważy (lub atakujący zauważy), że sytuacja pogorszyła się w sensie (1) i (2), tzn. dopóki nieprzypadkowe wzorce na wyjściu nie przekroczą progu od niezauważonego do zauważonego / zawstydzającego / katastrofalnego, i wtedy jest już za późno.
Jestem zaniepokojony innymi odpowiedziami, które udzielają niekwalifikowanej porady, że „XOR nie może zaszkodzić” na podstawie teoretycznych miar, które wydają się źle wykonywać modelowanie tego, co większość ludzi uważa za „dobre” i „złe” na temat PRNG w prawdziwym życiu. Ta rada jest sprzeczna z wyraźnymi i rażącymi przykładami, w których XOR pogarsza sytuację, takimi jak przykład rand () podany powyżej. Chociaż można sobie wyobrazić, że stosunkowo „silne” PRNG mogłyby konsekwentnie wykazywać odwrotne zachowanie, gdy XORed do zabawkowego PRNG, który był rand (), dzięki czemu XOR był dla nich dobrym pomysłem, nie widziałem żadnych dowodów w tym kierunku, teoretycznych lub empiryczny, więc nie wydaje mi się rozsądne zakładanie, że tak się dzieje.
Osobiście, będąc ugryzionym z zaskoczenia przez XORing rand () w mojej młodości i niezliczonymi innymi powiązaniami z niespodziankami przez całe moje życie, nie mam powodu, aby sądzić, że wynik będzie inny, jeśli spróbuję ponownie podobnej taktyki. Właśnie dlatego osobiście byłbym bardzo niechętny wobec XOR razem wielu PRNG, chyba że przeprowadzono bardzo obszerną analizę i weryfikację, aby dać mi pewność, że może to być bezpieczne dla poszczególnych RNG, o których mowa. Jako potencjalne lekarstwo na to, kiedy mam niskie zaufanie do jednego lub więcej indywidualnych PRNG, XOR nie jest w stanie zwiększyć mojej pewności, więc raczej nie użyję go do takiego celu. Wyobrażam sobie, że odpowiedź na twoje pytanie jest taka, że jest to powszechne przekonanie.