使用相似的种子时，为什么初始随机数会相似？

Question

使用相似的种子时，为什么初始随机数会相似？

javarandom

30

我发现使用Java的Random类生成随机数时有些奇怪。基本上，如果你使用相近的种子创建多个Random对象（比如在1到1000之间），每个生成器生成的第一个值几乎相同，但下一个值看起来正常（我没有进一步研究）。

以下是种子从0到9生成的前两个双精度随机数：

0 0.730967787376657 0.24053641567148587
1 0.7308781907032909 0.41008081149220166
2 0.7311469360199058 0.9014476240300544
3 0.731057369148862 0.07099203475193139
4 0.7306094602878371 0.9187140138555101
5 0.730519863614471 0.08825840967622589
6 0.7307886238322471 0.5796252073129174
7 0.7306990420600421 0.7491696031336331
8 0.7302511331990172 0.5968915822372118
9 0.7301615514268123 0.7664359929590888

而从991到1000：

991 0.7142160704801332 0.9453385235522973
992 0.7109015598097105 0.21848118381994108
993 0.7108119780375055 0.38802559454181795
994 0.7110807233541204 0.8793923921785096
995 0.7109911564830766 0.048936787999225295
996 0.7105432327208906 0.896658767102804
997 0.7104536509486856 0.0662031629235198
998 0.7107223962653005 0.5575699754613725
999 0.7106328293942568 0.7271143712820883
1000 0.7101849056320707 0.574836350385667

这里展示了通过从0到100,000使用不同的种子生成的第一个值。

基于种子生成的第一个随机双精度浮点数：

我搜索了相关信息，但并没有找到涉及此特定问题的资料。我知道 LCGs 算法存在许多问题，但我不知道这个问题，想知道这是否是已知问题。

另外，您是否知道这个问题是否仅适用于第一个值（或少数几个值），还是更普遍，需要避免使用接近的种子？

谢谢。

- Jeg

1

我认为通常使用种子可以减少随机性。你应该尽可能地使你的种子更随机，最好不要使用任何一个。 ;) 许多SecureRandom实现会忽略提供的种子。 - Peter Lawrey

有许多随机化函数。 - huseyin tugrul buyukisik

3

你明白“种子”是什么吗？这不是一个哈希函数，不要期望在稍微改变种子的情况下同时得到完全不同的结果。请注意，此处不提供解释。 - Shark

3

你可能会觉得这很有趣。http://vanillajava.blogspot.co.uk/2011/10/randomly-no-so-random.html 如果你想使用种子，你需要小心选择。注意：随机数生成器只使用种子的48位，并且不会生成每个可能的“long”或“double”。 - Peter Lawrey

https://dev59.com/_kbRa4cB1Zd3GeqPxy6a - auselen

显示剩余3条评论

4个回答

4

我不认为这是一个“问题”。

而且，您是否知道此问题仅针对第一个值（或前几个值），还是更普遍，并且应避免使用相似的种子？

在非加密 PRNG 中，连续数字之间的相关模式是常见问题，这只是其中一种表现形式。相关性（严格的自相关）固有于支撑算法的数学中。如果您想了解更多，请阅读 Knuth 的计算机编程艺术第三章的相关部分。

如果您需要不可预测性，则应为 Random 使用（真正的）随机种子...或让系统为您选择“相当随机”的种子；例如，使用无参构造函数。或者更好地，使用真正的随机数源或加密质量的 PRNG 而不是 Random。

记录如下：

Java 7 的 javadoc 没有指定 Random() 如何进行种子处理。
Linux 上 Java 7 的 Random() 实现是从纳秒时钟种子化的，与“唯一化”序列异或。唯一化序列是 LCG，使用不同的乘数，并且其状态是静态的。这旨在避免种子的自相关性...

- Stephen C

无参构造方法使用System.currentTimeMillis()作为种子，因此在大约同时实例化的不同Random类的实例将返回相关值。建议修改最后一段以提到改用SecureRandom。 - matt b

这个答案唯一更好的方式就是它能够解释这个相关性背后的数学原理。 - Erick Robertson

2

@ErickRobertson - 这对于一个非数学家来说要求太高了 :-) - Stephen C

1

@mattb - 1）Java 7的javadoc没有说明Random()如何进行种子初始化。2）在Linux上的Java 7中，它是从纳秒时钟进行种子初始化，并使用不同的LCG实现“唯一化”序列，其状态为static。这旨在避免种子的自相关性... - Stephen C

@StephenC 这很有趣，我没有意识到我看的是哪个版本，我的谷歌搜索带我来到了1.4.2文档，其中确实指定了使用currentTimeMillis()。看起来他们在JDK5中就改变了描述。此外，在OS X JDK 6上，构造函数看起来像public Random() { this(++seedUniquifier + System.nanoTime()); }，我不认为这会是一个XOR操作。 - matt b

1

@mattb - 在Java 7中进行了XOR运算，并且唯一标识符更加复杂。相信我...或者下载并阅读源代码。不要依赖古老的1.4.2 javadocs :-) - Stephen C

2

这是伪随机种子的一个相当典型的行为 - 它们不需要提供完全不同的随机序列，只需保证如果使用相同的种子，您可以再次获得相同的序列。

该行为发生的原因是PRNG的数学形式 - Java使用线性同余生成器，因此您只是看到将种子通过线性同余生成器的一轮运行的结果。这还不足以完全混合所有位模式，因此您会看到类似于相似种子的结果。

您最好的策略可能就是使用非常不同的种子 - 一种选择是通过哈希当前使用的种子值来获得它们。

- mikera

-1

通过生成随机种子（例如，使用System.currentTimeMillis()或System.nanoTime()上的某些数学函数进行种子生成），您可以获得更好的随机结果。还可以查看此处获取更多信息。

- Amir

1

-1 这并没有回答问题。看起来楼主已经意识到了这一点，但他正在使用固定的种子以便能够重现结果。 - Erick Robertson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex · Accepted Answer

最好的方式是下载并阅读Random源码以及一些伪随机生成器的论文，但这里是源码中的一些相关部分。首先，有三个常量参数控制算法：

private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) - 1;

乘数约为2的34次方，掩码为2的48次方减1，对于此分析而言，加法因子非常接近于0。

使用种子创建随机数时，构造函数会调用setSeed：

synchronized public void setSeed(long seed) {
    seed = (seed ^ multiplier) & mask;
    this.seed.set(seed);
    haveNextNextGaussian = false;
}

您提供的种子非常接近于零，因此在将两者 OR 运算在一起时，初始种子值被 multiplier 主导。在所有接近于零的测试用例中，内部使用的种子大约为 2^34；但是很容易看出，即使您提供了非常大的种子数字，类似的用户提供的种子也会产生类似的内部种子。

最后一个部分是 next(int) 方法，它基于当前种子实际生成请求长度的随机整数，然后更新种子：

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

这是一种称为“线性同余”伪随机生成器，意味着它通过将当前种子乘以一个常数乘数，然后加上一个常数加数（然后进行掩码操作以取出较低的48位）来生成每个连续的种子。生成器的质量取决于乘数和加数的选择，但所有此类生成器的输出都可以根据当前输入轻松预测，并且在重复之前具有一定的周期（因此建议不要在敏感应用中使用它们）。

您看到给定相似种子的nextDouble的类似初始输出的原因是，因为计算下一个整数只涉及乘法和加法，所以下一个整数的大小不会受到较低位差异的影响很大。计算下一个double涉及基于种子计算一个大整数，并将其除以另一个（常数）大整数，结果的大小主要受整数的大小影响。

由于重复乘以常数乘数并且因为48位掩码每次都会丢弃最高位，因此重复计算下一个种子将放大种子低位的差异，直到最终看到像均匀分布一样的结果。