1700537263
（2）从均匀分布U(0,1)产生一个随机数ui。
1700537264
1700537265
1700537266
（3）如果，则接受样本xi ；否则拒绝，重新进行步骤（1）～（3），直到新产生的样本xi被接受。
1700537267
1700537268
通过简单的推导，可以知道最终得到的xi服从目标分布p(x)。如图8.3（a）所示，拒绝采样的关键是为目标分布p(x)选取一个合适的包络函数M·q(x)：包络函数越紧，每次采样时样本被接受的概率越大，采样效率越高。在实际应用中，为了维持采样效率，有时很难寻找一个解析形式的q(x)，因此延伸出了自适应拒绝采样（Adaptive Rejection Sampling），在目标分布是对数凹函数时，用分段线性函数来覆盖目标分布的对数ln p(x)，如图8.3（b）所示，这里不再细述。
1700537269
1700537270
1700537271
1700537272
1700537273
图8.3 拒绝采样示意图
1700537274
1700537275
很多时候，采样的最终目的并不是为了得到样本，而是为了进行一些后续任务，如预测变量取值，这通常表现为一个求函数期望的形式。重要性采样就是用于计算函数f(x)在目标分布p(x)上的积分（函数期望），即
1700537276
1700537277
1700537278
．
1700537279
1700537280
（8.4）
1700537281
1700537282
1700537283
首先，找一个比较容易抽样的参考分布q(x)，并令，则有
1700537284
1700537285
1700537286
，
1700537287
1700537288
（8.5）
1700537289
1700537290
这里w(x)可以看成是样本x的重要性权重。由此，可以先从参考分布q(x)中抽取N个样本{xi}，然后利用如下公式来估计E[f]：
1700537291
1700537292
1700537293
1700537294
1700537295
（8.6）
1700537296
1700537297
图8.4是重要性采样的示意图。如果不需要计算函数积分，只想从目标分布p(x) 中采样出若干样本，则可以用重要性重采样（Sampling-Importance Re-sampling，SIR），先在从参考分布q(x)中抽取N个样本 {xi }，然后按照它们对应的重要性权重{w(xi)}对这些样本进行重新采样（这是一个简单的针对有限离散分布的采样），最终得到的样本服从目标分布p(x)。
1700537298
1700537299
1700537300
1700537301
1700537302
图8.4 重要性采样示意图
1700537303
1700537304
在实际应用中，如果是高维空间的随机向量，拒绝采样和重要性重采样经常难以寻找合适的参考分布，采样效率低下（样本的接受概率小或重要性权重低），此时可以考虑马尔可夫蒙特卡洛采样法，常见的有Metropolis-Hastings采样法和吉布斯采样法。后续会专门介绍马尔可夫蒙特卡洛采样法，这里不再赘述。
1700537305
1700537306
·总结与扩展·
1700537307
1700537308
上述解答中我们只是列举了几个最常用的采样算法，简单介绍了它们的具体操作。在实际面试时，面试官可能会让面试者选择其最熟悉的某个采样算法来回答，然后较深入地问一下该算法的理论证明、优缺点、相关扩展和应用等。例如，为何拒绝采样或重要性采样在高维空间中会效率低下而无法使用？如何从一个不规则多边形中随机取一个点？
1700537309
1700537310
1700537311
1700537312