当前位置：文档之家 › 第四章 随机数发生器和随机变量产生

第四章 随机数发生器和随机变量产生

  • 格式：ppt
  • 大小：1.29 MB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

第四章随机数产生原理

第四章随机数产生原理
2、管理科学的系统仿真研究
管理科学中的系统仿真研究，如服务系统、库存系统等。其共性就 是研究的对象是随机数，如顾客到达时间一般是一个服从指数分布 的随机数，而服务时间也可以看成是服从某种分布的随机数，当一 个系统是多队多服务体系时，问题就变的相当复杂了。我们很难用 数学的解析式来表达。这时Monte-Carlo方法也是有利的武器。对 于 这 个 领 域 的 已 有 各 种 比 较 成 熟 的 专 用 软 件 如 GPSS 、 SIMULATION等可以使用。
从算法上我们知道公式是递推的，因此一般的随机发生器程 序都要预先赋初值，这种初值为种（Seed），有些统计软件 如SPSS要求用户给出Seed.
以均匀分布（0，1）随机变量R变换成的随机变量。以r,ε,u, 分别表示 (0,1) 均匀分布,指数分布，N(0,1) 标准正态分布。 其他常见的分布如卡方分布、F分布等的抽样方法见表4.3.1。
的坐标。
显然末端距随链的不同而不 同，即为随机变量。
2
红链的末端距
1 0
绿链的末端距
二、伪随机数产生原理
前面Monte-Carlo方法的例子是以高质量的随机数为 基础的。通过完全的随机抽样或调查可以产生随机序 列。
x1, x2 ,, xn
当我们用Monte-Carlo方法研究一个实际问题时，我 们需要快速地获得大量的随机数。用计算机产生这样 的随机数是非常方便的，用数学方法在计算机上产生 的随机数称为伪随机数。
E[ f ( x)] f ( x)dx
即是f（x）的均值，对于均值我们有一个很好的估计，即
N
f (xi )
Eˆ [ f ( x)] i1 N
【例4.1.1】 用Monte-Carlo 对 1 x2dx 积分 0

第4讲 随机数的生成及随机变量抽样

第4讲 随机数的生成及随机变量抽样
P ( X = n) = 1 6
v
选取均匀随机数u，如
n −1 n <u≤ 6 6
v
则
XF = n
PDF 文件使用 "pdfFactory Pro" 试用版本创建
u=unifrnd(0,1,1,10000);Randnum=zeros(1,10000); for i=1:10000 if u(i)<=1/6 Randnum(i)=1; else if u(i)<=2/6 Randnum(i)=2; else if u(i)<=3/6 Randnum(i)=3; else if u(i)<=4/6 Randnum(i)=4; else if u(i)<=5/6 Randnum(i)=5; else Randnum(i)=6; end end end end end end cdfplot(Randnum)
= P( X ≤ u, Y ≤ u ) = P( X ≤ u ) P(Y ≤ u )
= FX (u ) FY (u ) FN (v) = P(min{ X , Y } ≤ v) = 1 − P (min{X , Y } > v)
= 1 − P ( X > v, Y > v) = 1 − P ( X > v) P (Y > v)
由 U (0 ,1)抽取 u ， −1 (u ) 计算 x = F
v
v
v
PDF 文件使用 "pdfFactory Pro" 试用版本创建
v
v
1) 离散型分布的直接抽样方法
xi < x
对于任意离散型分布： F ( x) =
∑ pi
v

4_随机数与随机变量的生成

4_随机数与随机变量的生成
重复步骤①~②，即可生成分布函数F(x)的随机变量的数列。
28
4.4.4 舍选法
反变换法、卷积法、组合法都有一个共同的特点，即直接 面向分布函数，因而称为直接法，它们以反变换法为基础。然 而，当反变换法难于使用（例如随机变量的分布函数不存在封 闭形式等）或者效率不高时，就需要使用非直接的方法。舍选 法就是其中的主要方法之一。该方法由于具有抽样灵活、计算 简单、使用方便等特点而得到了较为广泛的应用。
2
4.1 随机数的生成及其性质
• 目前，在用计算机生成随机数的方法中，一类使用最广、发
展也较快的方法是数学方法。 • 按照一定的算法（递推公式）来生成“随机”数列（也
称为随机数流）的方法。用户只需任意给定一个初始值 （或称为种子值），当调用该算法时，就可以按确定的 关系计算出下一个“随机”数。随后，以这个新生成的 “随机”数作为第二个种子值，再计算出下一个新的随 机数。多次调用该算法即可生成一个“随机”数的序列。
u
1 n
n
ui
i 1
s2
1n n 1 i1
ui u
2
于是有
Eu 1
2
Varu 1
12n
Es2 1 12
Vars2 1 180n
渐进服从标准正态分布N(0, 1)。
11
于是统计量：
v1
u
Eu Varu
12nu 1 2
v2
s2 E s2 Var s2
180n s2 1 12
组合发生器的不足之处在于，由于需要产生两个或多个基础 的随机数位并执行一些辅助操作，才能得到一个随机数，因此 该方法的计算速度相对较慢一些，成本比较高
9
4.3 随机数发生器的性能检验

第4章 随机数的产生

第4章 随机数的产生

重复产生两个相同的真随机数数列。 ●真随机数只能用某些随机物理过程来产生。 ●如果采用随机物理过程来产生真随机数，理 论上不存在什么问题。但在实际应用时，要做出 速度很快，而又准确的随机数物理过程产生器是 非常困难的。
准随机数：
准随机数概念是来自如下的事实： 要实现严格数学意义上的随机数，在理 论上虽然可行，但在实际中却是不可行 的，也没有这个必要。关键是要保证 “随机”数数列具有能产生出所需要的 结果的必要特性。

步骤3 计算D=max(D+,D-) 步骤4 对给定的显著水平α和样本大小 N， 查表确定临界值D 步骤5 若样本的统计量D大于临界值Dα， 则虚假设被拒绝。若D ≤Dα，则推断实际 分布与均分布之间未检测到差异。
例：假设产生了5个随机数：0.44,0.81, 0.14,0.05,0.93,使用科尔莫戈罗夫·斯 米尔诺夫检验其均匀性,α=0.05.
[0,1]均匀分布的随机数可以用来生成其它分 布的随机数。
[0,1]均匀分布概率密度函数
1 f ( x) 0
1
0 x 1
其他
f(x) 1
x2 1 1 E ( R) xdx 0 2 0 2
V ( R)
1 3 2 2
0
1
x
x 1 1 2 1 1 1 x dx [ E ( R)] ( ) 3 0 2 3 4 12
例如，在大多数模拟研究中，模拟 事例被认为是相互独立的，而这些事例 的顺序则似乎并不重要。因而我们可以 在大多数运算中，放心地置随机性的概 念于不顾。同样，我们也可以不考虑对 某些分布均匀性的涨落程度。 事实上在许多情况下，超均匀的分 布比真随机数的均匀分布更合乎实际需 要。
伪随机数：

第四章随机数产生原理

第四章随机数产生原理

第四章随机数产生原理随机数是在计算机科学领域非常重要的一个概念，它广泛应用于密码学、模拟和统计等领域。

在计算机中，随机数是指一系列看似无序的数字，其生成过程是不可预测的，即无法通过已有的信息来确定接下来生成的数值。

随机数是通过随机数生成器产生的，随机数生成器是一个能够生成随机数的算法或设备。

在计算机中，常见的随机数生成器包括伪随机数生成器和真随机数生成器。

伪随机数生成器（PRNG）是指通过确定性算法生成的数列，它并非真正的随机数，而是看似随机的数列。

PRNG的生成过程是可复制的，即通过相同的种子可以重现相同的随机数序列。

PRNG的基本原理是利用一个随机数种子作为输入，然后通过一系列算法对种子进行变换，生成一个数列作为输出。

PRNG的核心思想是通过在高维空间中的漫游来构造一个看似随机的数列。

PRNG的算法可以基于线性同余方法、拉格朗日插值、循环移位寄存器或混沌系统等。

线性同余法是一种简单而常用的随机数生成算法，它的基本原理是通过线性代数的方法，通过对当前的随机数X[i]进行线性变换，得到下一个随机数X[i+1]。

具体来说，线性同余法的生成过程可以描述为：X[i+1] = (a * X[i] + c) mod m其中X[i]表示当前的随机数，a和c是常数，m是模数。

此时，随机数序列X[i]的周期为m，当X[i]的值回归到初始值时，即表示一个周期的结束。

然而，由于PRNG是通过确定性算法生成的，因此在理论上是可以通过逆向计算来推断出随机数生成算法的种子和输出序列。

这就意味着PRNG的随机性是有一定局限性的，也就是说它无法提供真正的随机性。

为了解决PRNG的局限性，人们提出了真随机数生成器（TRNG）。

TRNG利用物理过程和环境的噪声等随机性源生成随机数。

TRNG的基本原理是通过使用物理过程和环境的不可预测性来生成随机数，这些过程和环境包括放射性衰变、电子噪声、热噪声等。

TRNG的生成过程是不可预测的，并且不会受到外界干扰的影响。

3、随机数与随机变量

3、随机数与随机变量

3、随机数与随机变量3.1随机数的生成与检验3.1.1 随机数与伪随机数 仿真中最基本的随机数：U(0 , 1)⎩⎨⎧≤≤=其它，,0101)(x x f +其它各种分布的随机数均可通过对U(0,1)随机数的变换得到。

++习惯上，称其它分布的随机数为随机变量。

随机数的产生方法手工机械及电子装置数学方法+由数学方法生成的随机数是按一定算法递推生成的，由于在已知初值的情况下，其每一个所生成的数均是可预知的，故被称为伪随机数。

今后在不引起混淆的情况下，也简称之为随机数。

++现代仿真中所用的随机数均为伪随机数。

3.1.2随机数发生器所谓随机数发生器即为用数学方法产生随机数的递推公式。

优良随机数发生器的品性总体均匀，样本随机，序列独立；足够长的周期；生成速度快，占用内存少，完全可重复。

1 早期随机数发生器平方取中随机数发生器n n n x u x x 10=⎢⎣⎡=x 0为2k 位非负整数。

缺点最终退化2 线性同余随机数发生器应用最广泛的随机数发生器之一，简称generator)x u ax x n n n /(==m 为模数，初值x 0均为非负整数。

称数列x n 重复值之间的最短长度为记为T 。

若T =m c ≠0的LCG 为乘同余发生器。

混合同余发生器的“满周期定理”若满足下列三个条件，则混合同余发生器可达到满周期：（1）c与m互素（可同时整除c与m的整数只有1）；（2）对任意素数q，若q能整除m，则q也能整除a-1；（3）若4能整除m，则4也能整除a-1。

为延长随机数发生器的周期，通常取m=2b，b为所用计算机的字长减1。

优点随机数周期尽可能大；便于参数选取（能整除m的素数只有2）；可利用“整数溢出”简化计算。

参数选取的基本原则m = 2ba= 4α+1c= 2β+1还有其他一些需考虑的因素，如怎样消除相关性，这一般需要选取较大的a（a<m），且a在二进制表示中，0，1无明显规律性。

一种在32x n= ( 314159269 u n= x n-1/ 231乘同余随机数发生器无法达到满周期，但可达到最大周期。

第4讲随机数的生成及随机变量抽样市公开课一等奖省赛课微课金奖PPT课件


并画经验分布函数曲线。
生成1行1000列21—30上离散均匀分布随机数；
并画经验分布函数曲线。
生成1行1000列501—510上离散均匀分布随机
数。 并画经验分布函数曲线。
function Random=liti42(mm) Random=unifrnd(0,1,1,mm); for i=1:mm
cdfplot(liti42(1000)), cdfplot(liti42(1000)+20), cdfplot(liti42(1000)+500)
第34页
总之 假如 X 密度函数f(x)难于抽样，而X关于Y条
件密度函数f2(x|y)以及Y分布F1(y)均易于抽样， 则X随机数能够下产生：
由Y的分布F1 y 抽取YF1，
由条件分布f2 x YF1 抽取X f2 ( x|YF1 )
能够证实由此得到Xf2 (x|YF)服从f(x) 。
第35页
❖ 定理 设随机变量U服从(0,1)上均匀分布，则 X=F-1(U)分布函数为F(x) 。
❖ 所以，要产生来自F(x)随机数，只要先产生来 自U(0,1)随机数，然后计算F-1(u) 即可。
❖ 其步骤为
由U 0,1抽取u， 计算x F 1u
第6页
v 1) 离散型分布直接抽样方法
❖ 对于任意离散型分布： F (x) pi
RandY
F
1 X
(1
(1
u
)
1 n
)
1
1 (1 u) n
生成n=201行10000列随机数，并画经验分布函 数曲线。
第28页
n=20 Randnum=1-(1-unifrnd(0,1,1,10000)).^(1/n); cdfplot(Randnum)

第四章 随机数发生器和随机变量产生

10
10
2 xn 1 上式中 k mod 10 2 k 的含义为： 10 2 xn 进行模为 102 k 的求余运算。我们看下面 1 对 k 10 的例子：
N mod M
表示对N 进行模为 M 的求余运算，其含义为：
N N mod M N M M
x0 76 5776
2 mod 10 2
mod 10
577 mod 100 77
x1 77
x 77 ） 1 12
（或者直接从5776取中取中间的两个数得
4-3 常用的随机数发生器
则
u1 x1 /10 x1 /100 0.77
2
2 2 5929 2 由于 x12 77
则
u2 x3 / 10000 0.9825
16
依次取下去，我们可以得到如下表：
4-3 常用的随机数发生器
n 1 2 3 4 5 6 …
xn1 xn
19267743 09982533 26301525
29622375 18762345 47437929 …
xn1
2677 0. 2677
例如：
(1)
45 45 mod 6 45 6 6 45 7 6 45 42 3 45 45 mod 9 45 9 9 45 5 9 45 45 0
(2)
10
u n 的计算表达式为：
xn / 10
• 简单、直观、易于实现；
• 数据内部特性难以控制，容易出现退化等 问题。
26
目前常用的ห้องสมุดไป่ตู้法——线性同余法
• 混和线性同余法

随机数发生器与随机函数PPT文档共25页

45、法律的制定是为了保证每一个人 自由发 挥自己 的才能 ，而不 是为了 束缚他 的才能 。—— 罗伯斯 庇尔
31、只有永远躺在泥坑里的人，才不会再掉进坑里。——黑格尔 32、希望的灯一旦熄灭，生活刹那间变成了一片黑暗。——普列姆昌德 33、希望是人生的乳母。——科策布 34、形成天才的决定因素应该是勤奋。——郭沫若 35、学到很多东西的诀窍，就是一下子不要学很多。——洛克
பைடு நூலகம்
随机数发生器与随机函数
41、实际上，我们想要的不是针对犯 罪的法 律，而 是针对 疯狂的 法律。 ——马 克·吐温 42、法律的力量应当跟随着公民，就 像影子 跟随着 身体一 样。— —贝卡 利亚 43、法律和制度必须跟上人类思想进 步。— —杰弗 逊 44、人类受制于法律，法律受制于情 理。— —托·富 勒

随机变量产生的原理

随机变量产生的原理12.3 随机变量产生的原理仿真对产生随机变量的方法的要求:准确性:即由这种方法产生的随机变量应准确地具有所要求的分布;快速性:离散事件仿真一次运行往往需要产生几万甚至几十万个随机变量。

介绍四类最常用的产生随机变量的方法:反变换法，组合法，卷积法及舍选法。

1、反变换法----以概率积分变换定理为基础(1)连续随机变量的反变换法:uFx()设随机变量x的分布函数为，先产生在[0，1区]间上均匀分布的独立随机变量，由反分,1Fu()布函数得到的值即为所需要的随机变量x:,1xFu,()原理说明:Fx(), 随机变量概率分布函数的取值范围为[0，1];Fx(), 以在[0，1]上均匀分布的独立随机变量作为的取值规律; 图12.1 连续分布函数的反变换法原理1,Fx,, 落在内的样本个数的概率就是;,,Fx/,x, 从而随机变量x在区间内出现的概率密度函数的平均值为;dFdx/,x, 当趋于0时，其概率密度函数就等于，即符合原来给定的密度分布函数，满足正确性要求。

例12.1 设随机变量x是[a,b]上均匀分布的随机变量，即:0xa,,1,,xa,,axb,,Fx(),axb,,fx(),,,ba,xfx()概率密度函数: 由可得到的分布函数: ba,,,0其它,1xb,,u, 用随机数发生器产生U(0，1)随机变量xa,uFx,,()()axb,,, 令 ba,xabau,，,(), 可得:(2)离散随机变量的反变换法:px()px()xxx,,,？xpx()设离散随机变量分别以概率，，…，取值，其中n212n12npx(),101,,px()i,，且。

ii,1px()px()px(), 将[0，1]区间按，，…，的值分成n个子区间; 12n, 产生在[0，1]区间上均匀分布的独立的随机数u; , 根据u的值落在何区间，相应区间对应的随机变量就是x所需要的随机变量。

i实现办法:x, 先要将按从小到大的顺序进行排序，即i图12.2 离散分布的反变换法xxx,,,？ 12n, 得到分布函数子区间的分界点n,1n，，((),()()],,(),()pxpxpxpxpx，？,,0,()px112ii，,,, ， 1,,i,1i,1，，xx,u~U(0,1)upx,(), 由随机数发生器产生的，若，则令，若11pxupxpx()()(),,，xx,,,？，则令依次下去。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
只要任意给定一个初始值（也称种子值），当调用该算 法时，就可以按确定的关系计算出下一个“随机”数， 然后，以新生成的随机数作为第二个种子值，再计算出 新的随机数。多次调用该算法就可以生成一个“随机数”
序列。
4
4-1 随机数的生成及本质
这种用算法生成的随机数，只要给定初始的 种子值，则以后所生成的“随机”数都是确定的
2
4-1 随机数的生成及本质
关于随机数生成方法的研究已有很长的历史。最 早的随机数是用手工实现的，如抽签、发纸牌、从罐 子中摸取带数字的球等方法。其中，有些方法至今仍 然还采用。 随着Monte-Carlo方法的出现，20世纪初出现了 生成随机数的机械装置和电子装置，如抽奖机等。
但是机械装置和电子装置不能重复生成与原来完全
7
4-3 常用的随机数发生器
生成随机数的方法经历了一段漫长的发展过程，
下面介绍几种有代表性的算法，主要有：
（1）早期的随机数发生器：平方取中随机数发
生器、乘积取中随机数发生器、常数乘子法、斐
波那契法（Fibonacci）等； （2）线性同余随机数发生器：混合同余随机 数发生器、乘同余随机数发生器；
例如：
(1)
45 45 mod 6 45 6 6 45 7 6 45 42 3 45 45 mod 9 45 9 9 45 5 9 45 45 0
(2)
10
u n 的计算表达式为：
xn / 10
8
4-3 常用的随机数发生器
1.平方取中随机数发生器
由冯.纽曼于1940年提出的，基本原理是：将一个
N位数平方后，取中间N位数为第一个随机数，然后再 平方取中间N位数为第二个随机数，递推公式如下： 2 xn 2k 1 x mod 10 n x2 k 2k n 110 x mod 10 n k /102 k u 10 x n 2k n x n / 10 u n 初始值为 x0 (正整数), k为x0的位数的一半 初始值为 x0 (正整数), k为x0的位数的一半 (1) 5.8 5 2 2 x n 1 x n 1 (2) 5.1 5 其中， 的整数部分，例如： k 表示取 k 9 10 Nhomakorabea10
2 xn 1 上式中 k mod 10 2 k 的含义为： 10 2 xn 进行模为 102 k 的求余运算。我们看下面 1 对 k 10 的例子：
N mod M
表示对N 进行模为 M 的求余运算，其含义为：
N N mod M N M M
数值，从本质上说这并不具有真正的随机性，因
此称这种方法为伪随机数PRN（Pseudo Random Number）。
5
4-2 随机数发生器的概念
• • 用数学方法生成随机数所依赖的算法和程序就 称为随机数发生器。 仿真模拟钟所用到各类随机变量都是以随机数 发生器产生的[0, 1)间均匀分布随机数为基础而 得来的。
第4章 随机数发生器及随机变量的产生
本章主要内容:
– 1. 随机数的生成和本质 – 2. 随机数发生器的概念 – 3. 常用的随机数发生器 – 4. 随机变量的产生方法
1
第4章 随机数发生器及随机变量的产生
本章重点:
• 1.计算机产生的随机数的本质 • 2.各类方法（特别是平方取中法 和线性同余法）产生随机数的原 理及其特点 • 3.拟转换法生成随机变量 本章难点: 逆转换法生成随机变量的原理
相同的随机数，对计算结果无法进行检查，并且生 成过程比较复杂。因此，它们未能得到进一步推广。
3
4-1 随机数的生成及本质
目前，在用计算机生成随机数的方法中，一类使
用最广、发展较快的方法是数学方法，其特点是占用
内存少、速度快并且便于检查。 用数学方法生成随机数是指按照一定的算法（递推
公式），来生成“随机”数列（也称随机数流）。我们
x0 76 5776
2 mod 10 2
mod 10
577 mod 100 77
x1 77
x 77 ） 1 12
（或者直接从5776取中取中间的两个数得
4-3 常用的随机数发生器
则
u1 x1 /10 x1 /100 0.77
2
2 2 5929 2 由于 x12 77
如果精心设计算法，就可以生成具有真正随
机数的统计性质的伪随机数。通常，只要所生成 的伪随机数能通过一系列统计检验（如独立性、 均匀性）就可以把它们作为真正的随机数使用。
6
4-2 随机数发生器的概念
一个优良的随机数发生器应具有以下 特征：
1. 产生的随机数必须是[0,1)之间均匀分布的 2. 产生的随机数必须是独立同分布 (IID) 3. 可产生相同的数列, 又可产生不同的数列 4. 数列具有足够长的（重复）周期 5. 产生随机数的速度快 6. 占有内存小
u n 为[0，1)区间上的数。
2k
初始值x0为 2k 位非负整数，关于k的取值一般最小取2， 为方便有时也取1。
11
4-3 常用的随机数发生器
例4.1 取k=1， x0 =76，求由“平方取中法”可 以得到如下随机数。 2 x0 2 76 2 5776 解： 2
2 x0 76 2 2 取 x1 mod 10 2 2 x 76 10 10 2 0 x1 mod 10 10 10 5776 mod 100 10 5776 mod 577 mod 100 100 10 77
取 则
x2 92
x1 77 5929
u2 x2 / 1002 0.92
x 92
u2 x2 /100 0.92
依次取下去，我们可以得到如下表：
13
4-3 常用的随机数发生器