算法基础09——随机化算法

随机化算法(randomized algorithm),是这样一种算法,在算法中使用了随机函数,且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下,即该算法在运行的过程中的某一步或某几步涉及一个随机决策,或者说其中的一个决策依赖于某种随机事件。

在我们的生活中,人们经常会去掷色子来看结果,投硬币来决定行动,这就牵涉到一个问题:随机。

计算机为我们提供好了随机方法(部分计算器也提供了),那么对于有些具有瑕疵的算法,如果配上随机化算法的话,又是可以得到意想不到的结果。

随机数发生器

蒙特卡罗法

  蒙特卡罗方法又称统计模拟法、随机抽样技术,是一种随机模拟方法,以概率和统计理论方法为基础的一种计算方法,是使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。将所求解的问题同一定的概率模型相联系,用电子计算机实现统计模拟或抽样,以获得问题的近似解。为象征性地表明这一方法的概率统计特征,数学家冯·诺依曼用闻名世界的赌城——蒙特卡罗命名 蒙特卡罗方法解题过程的主要步骤:
  1. 针对实际问题建立一个简单且便于实现的概率统计模型,使所求的量恰好是该模型的概率分布或数字特征。
  2. 对模型的随机变量建立抽样方法,在计算机上进行模拟测试,抽取足够多的随机数。
  3. 对模拟实验结果进行统计分析,给出所求解的“估计”。
  4. 必要时,改进模型以提高估计精度和减少实验费用,提高模拟效率。

U(0,1)随机数的产生

对随机系统进行模拟,便需要产生服从某种分布的一系列随机数。最常用、最基础的随机数是在(0,1)区间内均匀分布的随机数,最常用的两类数值计算方法是:乘同余法和混合同余法。

乘同余法:

其中,x0被称为种子,M是模,rn是(0,1)区间的随机数。

混合同余法:

其中,C是非负整数。
  这些随机数是具有周期性的,模拟参数的选择不同,产生的随机数质量也有所差异。更复杂的生成方法还有:

从U(0,1)到其它概率分布的随机数

离散型随机数的模拟

  设随机变量X的概率分布为:p(X=xi)=pi,分布函数有P(0)=0,P(n)=∑pi,设随机变量U~U(0,1)的均匀分布,则p(P(n−1)n(即pn)的概率与随机变量u落在P(n−1)与P(n)之间的概率相同。

如:离散随机变量X有分布律

x012
P(x)0.30.30.4

U是(0,1)的均匀分布,则有


这样得到的x便具有X的分布律。

连续型随机变量的模拟

常用的有两种方法:逆变换法和舍选法。

逆变换法:设随机变量Y的分布函数为F(y)是连续函数,而U是(0,1)上均匀分布的随机变量。另X=F−1(U),则X和Y具有相同的分布。
  
证明:由定义知,X的分布函数:

所以X和Y具有相同的分布。这样计算得F−1(∙),带入均匀分布的U,即可得到服从f(∙)的随机数Y。

例如:设X~U(a,b),则其分布函数为:


所以生成U(0,1)的随机数U,则a+(b−a)u便是来自U(a,b)的随机数。有些随机变量的累计分布函数不存在或者难以求出,即使存在,但计算困难,于是提出了
舍选法:要产生服从p(x)的随机数,设x的值域为[a,b],抽样过程如下:
1、已知随机分布Q(x)且x的取值区间也为[a,b],并要求c×Q(x)﹥p(x),xϵ[a,b],如图

2、从Q(x)中随机抽样得x,然后由U(0,c×Q(x∗))的均匀分布抽样得u。

3、接受或舍弃取样值x,如果u>P(x)舍弃该值;返回上一步,否则接受。几何解释如下:

常数c的选取:c应该尽可能地小,因为抽样效率与c成反比;一般取c=maxP(x)/Q(x),xϵ[a,b]。这里的Q(x)可以取均匀分布,这样由第二种中两个均匀分布便能得到其他任意分布的模拟抽样。

正态随机数的生成

除了上面的反函数法和舍选法,正态随机数还可以根据中心极限定理和Box Muller(坐标变换法)得到。

中心极限定理:如果随机变量序列 X1,X2,...,Xn,..独立同分布,并且具有有限的数学期望和方差E(Zi)=μ,D(Xi)=σ2(i=1,2,...),则对于一切x∈R有

也就是说,当n个独立同分布的变量和,服从N(nμ,nσ2)的正态分布(n足够大时)。
设n个独立同分布的随机变量U1,U2,...,Un,它们服从U(0,1)的均匀分布,那么

渐近服从正态分布N(0,1)。

Box Muller方法,设(X,Y)是一对相互独立的服从正态分布N(0,1)的随机变量,则有概率密度函数:

令x=Rcosθ,y=Rsinθ,其中x∈(0,2π),则R有分布函数:

令FR( r )=1−e−r2/2,则分布函数的反函数得:

如果U1服从均匀分布U(0,1),则R可由模拟生成((1−U1)也为均匀分布,可被U1代替)。令θ为2πU2,U2服从均匀分布U(0,1)。得:

  X和Y均服从正态分布。用Box Muller方法来生成服从正态分布的随机数是十分快捷方便的。

更新时间:2020-02-17 15:28:49

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础09随机化算法
最后更新:2020-02-17 15:28:49

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×