OMSCS-SIM课程笔记07-Random Variate Generation
这个系列是Gatech OMSCS 仿真和建模课程(ISYE 6644: Simulation and Modeling for Engineering and Science)的同步课程笔记。课程内容涉及计算机模拟在统计分析和建模中的应用,本节介绍常用的随机变量生成方法。
利用均匀分布U(0, 1)我们可以构造出各种不同类型的随机变量。

Inverse Transform Method
最基本的随机变量生成算法是逆变换方法(inverse transform method),它的理论基础是逆变换定理(inverse transform theorem):对于任意连续型随机变量


要使用逆变换方法进行采样只需要从均匀分布中采样一个随机数

Continuous Examples
很多常见分布的CDF都具有比较简单的解析形式,因此我们可以使用逆变换方法来生成来自这些分布的随机数。



但需要注意的是,正态分布的CDF是不具有解析形式的。如果一定要使用逆变换方法生成正态分布的随机数则可以通过一些近似方法来近似标准正态分布的CDF。


得到标准正态分布的随机数后只要通过简单变形就可以获得其它均值和方差所定义的正态分布。

Discrete Examples
对于离散型随机变量,可以把CDF转换成一个分段函数然后利用逆变换方法来进行采样。


对于几何分布Geom(

不过更常用的方法是利用几何分布和Bernoulli分布的关系来进行采样。

而对于Poisson分布Pois(


Empirical Distributions
在很多情况下我们无法使用已知的分布来表示随机变量,此时可以利用经验分布(empirical distributions)来近似它的CDF。

得到均匀分布随机数

Convolution Method
这里卷积(convolution)是指把随机变量加起来构造新的随机变量。比如说二项分布Bin(

类似地,三角分布Triangular(0, 1, 2)等于两个均匀分布U(0, 1)的和。

Erlang分布则是指数分布的和。

根据CLT我们还可以利用大量的均匀分布来构造出标准正态分布。

使用卷积来构造的其它常用分布如下:

Acceptance-Rejection Method
为了解决随机变量CDF无法计算的问题人们还开发出了接受-拒绝方法(acceptance-rejection method)来进行采样。接受-拒绝方法的思想是首先从一个已知的分布进行采样,如果生成的样本满足要求就接受它。

接受-拒绝方法严格的定义如下:设我们想要采样的PDF为
我们从
则接受样本



Proof
接下来我们证明一下接受-拒绝方法的正确性。记事件
而对于事件
利用全概率公式可以得到联合概率:
令
把上面的这些式子带入CDF有:
因此



Continuous Examples
在使用接受-拒绝方法进行采样时一般要求已知分布

对于CDF不可逆的函数我们无法使用逆变换方法进行采样,此时仍然可以使用接受-拒绝方法:


Poisson Distribution
接受-拒绝方法的经典应用是生成Poisson分布的随机数,这里介绍一种接受-拒绝方法的变体。根据定义,Poisson分布的样本可以理解为计数过程单位时间内的到达数量,参数

因此可以利用计数过程来生成Poisson分布的随机数。同时注意到相邻到达的时间间隔服从指数分布Exp(

上面的推导说明我们只需要从均匀分布中采样出一个随机数序列,选择它们累乘恰好小于


对于参数


Composition Method
composition方法(composition method)是指利用利用两个随机变量来构造出一个新的随机变量。如果随机变量


对于Laplace分布(Laplace distribution),我们可以把它的CDF利用Bernoulli分布进行分解。进行采样时只需要根据Bernoulli样本的结果选择对应的CDF进行采样即可。


Special-Case Techniques
对于某些特定的分布人们还开发出了一些特殊的采样方法。
Box–Muller Method
Box–Muller方法(Box–Muller method)是利用两个独立均匀分布来构造标准正态分布的方法。进行采样时只需要先采样出两个相互独立的均匀分布样本

利用Box–Muller方法还可以证明正态分布相关的一些性质。比如说


除了Box–Muller方法外也可以使用Polar方法(Polar method)来构造标准正态分布,试验表明Polar方法的计算效率要比Box–Muller方法略高一些。

Order Statistics
次序统计量(order statistics)定义为独立同分布的随机变量序列



对于一些常用概率分布有时可能无法直接计算它们的CDF。此时可以通过概率分布之间的关系,利用简单的概率分布来构造出复杂的概率分布。

Multivariate Normal Distribution
前面我们只介绍了如何生成一维随机变量的样本,在这一小节中则关注高维的正态分布。首先考虑二维的情况,对于二维正态分布我们需要两个维度上的均值、方差以及它们的相关系数来描述整个概率分布。

对于更高维度的情况我们只需要把均值和方差的概念推广到矩阵即可,因此描述高维正态分布只需要一个均值向量

从高维正态分布直接进行采样是比较困难的,但可以利用标准正态分布进行构造。记标准正态分布为
其中
因此对

大多数软件中都有Cholesky分解的实现,直接调用即可。

综合上面的步骤可以得到多元正态分布的采样算法如下:

Generating Stochastic Process
本节最后我们来介绍如何对随机过程进行采样。
Markov Chains
马尔科夫链(Markov chain)是一类重要的随机过程。简单来说马尔科夫链假设了系统在发生状态转移时的转移概率只与前一时刻的状态有关,与转移的历史过程无关。因此对离散马尔科夫链进行采样时只需要在每一步单独进行采样即可。


连续的情况与离散类似,只需要针对前一时刻的状态重新进行采样即可。考虑齐次Poisson过程(homogeneous Poisson process),我们可以利用指数分布采样出连续的到达时间间隔,然后就可以通过记数的方式来对齐次Poisson过程进行采样。

某些情况下我们已知[a, b]时间段上的到达数总量,目标是对到达时刻进行采样。此时只需要从均匀分布U(0, 1)进行采样,然后排序并变换到区间[a, b]上即可。

Nonhomogeneous Poisson Process
对于非齐次Poisson过程(nonhomogeneous Poisson Process),参数

因此对非齐次Poisson过程进行采样的一种方法是利用

正确的做法是使用Thinning算法进行采样,此时我们直接使用时间段上最大的




Time Series
对于时间序列(time series)一般可以直接根据定义来进行采样。
MA


AR


ARMA

EAR

ARP


Queuing
对于排队问题我们也有非常简单的采样方法。只要采样出了到达时刻和服务时间,其它的参数都可以通过定义计算出来。

Brownian Motion
本节最后介绍了如何对布朗运动(Brownian motion)进行采样。布朗运动在自然科学、金融市场等领域中都有着大量的应用,标准布朗运动的定义如下:


对布朗运动进行采样的理论基础是Donsker定理(Donsker’s theorem),它指出均值为0方差为1的独立同分布随机变量序列经过变换后会收敛到标准布朗运动上:

在此基础上就可以利用Bernoulli分布或是标准正态分布的样本来构造出布朗运动。

布朗运动的一些常用性质如下:

Geometric Brownian Motion
布朗运动的一个常见变体是几何布朗运动(geometric Brownian motion),它可以用来对股票价格进行建模。


