使用System.Random时的时间相关性(使用System.Random.TF时不存在)

Question

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

在使用System.Random中的mkStdGen生成随机布尔值答案1并使用System.Random中的mkStdGen生成随机布尔值答案2建议(基于引用其中的reddit文章)应该丢弃前几个生成器以获取明智的结果.然而,我发现不管有多少发生器丢弃,当观察分布的时间方面时,如果用连续种子生成连续的随机数(一个丢弃每个种子的相同数量的生成器),则获得不希望的结果.

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

如果我们生成无限序列的随机布尔值,则P(n)获得n具有相同值(例如[True,True,True]in [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个布尔值跟随相反的布尔值(例如[True]in [False,True,False,False]),因为有2500个布尔值,后面跟着相同的布尔值,但后面跟着相反的布尔值(例如[True,True]in [False,True,True,False]),大约1250个布尔组合成3s等.

因此,从上面的代码我们得到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 什么？

请注意,如果我们使用上面的失败方法tf-random(redditt文章),那么我们得到预期的结果:

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人组),等等......

Answer 1

让我们首先看看代码的内容，然后我们就可以到达那里。

首先，random应用于Bool相当于：

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

事实上，如果我用程序中合适的位置替换，我会得到相同的结果random。randomB关键是，为了确定布尔值，我们所关心的是下一个是否是Int值是偶数还是奇数。

接下来我们看一下 的定义StdGen：

data StdGen 
 = StdGen Int32 Int32

所以两个Int32s 就是状态。让我们看看它们是如何初始化mkStdGen以及如何调整的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'

请注意两件有趣的事情：

1. 初始化的方式s2保证它将为 1，除非您向 发送一个非常大的数字mkStdGen，在这种情况下它将是 2（该范围内的值少于 200 个，Int32将初始化s2为 2。

2. 状态的两半保持不同 - 更新s2仅取决于前一个s2，而不取决于前一个s1，反之亦然。

因此，如果您检查从传递给的特定固定代数中获得的生成器better_mkStdGen，它们状态的后半部分将始终相同。

尝试将其添加到您的程序中：

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

那么问题来了，为什么混合函数s1无法正确混合最后一位。请注意，它的写入方式 和s1'与k具有相同的奇偶校验s1，因此如果最终小于零，则该s1状态仅与前一个状态具有不同的奇偶校验。s1s1'

此时我需要稍微挥一下手，说s1'计算出的方式意味着如果 的两个初始值s1彼此接近，那么这两个 的值s1'也会接近，并且通常只会相差 40014 倍正如它们最初一样，在我们允许的范围内，s1相邻值很可能最终位于零的同一侧。