《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第2章 随机样本生成法

龚光鲁,钱敏平著应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社,2003 第2章随机样本生成法 1一维随机数 随机变量(或随机向量)的样本简称为随机数.由于在统计中常用的是独立样本列, 所以我们不妨假设随机数之间都是独立的.生成随机数的方法,也称为随机数的取样法 (Sampling ) 1.1均匀随机变量的计算机模拟 定义2.1在,1上均匀分布的随机变量的独立样本称为均匀随机数(U[0,随机数) 在计算机上产生的称之为”伪随机数”的数列,是一种具有非常长周期的,且能通过数理 统计中的独立性与均匀性假设检验的数列.实践证明伪随机数是均匀随机数的一种可行的 近似这种伪随机数虽然并不是独立同分布的U[O]随机变量的样本,而是在[0,1中取值 的周期数列,但是由于它可以像均匀随机数一样地通过数理统计中的独立性与均匀性假设 检验,而且它的周期非常长,以至在计算机实际运算过程中不会出现重复,所以在实际计算 中它能很好地替代均匀随机数 最普遍用以产生伪随机数的方法是同余法.典型的例子如下 ),y=1,xn=yn2-36(周期约为21010) n+1 5y, (mo ),y=1, (周期约为102) yn2=yn+yn(mod2),y=0,y1=1,x,n=yn2-(周期约为104) (关于伪随机数,可参见:现代数学手册,随机数学卷,第10篇,孙嘉阳,石坚,丛树 铮,徐映波编蒙特卡罗法.华中科技大学出版社,2000年). 1.2分布函数F(x)的随机数 命题2.2(反函数方法)分布函数为F(x)的独立随机变量列的样本,称为F(x)随机 数若F(x)严格单调递增,ξ是均匀随机数,则F()是F(x)随机数,其中F-为F的反 函数 证明P(F(5)≤x)=P(5≤F(x)=F(x) 命题2.3设随机变量ξ只取有限个值,其分布为 把[0,1 分为n个不交子区间,使第i个区间J的长度为P,任取均匀随机数U,则

33 龚光鲁，钱敏平著 应用随机过程教程及其在算法与智能计算中的应用 清华大学出版社, 2003 第２章 随机样本生成法 1 一维随机数 随机变量（或随机向量）的样本简称为随机数. 由于在统计中常用的是独立样本列， 所以我们不妨假设随机数之间都是独立的．生成随机数的方法，也称为随机数的取样法 (Sampling）． 1. 1 均匀随机变量的计算机模拟 定义２.１ 在[0,1]上均匀分布的随机变量的独立样本称为均匀随机数(U[0,1] 随机数). 在计算机上产生的称之为”伪随机数”的数列, 是一种具有非常长周期的, 且能通过数理 统计中的独立性与均匀性假设检验的数列. 实践证明伪随机数是均匀随机数的一种可行的 近似. 这种伪随机数虽然并不是独立同分布的U[0,1] 随机变量的样本, 而是在[0,1]中取值 的周期数列, 但是由于它可以像均匀随机数一样地通过数理统计中的独立性与均匀性假设 检验, 而且它的周期非常长, 以至在计算机实际运算过程中不会出现重复, 所以在实际计算 中它能很好地替代均匀随机数. 最普遍用以产生伪随机数的方法是同余法. 典型的例子如下: yn+1 = 5 13 yn (mod 2 36 ), y0 = 1, xn = yn × 2 -36 (周期约为2 ×1010）； yn+1 = 5 17 yn (mod 2 42 ), y0 = 1, xn = yn × 2 -42 (周期约为1012）； 2 1 44 0 1 44 周期约为 1014） 4 1 = + (mod 2 ), = 0, = 1, = × 2 ( × - n+ n + n n n y y y y y x y ． （关于伪随机数， 可参见：现代数学手册，随机数学卷，第 10 篇，孙嘉阳， 石坚，丛树 铮，徐映波编 蒙特卡罗法．华中科技大学出版社，2000 年）． 1. 2 分布函数F( x) 的随机数 命题２.２（反函数方法）分布函数为F( x) 的独立随机变量列的样本，称为 F( x) 随机 数．若F( x) 严格单调递增, x 是均匀随机数, 则 (x ) -1 F 是 F( x) 随机数, 其中 -1 F 为 F 的反 函数. 证明 ( ( ) ) ( ( )) ( ) 1 P F £ x = P £ F x = F x - x x . ? 命题２．３ 设随机变量x 只取有限个值，其分布为 ÷ ÷ ø ö ç ç è æ n n p p x x L L 1 1 x ~ . 把[0,1] 分为n 个不交子区间, 使第i 个区间 i J 的长度为 pi . 任取均匀随机数U , 则

1(U) 就是一个5随机数(它的意思是:如果U落入J,就取ξ=x1) 在统计再抽样中的应用 在样本组中再抽样,或者由样本作的参数估计代替分布中的未知参数后,所得到的分布 的随机取样,统一称为 Bootstrap方法.具体地说有如下两种方法 (1)非参数 Bootstrap方法.设自一个未知方差的分布取样X1…,x(不是计算 机模拟取样,而是人工取样)如果要作方差的区间估计,就需要知道方差估计σ的方差 lar().一般Vamr(σ)很不好求,需要对它用再抽样进行估计.为此可将样本分布 X 1作为离散随机变量的分布,独立地取样N次,每次独立地取样m个设从 第k次的m个样本值得到方差的估计σk(k≤N),将此N个的平均记为G,最后用 N-12(0k-0)2估计ar(a) 此法可以用于一般未知参数的方差估计 (2)参数 Bootstrap方法.设自一个带有未知参数(91,…9)的分布p(x,912…9) 的样本X1…,Xn(不是计算机模拟取样,而是人工取样)得到未知参数的估计(91…,9) 后,对分布Pp(x,91,……,91)用计算机模拟取样.独立地取样N次,每次独立地取样m个.其 它与(1)相同 注意,计算机模拟取样只能对已知的分布施行,对于含未知参数的分布,只能作普通的 人工取样.以上的两种再抽样方法,补充了人工取样采样量的限制.因为计算机模拟取样既 快速又经济 1.3正态随机数 N(,1)随机数称为标准正态随机数.生成标准正态随机数有一个比反函数的方法更为 简单的实践方法,就是利用中心极限定理设n,…,n2为均匀随机数(它们是独立的),由 中心极限定理,可以认为=n1+…+n12-6≈N(01),即用5=n1+…+n2-6近似地 作为标准正态随机数.在实际计算中n,(1≤i≤12)们还应该用伪随机数代替 命题2.4(生成标准正态随机数的 Box-Muller方法)取两个独立的均匀随机数

34 å= n i xi I J Ui 1 ( ) 就是一个x 随机数（它的意思是：如果U 落入 i J ，就取 i x = x ）． 在统计再抽样中的应用 在样本组中再抽样，或者由样本作的参数估计代替分布中的未知参数后，所得到的分布 的随机取样，统一称为 Bootstrap 方法．具体地说有如下两种方法 （１）非参数 Bootstrap 方法．设自一个未知方差的分布取样 X Xn , , 1 L （不是计算 机模拟取样，而是人工取样）如果要作方差的区间估计，就需要知道方差估计 2 Ù s 的方差 ( ) 2 Ù Var s ．一般 ( ) 2 Ù Var s 很不好求，需要对它用再抽样进行估计．为此可将样本分布 ÷ ÷ ø ö ç ç è æ n n X Xn 1 1 1 L L 作为离散随机变量的分布, 独立地取样N 次，每次独立地取样m 个．设从 第k 次的m 个样本值得到方差的估计 ( ) 2 k k £ N Ù s ，将此 N 个的平均记为 2 Ù s ，最后用 2 2 2 1 2 ( ) 1 1 Ù Ù = Ù - - = å Ù s s k s N N k 估计 ( ) 2 Ù Var s ． 此法可以用于一般未知参数的方差估计． （２）参数 Bootstrap 方法． 设自一个带有未知参数( , ) J1 LJl 的分布 ( , , ) 1 l p x J LJ 的样本 X Xn , , 1 L （不是计算机模拟取样，而是人工取样）得到未知参数的估计( l ) Ù Ù J１，L，J 后，对分布 p x, l ) Ù Ù （ J１，L，J 用计算机模拟取样．独立地取样 N 次，每次独立地取样 m 个．其 它与（１）相同． 注意，计算机模拟取样只能对已知的分布施行，对于含未知参数的分布，只能作普通的 人工取样．以上的两种再抽样方法，补充了人工取样采样量的限制．因为计算机模拟取样既 快速又经济． 1. 3 正态随机数 N(0,1) 随机数称为标准正态随机数． 生成标准正态随机数有一个比反函数的方法更为 简单的实践方法, 就是利用中心极限定理. 设 1 12 h ,L,h 为均匀随机数（它们是独立的）, 由 中心极限定理，可以认为 6 (0,1) x =h1 +L+h12 - » N , 即用x =h1 +L+h12 -6 近似地 作为标准正态随机数. 在实际计算中hi (1 £ i £ 12) 们还应该用伪随机数代替. 命题２.４ (生成标准正态随机数的 Box-Muller 方法) 取两个独立的均匀随机数

n, n2 2In n, cos(2r,) 52=y-2hn1sn(2x) 则51,2为相互独立的标准正态随机数 证明令1,n2~U[0且独立,则1-1,72也是独立的U,]随机变量.于是由命题 22,p=F(-n1)=√-2hn1~分布函数F(r)=1-e2,9=2n2~U[0,2],且 相互独立.而51=Pco9,52=pSin9,易见它们是独立的标准正态随机数 命题2.5(生成标准正态随机数的 Marsal ia方法)设(X,F)为单位圆上的均匀 随机数.则 In(X X+y 8)0) (提示将直角坐标(x,Y)转换为极坐标(R,9)) 一般正态随机数的生成若为标准正态随机数,则显见G2+为N(μ,a2)随机数 1.4 Poisson随机数 下述结论给出了利用伪随机数生成 Poisson随机数的方法。 命题2.6设U1,U2,…是相互独立的,1均匀随机数.若 Uk<es∏U,则定义N=n·那么N~ poisson 证明令T=-hUk~eXp1在指数流与 Poisson过程的关系(参见第3章)中取参 数为1,取时间t为λ即得 1.5混合分布随机数 对于权重为P12…,Pn(和为1的n个正数)的混合分布随机数,我们有 命题2.7设U~U[0110=10<…<tn=1,t1-1-1=P1(i≤n),F(x)i≤n)为分 布函数,那么 ∑F U--)l-(U)~分布函数为∑pF的混合分布 证明

35 1 2 h ,h , 令 2ln cos(2 ) 1 h1 ph2 x = - , 2ln sin( 2 ) 2 h1 ph2 x = - . 则 1 2 x ,x 为相互独立的标准正态随机数. 证明 令 , ~ [0,1] h1 h2 U 且独立, 则 1 2 1-h ,h 也是独立的U[0,1] 随机变量. 于是由命题 ２.2, (1 1 ) 2 ln 1 ~ 1 r = -h = - h - D F 分布函数 2 2 ( ) 1 r F r e - = - , 2 ~ [0 2 ] J ph2 U ，p D = , 且 相互独立. 而x1 = r cosJ,x2 = r sin J ，易见它们是独立的标准正态随机数. 命题２.５ （生成标准正态随机数的 Marsaglia 方法） 设(X,Y ) 为单位圆上的均匀 随机数. 则 ÷ ÷ ø ö ç ç è æ + - + =÷ ÷ ø ö ç ç è æ D Y X X Y X Y 2 2 2 2 2ln( ) h x ÷ ÷ ø ö ç ç è æ ÷ ÷ ø ö ç ç è æ ÷ ÷ ø ö ç ç è æ 0 1 1 0 , 0 0 ~ N . （提示 将直角坐标(X,Y ) 转换为极坐标(R,J) ）. 一般正态随机数的生成 若x 为标准正态随机数, 则显见sx + m 为 ( , ) 2 N m s 随机数. 1. 4 Poisson 随机数 下述结论给出了利用伪随机数生成 Poisson 随机数的方法。 命题２.６ 设U1 ,U2 ,L是相互独立的[0,1]均匀随机数． 若 Õ Õ + = = -l < £ 1 1 1 n k n k U k e Uk ， 则定义 N = n ． 那么 N ~ Poissonl . 证明 令 1 ln ~ exp Tk =- Uk D . 在指数流与 Poisson 过程的关系 ( 参见第 3 章) 中取参 数为 1, 取时间t 为l 即得. 1. 5 混合分布随机数 对于权重为 p pn , , 1 L (和为 1 的n 个正数) 的混合分布随机数, 我们有 命题２.７ 设 ~ [0,1],0 1, ( ) U U = t 0 <L < t n = t i - t i -1 = pi i £ n , F (x)(i n) i £ 为分 布函数, 那么 å= - - - - n i t t i i i I U p U t F i i 1 ( , ] 1 1 ( ) ( ) ~ 1 分布函数为 i i n i å p F =1 的混合分布. 证明

P1-41(0)≤x) P(F )1(U)≤x,U∈(1-,1]) Pi ∑P(-1<U≤1+pF(x)=∑pF(x) 在实际计算中,应该用伪随机数来取代均匀随机数U,如果取到的伪随机数落在(t-1,l1 中,则取F(U-b ),这样得到的数就是∑PF混合分布随机数 这个方法常用在排队论中.在那里的典型情形是混合指数分布(有的书上称为超指数分 布)即F(x)=1-c4,此时简单地有F(y)=-1-m(1-y),于是计算变得非常简单 入 而有效(当然也可利用命题22通过反函数来得到混合指数分布随机数.但是计算量会增加 很多,因为这个反函数并不简单 1.6 Von Neuman取舍原则 Von Neuman取舍原则 假定我们要生成密度为p(x)的随机数.为此取一个参考分布密度P0(x),使它满足 (1)p0(x)随机数容易生成,例如P0(x)为正态密度,均匀密度,指数密度,及它们的 混合密度; (2)po(x)与p(x)的取值范围差不多,且存在C,使p(x)≤C·P0(x) 那么,我们有 命题2.8设随机变量η具有密度P0(x),而随机变量U~U/[0,且与n独立,则 P(n≤x p() ≥U)=p(vh CP0(7) 证明对的取值用推广了的全概率公式(P(4)=「P(4|n=xg(x)dk),得到 Pn≤x,PO ≥U)「PU≤ pl) Cp()%0()d p(y)dy 左 ))∫PUsp) p() poG 取舍原则( Rejection Principle)的具体作法是 (1)独立地生成n个独立的P0(x)随机数n,…n与n个与之独立的U/[0,随机数

36 £ = - å - = - - ( ( ) ( ) ) ( , ] 1 1 1 1 I U x p U t P F i i t t n i i i i ( ( ) ( ) , ( , ]) ( , ] 1 1 1 1 1 t t i i i i i n i I U x U t t p U t P F i i - - - = £ Î - å - ( ( )) ( ) 1 1 P t 1 U t 1 p F x p F x n i i i n i å i i i i å = = = - < £ - + = ． ? 在实际计算中, 应该用伪随机数来取代均匀随机数U , 如果取到的伪随机数落在 ( , ] i 1 i t t - 中, 则取 ( ) 1 1 i i i p U t F - - - , 这样得到的数就是å= n i piFi 1 混合分布随机数. 这个方法常用在排队论中. 在那里的典型情形是混合指数分布(有的书上称为超指数分 布), 即 x i i F x e -l ( ) = 1- , 此时简单地有 ln(1 ) 1 ( ) 1 F y y i i - l = - - , 于是计算变得非常简单 而有效 (当然也可利用命题 2.2 通过反函数来得到混合指数分布随机数. 但是计算量会增加 很多, 因为这个反函数并不简单). 1. 6 Von Neuman 取舍原则 Von Neuman 取舍原则： 假定我们要生成密度为 p( x) 的随机数. 为此取一个参考分布密度 ( ) 0 p x , 使它满足: (1) ( ) 0 p x 随机数容易生成, 例如 ( ) 0 p x 为正态密度, 均匀密度, 指数密度, 及它们的 混合密度； (2) ( ) 0 p x 与 p( x) 的取值范围差不多, 且存在C ，使 ( ) ( ) 0 p x £ C × p x ． 那么，我们有 命题 2. ８ 设随机变量h 具有密度 ( ) 0 p x , 而随机变量U ~ U[0,1] 且与h 独立, 则 ò -¥ £ ³ = x U p v dv Cp p P x ) ( ) ( ) ( ) ( | 0 h h h . 证明 对h 的取值用推广了的全概率公式（ ò P(A) = P(A |h = x)g(x)dx ），得到 左 = = 右 £ £ = ³ £ ³ = ò ò ò ò ¥ -¥ -¥ ¥ -¥ -¥ p y dy C p y dy C p y dy Cp y p y P U p y dy Cp y p y P U U Cp p P U Cp p P x x x ( ) 1 ( ) 1 ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( , 0 0 0 0 0 0 h h h h h ．? 取舍原则(Rejection Principle)的具体作法是: (1) 独立地生成n 个独立的 ( ) 0 p x 随机数h hn , , 1 L 与n 个与之独立的U[0,1] 随机数 U U n , , 1 L

(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 章)