algorithm - 关于随机数序列生成

Question

我是随机算法的新手，通过阅读书籍自学。我正在阅读 Mark Allen Wessis 的《数据结构和算法分析》一书.

Suppose we only need to flip a coin; thus, we must generate a 0 or 1 randomly. One way to do this is to examine the system clock. The clock might record time as an integer that counts the number of seconds since January 1, 1970 (atleast on Unix System). We could then use the lowest bit. The problem is that this does not work well if a sequence of random numbers is needed. One second is a long time, and the clock might not change at all while the program is running. Even if the time were recorded in units of microseconds, if the program were running by itself the sequence of numbers that would be generated would be far from random, since the time between calls to the generator would be essentially identical on every program invocation. We see, then, that what is really needed is a sequence of random numbers. These numbers should appear independent. If a coin is flipped and heads appears, the next coin flip should still be equally likely to come up heads or tails.

以下是关于上述文本片段的问题。

1. 在上面的文本片段“我们可以使用最低位的秒数”中，作者提到这不起作用，因为一秒是很长的时间，和时钟可能根本不会改变”，我的问题是为什么一秒钟是很长的时间而时钟每秒都会改变，以及作者在什么情况下提到那个时钟不改变？请求通过简单的例子帮助理解。

2. 作者是如何提到即使在几微秒内我们也得不到随机数序列的？

谢谢!

Answer 1

使用随机(或在本例中为伪随机)数字的程序通常在短时间内需要大量的数字。这就是为什么简单地使用时钟并没有真正起作用的原因之一，因为系统时钟的更新速度不如您的代码请求新数字的速度快，因此很可能一遍又一遍地获得相同的结果，直到时钟变化。它在 Unix 系统上可能更引人注目，在该系统中，获取时间的常用方法只能提供秒级精度。甚至微秒也无济于事，因为现在的计算机比微秒快得多。

您要避免的第二个问题是伪随机值的线性相关性。想象一下，您想在一个正方形中随机放置一些点。您将选择一个 x 和一个 y 坐标。如果您的伪随机值是一个简单的线性序列(就像您天真地从时钟中获得的那样)，您将得到一条对角线，其中许多点聚集在同一位置。这真的行不通。

最简单的伪随机数生成器类型之一，Linear Congruental Generator有一个类似的问题，尽管乍一看并不那么明显。由于公式非常简单

你仍然会得到相当可预测的结果，尽管只有当你在 3D 空间中选择点时，因为所有数字都位于许多不同的平面上(所有伪随机生成器在特定维度上都会出现这个问题):