随机数生成器中的种子到底是什么?

机器算法验证 随机生成
2022-01-16 20:36:07

我尝试了一些常用的谷歌搜索等,但我发现的大多数答案要么有些模棱两可,要么是特定于语言/库的,例如 Python 或 C++stdlib.h等。我正在寻找与语言无关的数学答案,而不是库的细节。

例如,许多人说种子是随机数生成器的起点,相同的种子总是产生相同的随机数。这是什么意思?这是否意味着输出数是特定种子的确定性函数,随机性来自种子的值?但如果是这样的话,那么通过提供种子,我们程序员是不是在创造随机性而不是让机器来做呢?

另外,在这种情况下,起点意味着什么?这是说地图的一种不严谨的方式吗?还是我有什么问题?xXf:XY

3个回答

大多数伪随机数生成器 (PRNG)都建立在涉及某种递归方法的算法上,该算法从由称为“种子”的输入确定的基值开始。大多数统计软件(R、Python、Stata 等)中的默认 PRNG 是Mersenne Twister 算法MT19937,该算法在Matsumoto 和 Nishimura (1998)中有阐述。这是一个复杂的算法,因此如果您想详细了解它的工作原理,最好阅读有关它的论文。在这个特定的算法中,有一个次数为的递归关系,你的输入种子是一组初始向量该算法使用线性递归关系生成:nx0,x1,...,xn1

xn+k=f(xk,xk+1,xk+m,r,A),

其中是可以在算法中指定为参数的对象。由于种子给出了初始向量集(并给出了算法的其他固定参数),因此算法生成的一系列伪随机数是固定的。如果更改种子,则更改初始向量,这会更改算法生成的伪随机数。这当然是种子的功能。1mnrA

现在,需要注意的是,这只是一个使用 MT19937 算法的示例。有许多 PRNG 可以在统计软件中使用,并且它们各自涉及不同的递归方法,因此种子在它们中的每一个中意味着不同的事物(从技术角度来说)。R您可以在本文档中找到一个 PRNG 库,其中列出了可用的算法和描述这些算法的论文。

种子的目的是允许用户“锁定”伪随机数生成器,以允许可复制的分析。一些分析师喜欢使用真正的随机数生成器 (TRNG)设置种子,该生成器使用硬件输入生成初始种子数,然后将其报告为锁定数。如果种子是由原始用户设置和报告的,那么审核员可以重复分析并获得与原始用户相同的伪随机数序列。如果种子没有设置,那么算法通常会使用某种默认种子(例如,来自系统时钟),并且通常不可能复制随机化。

首先,今天计算机生成的“随机数”没有真正的随机性。所有伪随机生成器都使用确定性方法。(可能,量子计算机会改变这一点。)

艰巨的任务是设计生成的输出无法有意义地与来自真正随机源的数据区分开来的算法。

你是对的,设置种子会让你从一长串伪随机数中的一个特定已知起点开始。对于用 R、Python 等实现的生成器,这个列表非常长。足够长的时间,即使是最大的可行模拟项目也不会超过生成器的“周期”,从而使值开始循环。

在许多普通的应用程序中,人们不会设置种子。然后会自动挑选一个不可预测的种子(例如,从操作系统时钟上的微秒开始)。一般使用的伪随机发生器已经过测试,主要包括已证明难以用早期不令人满意的发生器模拟的问题。

通常,生成器的输出由一些值组成,出于实际目的,这些值无法与从然后操纵这些伪随机数以匹配从其他分布(例如二项分布、泊松分布、正态分布、指数分布等)中随机抽样的结果。(0,1).

对生成器的一项测试是查看其在模拟为 的“观察”中的连续对是否实际上看起来像是在随机填充单位正方形。(在下面完成两次。)略带大理石花纹的外观是固有可变性的结果。得到一个看起来完全一致的灰色的情节是非常可疑的。[在某些分辨率下,可能存在规则的波纹图案;如果发生这种虚假效果,请向上或向下更改放大倍率以消除这种虚假效果。]Unif(0,1)

set.seed(1776);  m = 50000
par(mfrow=c(1,2))
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
par(mfrow=c(1,1))

在此处输入图像描述

设置种子有时很有用。一些这样的用途如下:

  1. 在编程和调试时,有可预测的输出是很方便的。如此多的程序员set.seed在编写和调试完成之前将语句放在程序的开头。

  2. 在教授模拟时。如果我想向学生展示我可以使用 R 中的函数模拟公平骰子的滚动sample,我可以作弊,运行许多模拟,然后选择最接近目标理论值的一个。但这会给仿真的真正工作方式带来不切实际的印象。

如果我在开始时设置种子,模拟每次都会得到相同的结果。学生可以校对他们的我的程序副本,以确保它给出预期的结果。然后他们可以使用自己的种子或让程序选择自己的起点来运行自己的模拟。

例如,掷两个公平骰子时得到总数为 10 的概率是通过一百万次 2 骰子实验,我应该得到大约 2 位或 3 位的准确度。95% 的模拟误差幅度约为

3/36=1/12=0.08333333.
2(1/12)(11/12)/106=0.00055.

    set.seed(703);  m = 10^6
    s = replicate( m, sum(sample(1:6, 2, rep=T)) )
    mean(s == 10)
    [1] 0.083456         # aprx 1/12 = 0.0833
    2*sd(s == 10)/sqrt(m)
    [1] 0.0005531408     # aprx 95% marg of sim err.
  1. 共享涉及模拟的统计分析时。 如今,许多统计分析都涉及一些模拟,例如置换检验或吉布斯采样器。通过显示种子,您可以使阅读分析的人能够准确地复制结果,如果他们愿意的话。

  2. 在撰写涉及随机化的学术文章时。学术文章通常要经过多轮同行评审。绘图可以使用例如随机抖动的点来减少过度绘图。如果需要根据审稿人的评论对分析进行轻微更改,最好在审稿轮次之间不改变特定的无关抖动,这可能会让特别挑剔的审稿人感到不安,因此您在抖动之前设置种子。

TL;博士;

种子通常使您能够重现随机数序列。从这个意义上说,它们不是真正的随机数,而是“伪随机数”,因此是 PNR 生成器 (PNRG)。这些是现实生活中的真正帮助!

更详细一点:

几乎所有用计算机语言实现的“随机”数生成器都是伪随机数生成器。这是因为给定一个起始值(===> 种子),它们将始终提供相同的伪随机结果序列。一个好的生成器将产生一个无法区分的序列 - 在统计方面 - 与真正的随机序列(投掷真正的骰子,真正的硬币等)。

在许多模拟案例中,您希望获得真正的“随机”体验。但是,您还希望能够重现您的结果。为什么?好吧,至少监管机构对这种奇特的事情感兴趣。

有很多东西可以深入研究。人们甚至对“最佳”随机种子进行分析。在我看来,这会使他们的模型无效,因为他们无法处理“真正的”随机行为——或者他们的 PRNG 不适合他们的实现。大多数时候,他们只是没有做足够的模拟——但他们需要时间。

现在想象一个“真正的”RNG。可以基于机器中的一种随机性来实现这一点。如果您只采用随机种子(例如现在的时间),您会创建一种随机起点,但序列的随机性仍然取决于确定下一个数字的算法。在大多数情况下,这比起点更重要,因为结果的分布决定了实际的“结果”。如果您的序列应该是真正随机的,您将如何实现呢?可以说计算机的时钟滴答是确定性的,否则可能会显示出很多自相关。所以,你可以做什么?到目前为止,最好的选择是实施可靠的 PNRG。

量子计算?我不确定这会解决它。