线性全等生成器中的超平面问题

机器算法验证 随机生成
2022-03-17 10:32:16

来自维基百科

如果使用 LCG 在 n 维空间中选择点,则这些点最多位于m1/n超平面(Marsaglia 定理,由 George Marsaglia 开发)。这是由于序列的连续值之间的序列相关性Xn.

在此处输入图像描述

  1. 在数学上,序列的连续值之间的序列相关性是什么Xn?

  2. 我想知道一个时期内的点是如何分布到不同的超平面的,因为它们是按顺序一个接一个地生成的?我猜这些点不太可能先填写一个超平面,然后再填写下一个,并且永远不会在单周期内访问之前访问过的超平面?

    对每个固定超平面的每两次连续访问之间的时间间隔是否固定,并且对于所有超平面都相同?它与LCG的周期有关吗?

    采取一个完整周期序列的一小部分是否以某种方式克服了 LCG 的这个缺点?这就是我问上述问题的原因。

  3. 注意我认为有一个错字。“最多,m1/n超平面”应该是“最多,(n!m)1/n超平面”。我说得对吗?

谢谢!

1个回答
  1. corr(Rt,Rt1)1a(16cm+6(cm)2)+a+6m

    此公式改编自 Greenberger,1961[1],他在初始近似中给出了上面的第一项,然后给出了另一个带有附加项的近似。

    序列相关性通常非常小,即使对于较差的生成器也是如此

  2. 您自己的动画表明这些点不会“首先填充一个超平面”,因为您会看到不同的平面随着时间的推移获得更多的点。动画的第一步显示来自几个不同平面的点,然后更多,随着它的进行,较早的平面得到更多的点

    对每个固定超平面的每两次连续访问之间的时间间隔是否固定,并且对于所有超平面都相同?

    这个我不确定。我相信有一个通过超平面的循环。

    采取一个完整周期序列的一小部分是否以某种方式克服了 LCG 的这个缺点?

    不。

  3. 是的,它应该。截至 2014 年 5 月 31 日,对指示页面的编辑使其符合您的公式

我建议查看 DIEHARD 测试和 RNG 的类似测试

 

[1]:Greenberger, Martin (1961),
“计算机生成随机数中序列相关性的先验确定”,
数学。比较。 15 , 383-389 ( pdf )
(勘误: Math. Comp. 16 (1962), 406-406.)