伪随机性

伪随机数字序列是一种看似统计随机的数字序列，尽管它是由完全确定且可重复的过程产生的。

随机数的生成有很多用途，例如用于随机抽样、蒙特卡罗方法、棋盘游戏。 然而，在物理学中，大多数过程，例如重力加速度，都是确定性的，这意味着它们总是从相同的起点产生相同的结果。 一些值得注意的例外是放射性衰变和量子测量，它们都被建模为基础物理学中的真正随机过程。 由于这些过程不是随机数的实际来源，人们使用伪随机数，尽管它是由确定性过程生成的，但理想情况下它具有真正随机序列的不可预测性。

在许多应用中，确定性过程是一种称为伪随机数生成器的计算机算法，必须首先为其提供一个称为随机种子的数字。 由于相同的种子每次都会产生相同的序列，因此精心选择种子并保持隐藏非常重要，特别是在安全应用程序中，模式的不可预测性是一个关键特征。

在某些序列明显不可预测的情况下，人们使用了随机数的物理来源，例如放射性衰变、从电台之间调谐的收音机收集的大气电磁噪声，或者人们击键的混合时间。 获得这些数字所需的时间投入导致折衷：使用其中一些物理读数作为伪随机数生成器的种子。

在现代计算出现之前，需要随机数的研究人员要么通过各种方式生成随机数，要么使用现有的随机数表。

为研究人员提供现成的随机数字的xxx次尝试是在 1927 年，当时剑桥大学出版社出版了由 L.H.C. 开发的包含 41,600 个数字的表格。 蒂皮特。 1947年，兰德公司通过xxx的电子模拟产生数字； 结果最终于 1955 年作为具有 100,000 个正常偏差的百万随机数字发表。

在理论计算机科学中，如果没有来自该类对手的对手能够将其与具有显着优势的均匀分布区分开来，则该分布是针对一类对手的伪随机分布。这种伪随机性的概念在计算复杂性理论中得到研究，并在密码学中得到应用。

形式上，令 S 和 T 为有限集，令 F = {f: S → T} 为一类函数。 如果对于 F 中的每个 f，分布与 f ( X ) {displaystyle f(X)} 之间的统计距离，其中 X {displaystyle X} 是从 D, and f ( Y ) {displaystyle f(Y)} ，其中 Y {displaystyle Y} 从 S 上的均匀分布中采样，最多为 ε。

在典型应用中，类 F 描述了一种具有有限资源的计算模型，人们对设计具有特定伪随机属性的分布 D 感兴趣。分布 D 通常被指定为伪随机生成器的输出。