第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) Monte Carlo模拟 第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) 3.5 舍选抽样法 (acceptance-rejection sampling) 2019/5/22 3.5 舍选抽样法

3.5 舍选抽样法（acceptance-rejection sampling) 直接抽样法的困难： 许多随机变量的累积分布函数无法用解析函数给出; 有些随机变量的累积分布函数的反函数不存在或难以求出； 即使反函数存在，但计算困难 舍选抽样法(von Neumann)： 抽取随机变量x的一个随机序列xi, i=1,2,…, 按一定的舍选规则从中选出一个子序列，使其满足给定的概率分布. 2019/5/22 3.5 舍选抽样法

第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) Monte Carlo模拟 第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) 3.5 舍选抽样法 (acceptance-rejection sampling) 3.5.1 简单舍选抽样法 3.5.2 改进的舍选抽样法 3.5.3 典型的例子 2019/5/22 3.5 舍选抽样法

Von Neumann rejection method or Hit-and-miss method 3.5.1 简单舍选抽样法 Von Neumann rejection method or Hit-and-miss method 设随机变量x的取值区间为x[a,b], 其概率密度函数f(x)有界，即 舍选法抽样步骤： 抽取r1,r2 U[0,1] x = a + (b-a)r1 y = cr2 y  f(x) X = x  > 产生[a, b]区间内均匀分布的随机数x: x = (b-a)r1+a, r1 U[0, 1]; 产生[0,c]区间内均匀分布的随机数y: y = cr2, r2 U[0,1]; 当y  f(x)时，接受x为所需的随机数，否则，返回到第一步重新抽取一对(x,y). 2019/5/22 3.5 舍选抽样法

3.5.1 简单舍选抽样法 几何解释: e f c f(x) x a b 在二维图上，随机选取位于矩形abef内的点[x,y]； 选取位于曲线 f(x)下的那些点，则这些点将服从概率密度为f(x)的分布 2019/5/22 3.5 舍选抽样法

3.5.1 简单舍选抽样法 证明: e f c f(x) x a d b x和y的概率密度函数分别为 联合概率密度函数为 即d的概率函数为f(x) 2019/5/22 3.5 舍选抽样法

3.5.1 简单舍选抽样法 抽样效率: a b x f(x) c e f d 如果选出某特定分布的一个随机数平均地需要n个随机数r1 U[0, 1]，则定义为抽样效率 a b x f(x) c e f d 对舍选抽样法：欲产生m个随机变量x的值需产生n对(x,y)，显然，m  n 2019/5/22 3.5 舍选抽样法

第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) Monte Carlo模拟 第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) 3.5 舍选抽样法 (acceptance-rejection sampling) 简单舍选抽样法 改进的舍选抽样法 典型的例子 2019/5/22 3.5 舍选抽样法

构造一个新的概率密度函数g(x)，使它的形状接近f(x), 且有 3.5.2 改进的舍选抽样法 简单舍选抽样法的问题： 如果f(x)曲线下的面积占矩形面积的比例很小，则抽样效率很低，这是因为随机数x和y是在区间[a, b]和[0, c]内均匀分布，所产生的大部分投点不会落在f(x)曲线下 x c f(x) 改进方法： 构造一个新的概率密度函数g(x)，使它的形状接近f(x), 且有 式中Cg为常数，而g(x)的抽样相对比较容易。 Cgg(x) 改进的舍选抽样法 2019/5/22 3.5 舍选抽样法

产生分布为g(x) 的随机数x ，x[a,b]; 3.5.2 改进的舍选抽样法 抽样方法： 1. 产生两个随机数 产生分布为g(x) 的随机数x ，x[a,b]; 产生[0, Cg g(x)] 区间上均匀分布的随机数y，y= Cgg (x) , U[0,1]. 2. 接收或舍弃取样值 x. 如果 y > f(x)，舍弃，返回到1,重复上述过程; 否则，接受; 2019/5/22 3.5 舍选抽样法

3.5.2 改进的舍选抽样法 几何解释: c Cgg(x) f(x) x 在二维图上，随机选取位于曲线Cgg(x)下的点[x,y]； 选取位于曲线 f(x)下的那些点，则这些点将服从概率密度为f(x)的分布 2019/5/22 3.5 舍选抽样法

3.5.2 改进的舍选抽样法 证明: c Cgg(x) f(x) x d x和y的概率密度函数分别为 联合概率密度函数为 即d的概率函数为f(x) 2019/5/22 3.5 舍选抽样法

常数Cg应尽可能地小,因为抽样效率与Cg成反比; Cg=max{f(x)/g(x)}, x [a,b] 3.5.2 改进的舍选抽样法 抽样效率: c f(x) Cgg(x) 常数Cg的选取 x 常数Cg应尽可能地小,因为抽样效率与Cg成反比; Cg=max{f(x)/g(x)}, x [a,b] 2019/5/22 3.5 舍选抽样法

第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) Monte Carlo模拟 第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions) 3.5 舍选抽样法 (acceptance-rejection sampling) 简单舍选抽样法 改进的舍选抽样法 典型的例子 2019/5/22 3.5 舍选抽样法

无法用直接抽样法,累积分布函数无解析表达式 3.5.3 典型的例子 例1:标准正态分布的抽样,x[-a,a] 无法用直接抽样法,累积分布函数无解析表达式 Breit-wigner or Cauchy分布 2019/5/22 3.5 舍选抽样法

计算f(x), 如果u<= f(x), 接受x 3.5.3 典型的例子 由g(x)抽取x  直接抽样法 抽取u 计算f(x), 如果u<= f(x), 接受x 2019/5/22 3.5 舍选抽样法

例2：利用舍选法产生随机数C=cos, S=sin,其中为[0, 2]区间内均匀分布的随机数 3.5.3 典型的例子 例2：利用舍选法产生随机数C=cos, S=sin,其中为[0, 2]区间内均匀分布的随机数 方法1：先产生[0, 2]间均匀分布的随机数：  = 2 r， rU[0,1], 然后直接计算C和S  因需要计算三角函数，故此方法运算速度慢 方法2：利用舍选法可避免三角函数运算 令A和B为单位圆内直角三角形的两个边，则有 A B /2 2019/5/22 3.5 舍选抽样法

因此，只要产生单位圆内的随机坐标A和B,就可用代数运算求出C和S,算法为 3.5.3 典型的例子 因此，只要产生单位圆内的随机坐标A和B,就可用代数运算求出C和S,算法为 产生两个[0,1]区间上均匀分布的随机数u1和u2; 令v1=2u1-1, v2=u2,则v1U[-1,1],v2U[0,1]; 计算r2=v12+v22, 如果r2 > 1,转到1，重新产生； 令A=v1, B=v2, 计算C和S 2019/5/22 3.5 舍选抽样法