使用 System.Random 时的时间相关性（使用 System.Random.TF 时不存在）

问：

这个问题涉及人们从连续的种子生成连续随机数时观察到的时间相关性的起源（其中为每个种子丢弃相同数量的生成器）。System.Random

在使用 System.Random 的 mkStdGen 生成随机布尔值答案 1 和使用 System.Random 的 mkStdGen 生成随机布尔值答案 2 中，有人建议（基于引用他们的 reddit 文章）应该丢弃前几个生成器以获得合理的结果。然而，我发现，无论丢弃多少生成器，当人们查看分布的时间方面时，如果使用连续的种子生成连续的随机数（每个种子丢弃相同数量的生成器），就会获得不良结果。

我的问题是，所采用的算法以所描述的方式导致不同种子之间的这种时间相关性是什么？System.Random

如果我们生成一个无限序列的随机布尔值，那么获得具有相同值的连续布尔值（例如 in ）的概率为 。作为 快速检查我们有归一化条件：P(n)n[True,True,True][False,True,True,True,False](1/2)^n

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

代码如下：

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)]

使用连续种子的生成器生成每个连续的布尔值，在使用生成的随机结果之前丢弃 10 个生成器。生成一个由 10000 个随机数组成的序列，因此我们预计大约 5000 个布尔值后面跟着相反的布尔值（例如 in ），表示有 2500 个布尔值，后面跟着相同的布尔值，但后面跟着相反的布尔值（例如 in），大约有 1250 个布尔值，分为 3 个，依此类推。[True][False,True,False,False][True,True][False,True,True,False]

因此，从上面的代码中，我们得到了 1493 个 8 组和 8507 个 9 组。这不是预期的，无论丢弃了多少生成器，我们都会得到类似的结果（在上面的示例中，每个种子丢弃的生成器数量为 10 个）。[请注意，当我们进行相同的实验时，我们没有得到相同的行为，请参阅后面]。tf-random

如果我们使用先前生成的生成器生成连续的布尔值（我猜这是最初设计使用的方式，因为它本身返回一个新的生成器），我们似乎会得到更合理的结果：random

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)]

因此，我们得到 4935 个单例（大致等于 0.5*10000）、2513 个双元组（大致等于 0.5^2*10000）、1273 个三元组（大致等于 0.5^3*10000）等，这是我们预期的。

因此，如果我们（通过）生成一个随机序列，其中每个连续的随机数都是与连续的种子一起生成的，其中我们为每个种子丢弃相同数量的生成器，则无论丢弃的生成器数量如何，不良的相关性仍然存在。System.Random

导致这种情况的随机数生成的算法属性是什么？System.Random

请注意，如果我们使用上面的失败方法（redditt文章），那么我们会得到预期的结果：tf-random

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)]

即 50% 是单例，25% 是双组（2 人一组），等等......