从历史上看,伪 RNG 的范围是否为 [0,1] 是因为易于从Ff使用F− 1( p )F−1(p),还是其他原因?

机器算法验证 随机生成 历史
2022-03-24 18:48:40

一种从概率密度函数模拟随机抽取的简单但不一定有效的方法f,是将逆累积分布函数应用于从 0 到 1 均匀分布的随机变量。我(几乎不)熟悉的伪随机数生成器 (RNG) 会产生具有这种分布的伪随机值。

我不太了解 RNG 的开发历史,但我想知道 RNG 默认行为是否是明确设计的,因为它适合从任意分布(或至少从具有可计算逆累积分布函数的任意分布)模拟?或者是否还有其他原因导致 RNG 算法输出的范围应为 [0,1] - 而不是 [-1, 1]、[0, 浮点限制] 或 [0, 长限制] 等 - 特别是统一,而不是其他一些分布?

我知道,除了统计属性之外,计算算法还有其他属性,例如安全性、内存使用、计算复杂性等,这些都会影响 RNG 算法的开发和采用;欢迎任何见解。

2个回答

原则上,任何连续分布都可以作为随机数生成器的起点。尽管如此,标准的连续均匀分布是伪随机数生成器 (PRNG) 的自然起点,主要原因如下:

  • 逆变换采样的方法允许我们从一个标准的均匀随机变量生成任何随机变量,而后者是这个计算的自然起点。特别是,将标准均匀随机变量转换为具有另一种分布的随机变量的数学特别简单和直观。

  • 为了测试 PRNG 方法的准确性,标准均匀分布具有特别简单的特性。这些方法要经过一系列测试,以确保它们具有随机数生成器所需的特性。对于生成标准连续均匀随机变量的 PRNG,这些测试特别容易构建。例如,对于均匀随机变量,标准占用测试特别容易部署。

  • 生成实数的计算方法会出现舍入误差。在大多数平台中,数字以双精度浮点格式存储,并且这种格式在小数部分具有固定的精度水平。在生成标准连续均匀随机变量时,小数部分的值之间的区间具有固定概率,因此没有区间大于或小于其他区间。(与此推理相反,请注意,这也可以说是首选指数随机变量作为分析起点的原因,因为浮点格式使用指数。)

审查 PRNG。一、标准均匀分布Unif(0,1)在数学上很简单。因此,出于实际目的,假设从标准统一总体的随机样本中无法区分的伪随机数,很容易测试该声明是否正确。

例如,接近1/10th 的观测值应位于每个区间内(0.1k,0.1k+.1),为了k=0,,9,我们可以做一个卡方拟合优度检验,看看这是否属实。

今天在 R 中,该过程runif(10^4)生成10000观察据推测来自 Unif(0,1).

set.seed(510)
u = runif(10^4)
hist(u, br=seq(0,1,by=.1), ylim=c(0,1200), label=T)

在此处输入图像描述

x = hist(u, br=seq(0,1,by=.1), plot=F)$counts; x
[1]  959  960 1044 1048  966 1001 1044 1001  990  987

所以我们看到10000观察结果与来自的样本一致Unif(0,1).[chisq.test如果没有提供其他概率,则假定组的概率相等。]

chisq.test(x)

        Chi-squared test for given probabilities

data:  x
X-squared = 10.884, df = 9, p-value = 0.2837

    Chi-squared test for given probabilities

data:  x
X-squared = 10.884, df = 9, p-value = 0.2837

依此类推,通过更多测试来验证随机数生成器是否有用。

连续分布的分位数方法。其次,正如您所说,可以使用分位数(逆 CDF)变换从各种其他分布中获取样本。所以下面的变换应该给我们一个伪随机样本Exp(1).

w = qexp(runif(10^5), 1)
hist(w, prob=T, br=50, col="skyblue2")
 curve(dexp(x,1), add=T, col="red", n=10001)

在此处输入图像描述

在上图中,标准的均匀密度曲线似乎非常适合数据的密度直方图。此外,Kolmogorov-Smirnov 检验不会拒绝原假设,即其中的前 5000 个值w是来自标准均匀分布的样本。[该测试不允许样本大于 5000。]

ks.test(w[1:5000], pexp, 1)

        One-sample Kolmogorov-Smirnov test

data:  w[1:5000]
D = 0.0054447, p-value = 0.9984
alternative hypothesis: two-sided

检验统计量DKS 检验的最大垂直差异是目标 CDF 与样本的经验 CDF之间的最大垂直差异 (样本值的阶梯函数,近似于 CDF)。我们以大小为 100 的样本进行说明。

ks.test(w[1:100], pexp, 1)

        One-sample Kolmogorov-Smirnov test

data:  w[1:100]
D = 0.076693, p-value = 0.5988
alternative hypothesis: two-sided

plot(ecdf(w[1:100]))
curve(pexp(x,1), add=T, col="red", lwd=2)

在此处输入图像描述

离散分布的分位数方法。分位数变换方法也适用于离散随机变量(前提是分位数函数经过仔细编程,就像在 R 中一样)。所以让我们模拟一个样本Binom(10,.5): [R 过程ks.test不适用于离散分布。]

v = qbinom(runif(5000), 10, .5)
hist(v, prob=T, br = (-1:10)+.5, col="skyblue2")
  vv = 0:10;  pdf = dbinom(vv, 10, .5)
  points(vv, pdf, col="red")

在此处输入图像描述

注意:(1)在 R 中,我们用来生成正态随机样本的分位数方法——即使正态 CDF 不能以封闭形式表示,因此不能在解析上倒置。R 使用 Michael Wichura 对标准正态 CDF 的(分段)有理逼近,以及他的反演。结果精确到双精度算术。

set.seed(2020);  rnorm(1)
[1] 0.3769721
set.seed(2020);  qnorm(runif(1))
[1] 0.3769721

模拟标准正态变量的早期方法是(a)使用i=12Ui6,在哪里UiiidUnif(0,1),它依赖于 CLT 对均匀随机变量的快速收敛,并且只需要简单的算术运算,并且 (b) 使用Box-Muller 变换,它在某种程度上更准确,需要计算对数和三角函数。

(2) 毫无疑问,还有很多其他原因:其中一些从 1950 年代中期就失去了历史,而另一些可能还没有在其他答案或评论中出现。