基本抽样算法（Basic Sampling Algorithms）_JackWang

http://blog.sina.com.cn/u/2049205407

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

基本抽样算法（Basic Sampling Algorithms）

(2013-04-13 09:31:11)

标签：

抽样算法

累积分布函数

随机数发生器

随机数

分类： Machine_Learning

作为一名programmer，伪随机数发生器是经常用到的。在 C/C++ 语言中我们可以用 rand 函数来获得范围为 0-RAND_MAX 的整数类型的随机数。一般情况下我们得到的随机数都是服从均匀分布的，那么如果我们想要得到服从其他分布的随机数，该怎么办呢？比如我们需要一个随机数生成器，要求她产生的随机数服从正态分布。

对于大多数比较简单的分布，我们可以用基本采样算法（Basic Sampling Algorithms），对于其他更复杂的算法，可以用Rejection-sampling（或称为Acceptance-rejection sampling接受拒绝算法）来解决，Rejection-sampling将在下一篇文章中介绍。

基本采样算法的思想很简单：用均匀分布到目标分布的转换来实现目标分布随机数的产生。所以该算法实现的基础是首先要有一个均匀分布的随机数发生器。不失一般性的，我们假设均匀分布的取值范为(0,1)（在 C/C++ 中只需把rand生成的随机数除以RAND_MAX即可）。

首先假设有两个变量 Z 和 Y ，变量 Z 的取值服从(0,1)上的均匀分布--p(Z)， Y 的取值服从目标分布--p(Y)。p(Z)和p(Y)是这两个变量的概率密度函数。

对变量 Y 求累积分布函数（Cumulative Distribution Function，cdf）：

http://s2/mw690/7a24649f4da39cd178fb1&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" />

由于该累积分布函数是连续且严格单调递增的，z是（0,1）上均匀分布的随机变量，则 http://s1/mw690/7a24649f4da39f9ab60c0&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" />服从分布p(Y)。

结论：可以用求累积分布函数的反函数和均分随机数来产生任意分布的随机数。

下面举一个例子：

变量的随机数的分布为指数分布：

http://s15/mw690/7a24649f4da3a2261e7ce&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" />

求她的累积分布函数（服从均匀分布）：

http://s9/mw690/7a24649f4da3a2e31d698&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" />

求反函数，得：

http://s10/mw690/7a24649f4da3a38818a49&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" />

从而发生器只需把均分随机数序列 Z 带入式子 http://s10/mw690/7a24649f4da3a38818a49&690Sampling Algorithms）" TITLE="基本抽样算法（Basic Sampling Algorithms）" /> 就可以得到服从指数分布的随机数序列。

其他很多分布的随机数发生器也都可以用这种方法来构造。

参考：

累积分布函数http://zh.wikipedia.org/wiki/累积分布函数

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：遗传算法 Genetic Algorithm

后一篇：连续严格单调递增累积分布函数服从均匀分布

新浪BLOG意见反馈留言板　欢迎批评指正