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

这个问题关系到当人们从连续的种子产生连续的随机数时，人们用System.Random观察到的时间相关性的起源(其中，每个种子丢弃相同数量的发生器)。

在Using mkStdGen from System.Random to generate random booleans Answer 1和Using mkStdGen from System.Random to generate random booleans Answer 2中，建议(基于引用它们的reddit文章)建议丢弃前几个生成器，以便获得合理的结果。但是我发现，不管丢弃多少个生成器，当人们观察分布的时间方面时，如果使用连续的种子生成连续的随机数(对于每个种子而言，丢弃相同数量的生成器)，则将获得不期望的结果。

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

如果我们生成一个无限的随机 bool 序列，则获得具有相同值的P(n)连续 bool 值(例如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)]

使用来自连续种子的生成器生成每个连续 bool 值，并在使用结果随机结果之前丢弃10个生成器。会生成10000个随机数序列，因此我们期望大约5000个 bool 值后跟相反的 bool 值(例如[True]中的[False,True,False,False])，因为会有2500个 bool 值，其后是相同的 bool 值，然后是相反的 bool 值(例如[True,True]中的[False,True,True,False])，分为3s的大约1250个 bool 值，等等。

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

如果我们改为使用先前生成的生成器生成连续的 bool 值(我猜这是它最初设计时使用的方式，因为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人一组)，依此类推...

最佳答案

让我们先看一下代码中所说的内容，然后我们就可以到达目标了。

首先，应用于random的Bool等效于:

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

实际上，如果在您的程序中将random替换为randomB，我将得到相同的结果。关键是要确定 bool 值，我们只关心下一个Int值是偶还是奇。

接下来，让我们看一下StdGen的定义:

data StdGen
 = StdGen Int32 Int32

因此，两个Int32是状态。让我们看看如何使用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'

请注意两个有趣的事情:

除非您向s2发送一个非常高的数字，否则mkStdGen的初始化方式将确保它为1，在这种情况下它将为2(在Int32范围内，将s2初始化为2的值少于200。

状态的两个部分保持不同-更新的s2仅取决于先前的s2，而不取决于先前的s1，反之亦然。

结果，如果您检查传递给better_mkStdGen的一定固定数量的生成器中的生成器，则它们状态的后半部分将始终相同。

通过将其添加到您的程序中来进行尝试:

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

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

在这一点上，我需要动手一点，并说计算s1'的方式意味着，如果s1的两个初始值彼此接近，那么s1'的两个值也将接近，并且通常只有40014次距离它们最初的距离很远，在我们允许的s1范围内，相邻值很有可能最终落在零的同一侧。

关于algorithm - 使用System.Random时的时间相关性(使用System.Random.TF时不存在)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22128765/