(2)对于1=12,…,如果有P(n) CPo(n,) ≥U1,就保留n1,否则就舍弃n, 由命题2.8,所有这样保留下来的那些n,们就成为一系列独立的p(x)随机数(当然个数会 比n小很多)这种取舍方法称为 Von Neuman取舍原则 取舍原则可以改良为 如果p(x)=y·h(x),只要存在C,使h(x)≤C·p0(x),那么我们可以在取舍原则中 用h(x)代替p(x),得到p(x)随机数.具体为:独立地生成n个独立的P0(x)随机数 h,…,n与n个与之独立的独立UO随机数U1,…,Un,如果n)2U,则保留 0() 否则舍弃n,那么所有保留下的是相互独立的p(x)随机数 证明只需注意到这时有p()y:C.p(x),并且一P(x)=如()即可 yCPo(x) Cp(x) 注1一般地γ需通过 1=[h(x)dx计算,其中的积分不易计算但是上面的事实说 明不必计算γ,即可以忽视这个常数因子.这就使取舍原则变得非常好用.取舍原则的优 点是简单易行,可以适用于非常复杂的分布 注2如果p(x)只在有限区间[a,b上不等于零,而且有界,那么P0(x)就可取均匀分 布U[a,b];如果p(x)只在右半直线不等于零,那么指数分布就可以是p0(x)的一个选择 如果p(x)在实直线上不等于零,且分布密度的尾部不大,则正态分布就可以是P0(x)的一 个选择,如果p(x)在实直线上不等于零,且分布密度的尾部较大(重尾分布),则t分布 就可以是P(x)的一个选择,如果p(x)具有多个峰,则混合正态分布或混合指数分布就可 以是p0(x)的一个选择可见适当精心地选取P0(x)是使计算省时的关键 注3原则上取舍原则也适用于离散分布和多维密度,但是在多维密度的情形,Po(x) 的选取并不容易 注4样本生成的一个重要应用,就是对于函数的一些积分,用 Monte Carlo方法(随机 模拟算法)给出估计·直观地可以猜测,采用的随机数的密度P。(x)的形状与被积函数越像, 则估计的方差会越小,即效果越好.这种取样法称为重要度采样( Impotance Samling)(确切 的定义与方差的最小性证明可参见第8章)37 (2) 对于i = 1,2,L, 如果有 i i i U Cp p ³ ( ) ( ) 0 h h , 就保留hi , 否则就舍弃hi 。 由命题 2.８, 所有这样保留下来的那些hi 们就成为一系列独立的 p( x) 随机数(当然个数会 比n 小很多). 这种取舍方法称为 Von Neuman 取舍原则. 取舍原则可以改良为： 如果 p(x) = g × h(x) , 只要存在C ，使 ( ) ( ) h x £ C × p0 x , 那么我们可以在取舍原则中 用 h(x) 代替 p( x) ，得到 p( x) 随机数． 具体为：独立地生成n 个独立的 ( ) 0 p x 随机数 h hn , , 1 L 与n 个与之独立的独立U[0,1] 随机数U U n , , 1 L ，如果 i i i U Cp h ³ ( ) ( ) 0 h h , 则保留hi , 否则舍弃hi , 那么所有保留下的是相互独立的 p( x) 随机数. 证明 只需注意到这时有 ( ) ( ) p x £ g ×C × p0 x , 并且 = × ( ) ( ) 0 Cp x p x g ( ) ( ) 0 Cp x h x 即可． 注１ 一般地g 需通过 ò = h(x)dx 1 g 计算, 其中的积分不易计算. 但是上面的事实说 明不必计算g , 即可以忽视这个常数因子．这就使取舍原则变得非常好用．取舍原则的优 点是简单易行, 可以适用于非常复杂的分布. 注２ 如果 p( x) 只在有限区间[a, b]上不等于零, 而且有界, 那么 ( ) 0 p x 就可取均匀分 布 U[a,b] ; 如果 p( x) 只在右半直线不等于零, 那么指数分布就可以是 ( ) 0 p x 的一个选择; 如果 p( x) 在实直线上不等于零，且分布密度的尾部不大, 则正态分布就可以是 ( ) 0 p x 的一 个选择; 如果 p( x) 在实直线上不等于零，且分布密度的尾部较大（重尾分布）, 则t 分布 就可以是 ( ) 0 p x 的一个选择; 如果 p( x) 具有多个峰, 则混合正态分布或混合指数分布就可 以是 ( ) 0 p x 的一个选择. 可见适当精心地选取 ( ) 0 p x 是使计算省时的关键. 注３ 原则上取舍原则也适用于离散分布和多维密度，但是在多维密度的情形， ( ) 0 p x 的选取并不容易． 注４ 样本生成的一个重要应用, 就是对于函数的一些积分, 用 Monte Carlo 方法(随机 模拟算法)给出估计． 直观地可以猜测, 采用的随机数的密度 ( ) 0 p x 的形状与被积函数越像, 则估计的方差会越小, 即效果越好. 这种取样法称为重要度采样 (Impotance Samling)(确切 的定义与方差的最小性证明可参见第 8 章)