haskell - RandomGen 的 split 函数的确切语义应该是什么？

Question

似乎在 Haskell 中，split 的行为在很大程度上取决于所选择的(伪)随机数生成器 (PRNG)。通过查看 API 中生成随机数的各种方式，我被 split 吸引了。

假设我们采用相对较新的 Threefish发电机。

我们需要:

 λ> import System.Random
 λ> import System.Random.TF
 λ> import Control.Monad.Random

接下来，我们以 3 种不同的方式生成 20 个两位数的序列:

 λ> tg0 = mkTFGen 42
 λ> 
 λ> evalRand  (sequence (replicate 20 $ getRandomR (10,99)))  tg0
[62,99,78,18,38,21,54,25,54,94,62,57,55,69,98,78,99,73,59,24]
 λ> 
 λ> take 20 $ evalRand  (sequence (repeat $ getRandomR (10,99)))  tg0
[62,99,78,18,38,21,54,25,54,94,62,57,55,69,98,78,99,73,59,24]
 λ> 
 λ> take 20 $  evalRand  (getRandomRs (10,99))  tg0
[62,99,78,18,38,21,54,25,54,94,62,57,55,69,98,78,99,73,59,24]
 λ> 

无论我们是否使用无限序列的前缀，我们都会得到相同序列的 3 次。

但对于“标准”StdGen 生成器而言并非如此。这里:

 λ> 
 λ> sg0 = mkStdGen 42
 λ> 
 λ> evalRand  (sequence (replicate 20 $ getRandomR (10,99)))  sg0
[69,79,35,32,84,89,76,39,16,73,73,37,34,96,12,23,45,59,31,34]
 λ> 
 λ> take 20 $ evalRand  (sequence (repeat $ getRandomR (10,99)))  sg0
[69,79,35,32,84,89,76,39,16,73,73,37,34,96,12,23,45,59,31,34]
 λ> 
 λ> take 20 $  evalRand  (getRandomRs (10,99))  sg0
[33,66,18,33,73,38,73,35,59,82,42,44,48,20,58,21,89,14,43,14]
 λ> 

所以在这里，第三个序列与其他序列不同。事实证明，这是因为 getRandomRs 在当前生成器上调用了 split。

可以这样直接检查:

 λ> 
 λ> (sg0a, sg0b) = split sg0
 λ> (tg0a, tg0b) = split tg0
 λ> 
 λ> :{
|λ> let { getRandomDouble :: RandomGen g => g -> Double ;
|λ>       getRandomDouble g = fst $ random g }
|λ> :}
 λ> 
 λ>  λ> 
 λ> getRandomDouble tg0
0.6499718678721916
 λ> getRandomDouble tg0a
0.6499718678721916
 λ> 
 λ> getRandomDouble tg0b
0.7724686371301966
 λ> 
 λ> getRandomDouble sg0
1.0663729393723398e-2
 λ> getRandomDouble sg0a
0.36531519389010025
 λ> 
 λ> getRandomDouble sg0b
0.7740913257381021
 λ> 

因此，在 Threefish 生成器的情况下，拆分的左侧组件(由 getRandomRs 使用)生成与原始序列相同的序列。对于 StdGen 生成器，它生成不同的序列，导致开头提到的令人惊讶的结果。

stdSplit 函数的源代码是 here .它包括一条评论:

    -- no statistical foundation for this!

问题:stdSplit 的行为是否合法(符合语言标准)和/或统计合法？我知道可能有必要不破坏现有的客户端代码，但是是否有关于此的指南适用于较新的 PRNG？

注意: PRNG API 提供split 函数的情况并不常见。提供 advance 功能更为常见，如 Python/NumPy 中的此处所示例如，可以根据需要使用 advance 函数创建额外的生成器。对于某些 PRNG，advance 函数的成本仅为 O(log(numSteps))。

Answer 1

事实上，H. G. Schaathun 在 2015 年的“Evaluation of Splittable Pseudo-Random Generators”中评估了 StdGen、tf-random 和其他可拆分伪随机生成器的统计质量，发现大多数生成器在统计上存在缺陷，除了tf-随机。 (SplitMix 是“在 [那篇] 论文最初提交后发表的”，因此没有在那里进行研究；然而，recent testing 表明它在统计上似乎表现不错。)