首页 > 其他分享 >科普向-计算机如何生成随机数?(第一期)

科普向-计算机如何生成随机数?(第一期)

时间:2024-09-17 21:23:44浏览次数:10  
标签:random 均匀分布 生成 第一期 分布 随机 随机数 科普

一、背景

我们在日常生活中会遇到许许多多的随机事件,最典型的例子就是抛硬币或者骰子。在生活中,我们想要得到一个随机结果的方式很简单,直接拿一枚硬币或者一个骰子就可得到一个比较随机的结果。

对于这里为什么要用“比较”这个词是因为如果能知道事物的一切信息的话,“随机”也就不再是随机了。这里有点类似“上帝会不会掷骰子”的问题。在这里就不对这点进行深入讨论了。以下内容均是在我们相信不可能得到关于事物的一切信息,即“随机性”存在的基础上进行讨论的。

计算机编程中我们想要生成一个随机数,通常会使用random函数,比如下面这段python代码:

import random
# 生成一个0到1之间的随机浮点数
random_float = random.random()
# 使用random.choice()随机选择一个元素
selected_number = random.choice([1,2])

但是你是否想过这样的问题?计算机的程序都是人们设置好的,那如果是人们提前设置好的程序,怎么会存在”随机“呢?换句话说,计算机是如何生成随机数的?所生成的随机数真的是随机的么?我们如果要用计算机生成随机数就要给计算机定义这些“随机”,但是这样是不是就会变成“确定”而不是“随机”了?

我们接下来就来回答:计算机是用什么方法产生这些随机数以及随机分布的。

二、生成区间[0,1]上的均匀分布

1、NOISE

最容易想到的就是基于Noise的生成方法,这里的噪声指的是计算机的电噪声和热噪声,这些噪声本身具有随机性,因此会产生随机。但这种方式存在的一个重大问题是不可控以及无法重复。事实上我们没办法精准控制每次计算的电噪声以及热噪声。而这种不可重复性使得很多结果不具备可信性。想象一下一篇文章里的数据不同人用不同的电脑算出来的结果和原文差距很大且各不相同,自然就无法验证结论的可靠性。

2、伪随机数生成(PRNG: Pseudo-Random Number Generate)

a)利用线性同余生成(LCG:Linear Congruence Generate)

给定a,\,b,\,m,\,X_0, 考虑下面这个线性同余

X_{n+1}\equiv aX_n+b\,\,\,\,\,\,(mod\,\,\, m) \quad \quad \quad \quad \quad (1)

用这种方法会生成的序列{\frac{X_n}{m}}就是在[0,1]上的均匀分布。

因为做线性同余运算会产生周期性, 事实上这个周期:

Period\,\leqslant\, m\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad\quad\quad (2)

事实上,我们有这样一个定理说明上式 (2) 什么时候取到等号:

Thm 2.1: LCG的周期是m,当且仅当:

<1> b与m互素;

<2>m的每一个素因子可以被a-1整除;

<3>如果m|4,则(a-1)|4

很容易给出一个例子(读者可自行验证)

m=2^k,\,a=4c+1,\,b \text{ is odd number}

当然LCG还有更一般的形式:

X_{n+1}\equiv a_0X_n+a_1X_{n-1}+...+a_jX_{n-j}+b\,\,\,\,\,\,(mod\,\,\, m) \quad \quad \quad \quad \quad (3)

但是这样得到的周期 \tau 最大并不能取到 m^{j+1}-1\tau 的大小是由a_j,b\,\,and \,\,m决定的

关于LCG的一个重要事实是,它显示了s元组即向量(X_n,X_{n-1},...,X_{n+s-1})的非常差的分布.

Marsaglia在Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. USA, 61:25, 1968.中证明了这一重要事实:

Thm 2.2: 一个通过(1)式得到的s元组(X_n,X_{n-1},...,X_{n+s-1})位于一个s维超平面(0,1)^s上的等距平行线上,其最大值为(s!m)^\frac{1}{s}

可以看出当s较大时,相对于均匀分布的偏差是明显的。
尽管LCG有这个缺点,但它仍然是实践中应用最广泛的伪随机数生成器。

(b)线性反馈移位寄存器(LFSR: Linear Feedback Shift Register)

再简单介绍另一种方法LFSR,生成方式如下:

对于一个二进制数字X_k=(a_n,a_{n-1},...,a_1)_B可以生成

X_{k+1}=(b_n,b_{n-1},...,b_2,b_1)_B

其中   b_j=a_{j-1}\,\,\,j\in[2,n],  b_1=\sum_{k=1}^{n-1}w_ka_k+a_n\quad(mod\,2)

三、逆变换法

a) 一个例子

考虑下面的分布,F(x)是概率分布函数,f(x)是概率密度函数,如何让计算机生成下面的分布呢?

事实上,对于如上图所示的分布:

X\sim p(x)d(x),\quad\quad F(x)=\mathbb{P}(X\leq x) ,\quad F(x)\in [0,1]\\\\F(x)=\int_{-\infty}^{x}p(x)dx,\quad\quad p(x)=\frac{dF}{dx}

可以把其看成是Y轴上的均匀分布\mathcal{U}[0,1],通过F^{-1}(y)映射到x轴:

x\doteq F^{-1}(y),\quad\quad y\sim \mathcal{U}[0,1]

根据定义以及y\sim \mathcal{U}[0,1]

\mathbb{P}(X\leq x)=\mathbb{P}(F^{-1}(y)\leq x)=\mathbb{P}(y\leq F(x))=F(x)

因此这样产生的x符合:

X\sim p(x)d(x),\quad\quad F(x)=\mathbb{P}(X\leq x) ,\quad F(x)\in [0,1]

所以用这种逆变换法也可以产生我们需要的分布。

b) 另一个例子:指数分布的生成

对于指数分布exp(\lambda ), 其概率密度函数:

p(x)=\left\{\begin{matrix} \lambda e^{-\lambda x}& x\geq 0 \\ 0& x< 0 \end{matrix}\right.

图像如下:

我们很容易可以得到其分布函数:

F(x)=\int_{0}^{x}p(t)dt=-e^{-\lambda t}|_0^x=1-e^{-\lambda x}\doteq y \quad\quad y \in [0,1)

可以反解出:

x=-\lambda^{-1}log(1-y)

所以我们可以利用前面讲到的生成 \mathcal{U}[0,1] 的方法生成 Y_n \sim\mathcal{U}[0,1]\quad i.i.d, 之后利用上面的式子可以得到:

X_n=-\lambda^{-1}log(1-Y_n), \quad\quad where\,\,Y_n \sim\mathcal{U}[0,1]\quad i.i.d

c) 如何生成[a,b]上的均匀分布\mathcal{U}[a,b]

(i)平移拉伸

对于LCG生成的X_n做下面变换即可:

Y_n=(X_n+a)(b-a), \quad\quad\quad X_n \sim\mathcal{U}[0,1]\quad i.i.d

因此就得到了Y_n \sim\mathcal{U}[a,b]\quad i.i.d

这里就回答了我们一开始的问题,计算机是如何生成随机数的问题。实际上对于给定区间的随机数,就转换成了生成在这个区间的均匀分布问题,我们只需要按上述方法生成一个数即可。这个数就是服从在这个给定区间均匀分布的数,而这个均匀分布本身就代表了随机性。 

(ii)逆变换法

考虑分布函数F(x)=(b-a)^{-1}(x-a)=y,\quad\quad\quad where\,\, y\sim\mathcal{U}[0,1]\quad i.i.d

我们只需要生成y\sim\mathcal{U}[0,1]\quad i.i.d,随后根据 x=F^{-1}(y) 即可得到 x\sim\mathcal{U}[a,b]\quad i.i.d

d)生成两点分布或者多点分布

(i)两点分布

如果要生成[0,1]上的两点分布,我们只需要给定一个阈值 p, 随后生成[0,1]上的均匀分布x\sim\mathcal{U}[0,1],之后再加上条件判断:

if\left\{\begin{matrix} y=1 & x\leq p \\ y=0&x>p \end{matrix}\right.

这样生成的y就服从y \sim \mathcal{B}(p)

(ii)多点分布

类似于两点分布,只需要多加入几个分点(阈值)即可,这里就不过多赘述啦。

这样就回答了计算机如何在给定的数中进行随意选取的问题。比如给了k个数,那么可以生成 [0,1] 上的均匀分布,之后利用(k-1)个分点把 [0,1] 分成k段,如果生成的随机数在第i个区间,那么就输出给定的数中得第i个数。

e) 局限性

当然我们会注意到使用逆变换法对F(x)的要求十分严格,通常需要没有跳跃间断点并且不存在一个区间[m,n]使得 F(x)\equiv C\quad\quad x\in[m,n]其中C为一个常数。当然对于F(x)也需要F^{-1}(x)是可以求出来的,这也是使用逆变换法的根本。

四、结语

这期讲了一些简单的例子,当然我们平常遇到的最常见的分布函数(比如正态分布),以及一些更为一般的分布函数计算机要怎么生成相应的分布呢?会在下一期里同大家分享~

上面内容只是作为科普,仅代表个人的一些理解,如果有不严谨或者错误的地方欢迎各位大佬指正!

标签:random,均匀分布,生成,第一期,分布,随机,随机数,科普
From: https://blog.csdn.net/weixin_63470844/article/details/142306348

相关文章

  • 科普向-计算机如何生成随机数?(第二期)
    一、引言在上期中,我们介绍了LCG和逆变换法,了解了区间上的均匀分布,多点分布以及一些简单分布函数的生成。本期我们将把情况推向更为一般的情况,讲介绍正态分布的生成,以及舍选法生成一般概率分布函数的分布。二、正态分布对于正态分布  的概率密度和分布函数:直接计算上述......
  • 《算法妙趣生,代码启征程》---第一期:双指针算法
      写这个系列是为了记录我所学习的模块,进行分析+总结+归纳。如果你也对算法感兴趣,可以跟着我一起学习总结,我会在我理解明白了的基础上,进行尽可能详细,通俗易懂的语言进行表达。目录 1.是什么2.题目解析(1)移动零 283.移动零-力扣(LeetCode)(2)复写零 1089.......
  • 科普文:软件架构数据库系列之【MySQL的sql_mode参数】
    概叙科普文:软件架构数据库系列之【MySQL解析器和优化器】-CSDN博客科普文:软件架构数据库系列之【MySQL查询优化器中的优化策略optimizer_switch】-CSDN博客科普文:软件架构数据库系列之【MySQL执行计划Extra梳理】-CSDN博客科普文:软件架构数据库系列之【MySQL控制查询优化器......
  • Windows10解决“远程计算机或设备将不接受连接检测到该设备或资源(Web 代理)未设置为
    问题表述:远程计算机或设备将不接受连接检测到检测到 该设备或资源(Web代理)未设置为接受端口“7897”上的连接。 在教室上课,因为各种原因改了网络设置,以致无法Web联网。但是微信和钉钉收发消息自如。网络诊断后报错这是我遇到的报错。解决方法:左下角“开始”“设置”......
  • 随机数生成工具,且偏差值累计和等于0【工程内业】
    随机数生成工具1、需求:工程内页,尤其是盖板钢筋、桩基钢筋的主筋间距,偏差值累加最好要解决0,这样才能保证资料的准确性。2、实现:暂时以VB和MFC实现,添加导出excel功能。3、界面截图:4、验证:4、下载地址:......
  • 00 概念科普|大模型是什么
    AI大模型全套学习资料“最先掌握AI的人,将会比较晚掌握AI的人有竞争优势”。这句话,放在计算机、互联网、移动互联网的开局时期,都是一样的道理。我在一线互联网企业工作十余年里,指导过不少同行后辈。帮助很多人得到了学习和成长。我意识到有很多经验和知识值得分享给大家,......
  • 科普文:软件架构数据库系列之【MySQL5.7和MySQL 8.0的差异】
    引言MySQL作为最常用的开源关系型数据库管理系统之一,一直在不断发展和改进。随着时间的推移,MySQL也经历了多个版本的演进,每个版本都带来了一系列重要的更新和改进。其中,MySQL5.7和MySQL8是两个备受关注的版本,它们之间存在一些关键的差异。本文将深入探讨这两个版本之间的主......
  • 科普文:软件架构数据库系列之【MySQL5.7的系统表梳理】
    概叙MySQL5.7的系统中包含了多个重要的系统表,这些表分布在不同的数据库中,提供了关于数据库结构、权限、性能等关键信息的访问。mysql>\s;--------------mysqlVer14.14Distrib5.7.21,forWin64(x86_64)Connectionid:3Currentdatabase:Currentuser:......
  • uniapp微信小程序的老年防诈科普及交流平台设计和实现 f254d可视化分析系统
    目录技术介绍具体实现截图微信开发者工具HBuilderXuniapp系统设计java类核心代码部分展示登录的业务流程的顺序是:可行性论证详细视频演示技术可行性系统测试系统安全性数据完整性实现思路系统实现源码获取技术介绍如今微信小程序有以下发展优势(1)无须下载,无须注......
  • 安装应用教程的科普
    正常来说我们拿到的电脑都是windows的系统,对于一线品牌比如联想,惠普都有自带的应用商店,很方便,不用动手这么多但是,一般我们的电脑都是纯净版,不带应用市场,就一个微软应用商店,这个微软应用商店网络时好时不好的,也不能改安装位置跟创建快捷键,这时候就用我们自带的Edge浏览器打开浏览......