Zeitliche Korrelationen bei Verwendung von System.Random (nicht vorhanden bei Verwendung von System.Random.TF)

Question

Diese Frage betrifft die Ursprünge von zeitlichen Korrelationen, die man mit System.Random beobachtet, wenn man aufeinanderfolgende Randome aus aufeinanderfolgenden Seeds erzeugt (wobei man die gleiche Anzahl von Generatoren verwirft) für jeden Samen).

In Using mkStdGen from System.Random to generate random booleans Answer 1 und Using mkStdGen from System.Random to generate random booleans Answer 2 wurde vorgeschlagen (basierend auf dem Reddit-Artikel, auf den verwiesen wird), dass die ersten Generatoren verworfen werden sollten, um vernünftige Ergebnisse zu erhalten. Ich finde jedoch, dass unabhängig davon, wie viele Generatoren man verwirft, man, wenn man den zeitlichen Aspekt der Verteilung betrachtet, unerwünschte Ergebnisse erhält, wenn aufeinanderfolgende Zufallszahlen mit aufeinanderfolgenden Samen erzeugt werden (wobei einer dieselbe Anzahl von Erzeugern für jeden Samen verwirft).

Meine Frage ist, was ist es über die in eingesetzt Algorithmus System.Random, die zwischen den verschiedenen Samen in der beschriebenen Weise in dieser zeitlichen Korrelation ergibt?

Wenn wir eine unendliche Folge von Zufall booleans erzeugen, dann ist die Wahrscheinlichkeit von P(n)n sukzessiven booleans erhalten, die mit dem gleichen Wert ist (beispielsweise die in [True,True,True][False,True,True,True,False]) ist (1/2)^n. Als schnelle Überprüfung haben wir die Normierungsbedingung:

P(1)+P(2)+....P(infty) = (1/2) + (1/2)^2 + ... = 1 

den folgenden Code:

module Main where 
import Data.List 
import System.Random 

generateNthGenerator startGen 0 = startGen 
generateNthGenerator startGen n = generateNthGenerator newGen (n-1) 
    where newGen = snd $ ((random startGen) :: (Bool,StdGen)) 

better_mkStdGen generation seed = 
    generateNthGenerator (mkStdGen seed) generation 

randomNums generation = 
    map (fst . random . (better_mkStdGen generation)) [0 .. maxBound] :: [Bool] 
-- e.g. [True,True,False,False,False,True,True,True,False,False] 

sortedLengthOfConsecutives num randList = 
    sort $ map length $ take num $ group randList 

frequencyOfConsecutives sortedLengthOfCons = 
    map (\x -> (head x, length x)) $ group sortedLengthOfCons 

results = frequencyOfConsecutives 
      $ sortedLengthOfConsecutives 10000 
       $ randomNums 10 

main = do 
    print results -- [(8,1493),(9,8507)] 

erzeugt jeder aufeinanderfolgenden boolean Generatoren aus den aufeinanderfolgenden Samen verwendet wird, verwirft 10 Generatoren bevor die resultierende Zufallsergebnis verwendet wird. Eine Folge von 10000 Zufallszahlen wird erzeugt, und so erwarten wir, dass ungefähr 5000 Booleans dem entgegengesetzten Boolean folgen (zB [True] in), denn es gibt 2500 booleans, denen derselbe Boolesche gefolgt von dem entgegengesetzten boolean folgt (zB [True,True] in [False,True,True,False]), etwa 1250 boolesche Werte, die in 3s usw. gruppieren.

Also aus dem obigen Code erhalten wir 1493 8-Gruppen und 8507 9-Gruppen. Dies ist nicht das, was erwartet wird, und wir erhalten ähnliche Ergebnisse unabhängig davon, wie viele Generatoren verworfen werden (im obigen Beispiel ist die Anzahl der für jeden Seed verworfenen Generatoren 10). [Hinweis, wenn wir das gleiche Experiment mit tf-random machen wir nicht das gleiche Verhalten, siehe später].

Wenn wir statt aufeinanderfolgende booleans erzeugen mit dem zuvor erzeugten Generator (was ich die Art und Weise erraten, in der sie ursprünglich verwendet wurde entwickelt, da random selbst gibt einen neuen Generator), scheinen wir mehr vernünftige Ergebnisse zu erhalten :

module Main where 
import Data.List 
import System.Random 

generateRandomInner gen = 
    let (randBool, newGen) = (random gen)::(Bool,StdGen) 
    in randBool:(generateRandomInner newGen) 

generateRandoms seed = 
    let (randBool, newGen) = (random $ mkStdGen seed)::(Bool,StdGen) 
    in randBool:(generateRandomInner newGen) 

seed = 0 

randomNums = generateRandoms seed 

sortedLengthOfConsecutives num randList = 
    sort $ map length $ take num $ group randList 

frequencyOfConsecutives sortedLengthOfCons = 
    map (\x -> (head x, length x)) $ group sortedLengthOfCons 

results = frequencyOfConsecutives 
      $ sortedLengthOfConsecutives 10000 
       $ randomNums 
main = do 
    print results 
    --[(1,4935),(2,2513),(3,1273),(4,663),(5,308), 
    -- (6,141),(7,86),(8,45),(9,16),(10,12),(11,6), 
    -- (12,1),(13,1)] 

So bekommen wir 4935 Singletons (entspricht etwa 0,5 * 10000), 2513 duples (entspricht etwa 0,5^2 * 10000), 1273 Tripel (entspricht in etwa 0,5^3 * 10000) usw., die, was wir erwarten von.

So scheint es, wenn wir (über System.Random) eine Zufallssequenz erzeugen, wo jedes aufeinanderfolgende Zufall mit dem nachfolgenden Keim erzeugt wird, wobei wir die gleiche Anzahl von Generatoren für jeden Keim verwerfen, eine unerwünschte Korrelation besteht unabhängig von der Anzahl der verworfenen Generatoren .

Was ist das über die algorithmischen Eigenschaften der Zufallszahlenerzeugung von System.Random, die in dieser Folge?

Beachten Sie, dass, wenn wir die fehlerhafte Methode, die oben mit tf-random (Redditt Artikel) beschäftigen dann wir die erwarteten Ergebnisse erhalten:

module Main where 
import Data.List 
import System.Random 
import System.Random.TF 

generateNthGenerator startGen 0 = startGen 
generateNthGenerator startGen n = generateNthGenerator newGen (n-1) 
    where newGen = snd $ ((random startGen) :: (Bool,TFGen)) 

better_mkStdGen generation seed = 
    generateNthGenerator (seedTFGen (0,0,0,seed)) generation 

randomNums generation = 
    map (fst . random . (better_mkStdGen generation)) [0 .. maxBound] :: [Bool] 
-- e.g. [True,True,False,False,False,True,True,True,False,False] 

sortedLengthOfConsecutives num randList = 
    sort $ map length $ take num $ group randList 

frequencyOfConsecutives sortedLengthOfCons = 
    map (\x -> (head x, length x)) $ group sortedLengthOfCons 

results = frequencyOfConsecutives 
      $ sortedLengthOfConsecutives 10000 
       $ randomNums 10 

main = do 
    print results 
    -- [(1,4867),(2,2573),(3,1243),(4,646),(5,329), 
    -- (6,176),(7,80),(8,43),(9,26),(10,10),(11,4), 
    -- (12,2),(19,1)] 

dh 50% sind Singletons, 25% sind duples (Gruppen von 2) usw. ...

Answer 1

Beginnen wir damit, dass wir uns ansehen, was der Code sagt, und wir können dorthin gelangen.

First off, random zu Bool angewendet entspricht:

randomB :: StdGen -> (Bool, StdGen) 
randomB g = let (i, g') = next g in (i `mod` 2 == 1, g') 

In der Tat, wenn ich random mit randomB ersetzen, wenn diese in Ihrem Programm angemessen ist, bekomme ich die gleichen Ergebnisse. Der Punkt ist, dass für die Bestimmung der booleschen Werte alles darauf ankommt, ob der nächste Int Wert gerade oder ungerade ist.

Als nächstes wollen wir bei der Definition von StdGen aussehen:

data StdGen 
= StdGen Int32 Int32 

So zwei Int32 s der Zustand sind. Mal sehen, wie sie mit mkStdGen initialisiert sind und wie sind sie angepasst mit next:

mkStdGen :: Int -> StdGen -- why not Integer ? 
mkStdGen s = mkStdGen32 $ fromIntegral s 

mkStdGen32 :: Int32 -> StdGen 
mkStdGen32 s 
| s < 0  = mkStdGen32 (-s) 
| otherwise = StdGen (s1+1) (s2+1) 
     where 
    (q, s1) = s `divMod` 2147483562 
    s2  = q `mod` 2147483398 

...

stdNext :: StdGen -> (Int, StdGen) 
-- Returns values in the range stdRange 
stdNext (StdGen s1 s2) = (fromIntegral z', StdGen s1'' s2'') 
    where z' = if z < 1 then z + 2147483562 else z 
     z = s1'' - s2'' 

     k = s1 `quot` 53668 
     s1' = 40014 * (s1 - k * 53668) - k * 12211 
     s1'' = if s1' < 0 then s1' + 2147483563 else s1' 

     k' = s2 `quot` 52774 
     s2' = 40692 * (s2 - k' * 52774) - k' * 3791 
     s2'' = if s2' < 0 then s2' + 2147483399 else s2' 

Hinweis zwei interessante Dinge:

1. Die Art und Weise s2 Initialisiert wird garantiert, dass es 1 wird, es sei denn, Sie senden eine sehr hohe Zahl an mkStdGen, in diesem Fall wird es 2 sein (es gibt f ewer als 200 Werte im Bereich, die Int32s2 bis 2.

2. die beiden Hälften des Zustandes initialisiert wird, wird auseinandergehalten - die aktualisierten s2 hängt nur von den vorherigen s2, nicht auf den vorherigen s1, und umgekehrt.

Als Folge, wenn Sie die Generatoren untersuchen, die Sie aus einer bestimmten festen Anzahl von Generationen zu better_mkStdGen weitergegeben zu bekommen, wird die zweite Hälfte ihres Staates immer identisch sein.

Versuchen Sie es, indem Sie diese an Ihrem Programm:

print $ map (dropWhile (/= ' ') . show . better_mkStdGen 10) [0 .. 20] 

Also dann ist die Frage, warum die Mischfunktion in s1 nicht richtig das letzte Stück zu mischen.Beachten Sie, dass die Schreibweise s1' und k die gleiche Parität wie s1 hat, so dass der s1-Status nur dann eine andere Parität aufweist als der vorherige s1-Status, wenn s1' kleiner als Null ist.

An dieser Stelle muss ich ein wenig handwave und sagen, dass die Art und Weise s1' berechnet wird, bedeutet, dass, wenn zwei Anfangswerte für s1 dicht beieinander sind, die beiden Werte für s1' auch nahe beieinander sein, und im allgemeinen Willen nur 40014-mal so weit auseinander wie sie ursprünglich waren, was in dem Bereich, den wir für s1 zulassen, benachbarte Werte ziemlich wahrscheinlich auf der gleichen Seite von Null enden lässt.