第三讲球对称分布 (I)在高维空间随机均匀)取一个向量，它几乎与任何其它给定的或独立的随机向量正交
1 第三讲 球对称分布（II） 在高维空间随机(均匀)取一个向 量，它几乎与任何其它给定的或 独立的随机向量正交
球对称随机向量的计算机采样球对称分布的表示（极分解）x=ur在理论证明或计算时非常有用。另一个重要的应用是用于蒙特卡洛采样/抽样（sampling），这里的采样/抽样指的是计算机随机数的生成。该表示。蒙特卡洛（MonteCarlo，MC）需要产生给定分布的随机数或随机向量，我们默认U（0,1）随机数容易生成并直接利用。Inversionsampling算法（适用于累积分布函数容易求逆的情形）Inversion假设随机变量X的累积分布函数F(x)=P(X<x)连续，F=1-Fsampling若~U(0,1),则F-1()兰X,F-1()兰x例如, 如果R~p(r) = nrn-1,0 <r < 1,F(r)= rn。为了生成随机数R，可首先生成～U(0,1)，令R=1/n即可。2
2 球对称随机向量的计算机采样 球对称分布的表示（极分解）𝐱 = 𝐮𝑟 在理论证明或计算时非常有 用。另一个重要的应用是用于蒙特卡洛采样/抽样（sampling）， 这里的采样/抽样指的是计算机随机数的生成。该表示。 𝑑 蒙特卡洛（Monte Carlo,MC) 需要产生给定分布的随机数或随机 向量，我们默认𝑈(0,1)随机数容易生成并直接利用。 Inversion sampling 𝑑 Inversion sampling算法(适用于累积分布函数容易求逆的情形)： 假设随机变量𝑋的累积分布函数𝐹(𝑥) = 𝑃 𝑋 < 𝑥 连续 , 𝐹ത = 1 − 𝐹。 若𝜉~𝑈(0,1),则𝐹 −1 𝜉 = 𝑋，𝐹ത−1 𝜉 = 𝑋. 𝑑 例如，如果𝑅~𝑝 𝑟 = 𝑛𝑟 𝑛−1 , 0 < 𝑟 < 1, 𝐹(𝑟) = 𝑟 𝑛。 为了生成随机数𝑅 ， 可首先生成𝜉~𝑈(0,1) , 令𝑅 = 𝜉 1/𝑛即可
N(0,1)非常重要。直接利用inversionsampling不能产生N(0,1）随机数，这是因为我们没有累积分布函数Φ的精确显式表达，无法精确计算Φ-1。但有趣的是，利用二元正态的极分解，我们可以很容易地同时产生两个N（0,1)随机数，原理如下：已知x~Nz(0,12）兰uR，u~U(S1),R~X2，只需产生u和R：： 产生9~U(0,2元),则 u = (cos(0), sin(0))T～ U(S1)· R~X2的密度px(r)= rexp(-r2 /2)，F(r) = exp(-r2 /2),则 = F(R)~U(0,1),R = -2log(5)~X2, 其中E~U(0,1), 。正态抽样：Box-Muller方法(N2(0,12)抽样)：Box-Muller算法·产生~U(0,2元)，5~U(0,1)，独立; R = y-2log(), u = (cos(0),sin(0))T;· X = Ru~N2(0,I2).利用Box-Muller方法独立产生若于正态随机变量，合在一起即得到多元标准正态随机向量。所以正态随机向量非常容易产生。3
3 已知 𝐱~𝑁2 0,𝐼2 = 𝐮𝑅， 𝐮 ~𝑈(𝑆 1 ), 𝑅~𝜒2，只需产生𝐮和𝑅: • 产生𝜃~𝑈 0,2𝜋 ,则 𝐮 = cos(𝜃), sin(𝜃 ) ⊤~ 𝑈(𝑆 1 ) • 𝑅~𝜒2的密度 𝑝𝜒2 𝑟 = 𝑟exp(−𝑟 2 /2) ，𝐹ത 𝑟 = exp(−𝑟 2 /2), 则 𝜉 = 𝐹ത 𝑅 ~𝑈 0,1 , 𝑅 = −2log(𝜉)~𝜒2，其中𝜉~𝑈 0,1 , 𝜉 ⫫ 𝜃。 𝑑 𝑁(0,1)非常重要。直接利用inversion sampling不能产生𝑁(0,1) 随机数, 这是因为我们没有累积分布函数Φ的精确显式表达， 无法精确计算Φ−1。但有趣的是，利用二元正态的极分解， 我们可以很容易地同时产生两个𝑁(0,1)随机数，原理如下： Box-Muller方法 (𝑁2 0,𝐼2 抽样): • 产生𝜃~𝑈 0,2𝜋 ，𝜉~𝑈(0,1)，独立; • 𝑅 = −2log(𝜉)， 𝐮 = cos(𝜃), sin(𝜃 ) ⊤; • 𝐱 = 𝑅𝐮~𝑁2 0,𝐼2 . 正态抽样： Box-Muller 算法 利用Box-Muller方法独立产生若干正态随机变量，合在一起即得 到多元标准正态随机向量。所以正态随机向量非常容易产生
由第二讲定理1，若z～Nn(0,In)，则u=～U(Sn-1)，因此将U(sn-1)1zl抽样Nn(O,In)随机向量单位化即得到球面均匀随机向量。U(sn-1)抽样产生z~Nn(O,In）;Z则u~U(sn-1);令u：J/zll般球对假设球对称随机向量x～f(x)=h(lxl)，由第二讲定理1的推论，2元/2称随机向xuR,uⅡ R, u~U(Sn-1),R~p(r) =h(r)rn-1r(n/2)量的抽样球对称分布抽样：产生z~Nn(O,In）;则u~U(sn-1);令u关键是产生随机变量R，可采用IIzll 2元/2inversionsampling，；如果不可行，产生一元R~p(r)=h(rrn-r(n/2)可采用拒绝抽样，importance· 令x = uR,则x ～ f(x) = h(llxll)。sampling等等（参见附录1)1/m例如，U(Bn)采样：生成E～U(O,1)，z～Nn(O,In)，X=z0
4 𝑈 𝑆 𝑛−1 抽样 由第二讲定理1，若𝐳~𝑁𝑛 0,𝐼𝑛 ，则𝐮 = 𝐳 𝐳 ~𝑈 𝑆 𝑛−1 ，因此将 𝑁𝑛 0,𝐼𝑛 随机向量单位化即得到球面均匀随机向量。 𝑈 𝑆 𝑛−1 抽样 • 产生𝐳~𝑁𝑛 0,𝐼𝑛 ； • 令 𝐮 = 𝐳 𝐳 ，则𝐮~𝑈 𝑆 𝑛−1 ; 一般球对 称随机向 量的抽样 假设球对称随机向量𝐱 ~ 𝑓 𝐱 = ℎ( 𝐱 )， 由第二讲定理1的推论， 𝐱 = 𝐮𝑅, 𝐮 ⫫ 𝑅, 𝐮~𝑈 𝑆 𝑛−1 , 𝑅~𝑝 𝑟 = 2𝜋 𝑛/2 Γ(𝑛/2) ℎ 𝑟 𝑟 𝑑 𝑛−1 球对称分布抽样： • 产生𝐳~𝑁𝑛 0,𝐼𝑛 ； • 令 𝐮 = 𝐳 𝐳 ，则𝐮~𝑈 𝑆 𝑛−1 ; • 产生一元𝑅~𝑝 𝑟 = 2𝜋 𝑛/2 Γ(𝑛/2) ℎ 𝑟 𝑟 𝑛−1 • 令𝐱 = 𝐮𝑅, 则𝐱 ~ 𝑓 𝐱 = ℎ( 𝐱 )。 关键是产生随机变量𝑅，可采用 inversion sampling,；如果不可行， 可采用拒绝抽样，importance sampling 等等 (参见附录1) 例如，𝑈(𝐵 𝑛 )采样: 生成𝜉~𝑈(0,1) ，𝐳~𝑁𝑛 0,𝐼𝑛 ，𝐱 = 𝐳 𝐳 𝜉 1/𝑛
拒绝采样或拒绝-接受采样是一种应用广泛的采样方式，U(B）的其是均匀分布采样经常采用。拒绝采样的原理是若x~U(C),拒绝抽样Co C C, 则 x|xECo~U(Co).若u.,unid~U(-1,1),则u = (ui,..,un)T~U([-1,1jn)拒绝U(Bn)的拒绝抽样：为了生成x～U(Bn），我们先在容易采样的区域[-1,1]n>Bn中均匀采样x~U([-1,1]"），如果得到的点落在Bn内，这就是我们需要的X；若该点落在球外，则拒绝该点。上述方法适用于n较小的情形，当n较大，比如n=10时，单位球与超立方体[一1,1110的体积之比为0.0025，这意味着生成10000个U([-1,1]10),其中只有约25个落在单位球内，采样效率低下5
5 拒绝采样或拒绝-接受采样是一种应用广泛的采样方式，尤 其是均匀分布采样经常采用。拒绝采样的原理是若𝑥~𝑈 𝐶 , 𝐶0 ⊂ 𝐶, 则 𝑥|𝑥∈𝐶0~𝑈 𝐶0 . 𝑈(𝐵 𝑛 )的 拒绝抽样 𝑈(𝐵 𝑛 )的拒绝抽样： 为了生成𝐱~𝑈(𝐵 𝑛 ) ，我们先在容易采样的区域 −1,1 𝑛 ⊃ 𝐵 𝑛中 均匀采样𝐱~𝑈( −1,1 𝑛 ) ，如果得到的点落在𝐵 𝑛内，这就是我们 需要的𝐱；若该点落在球外，则拒绝该点。 若𝑢1, . , 𝑢𝑛 𝑖𝑖𝑑 ~𝑈 −1,1 , 则 𝐮 = (𝑢1, . , 𝑢𝑛) ⊤ ~𝑈 −1,1 𝑛 拒绝 上述方法适用于𝑛较小的情形，当𝑛较大，比如𝑛 = 10时，单位 球与超立方体 −1,1 10的体积之比为0.0025，这意味着生成10000 个𝑈 −1,1 10 , 其中只有约25个落在单位球内，采样效率低下