接受-拒绝采样或舍选法（Acceptance-Rejection Sampling）是一种通用的蒙特卡洛采样方法，由约翰·冯·诺依曼（John von Neumann）于20 世纪 40 年代中期（约 1947-1951 年间）在曼哈顿计划期间正式提出并系统化。该方法用于从难以直接采样的复杂目标分布中生成样本。其核心思想是利用一个易于采样的建议分布来包裹目标分布，并通过概率判断接受或拒绝样本，从而间接获得服从目标分布的样本集。
一、接受-拒绝采样原理
假设我们有一个目标概率密度函数，为了对其进行采样，我们可以选择一个已知的、易于采样的建议分布（proposal distribution）
，比如均匀分布或高斯分布。然后，我们需要找到一个合适的缩放常数
, 使得能够完全覆盖目标函数，即满足
对所有
都成立。
采样的具体步骤如下：
- 从建议分布
中随机采样一个点
- 计算接受概率
- 生成一个均匀分布的随机数
- 如果
，则接受这个样本；否则拒绝这个样本，重新从步骤1开始
这个过程可以形象地理解为：我们在曲线下方随机投点，如果点落在曲线
下方，则接受这个样本；否则拒绝这个样本。通过这种方式，我们最终得到的样本将服从目标分布
。 具体过程是这样的：先通过分布
产生一个随机数
（如下图中x轴上的坐标点
)，然后用区间
上的均匀分布
产生一个随机数
，这等效于在区间
上得到一个服从均匀分布
的随机数
(如图y轴上的点
)。 如果
落在区间
中(即
在
曲线下方)，则接受
这个随机数，如果落在
上(即
在
曲线上方)则拒绝这个随机数。
二、接受-拒绝采样的证明
假设目标分布为，而建议分布为
，且存在常数
使得对所有得
，满足
。 这里要证明得是：
, 也就是被接受随机数的分布与目标分布一致。
证明之前先明确几个事件与关系：
（1）接受事件：
（2）均匀分布的概率密度函数：
（3）随机变量是独立的。
证明：首先由条件分布计算公式：
计算联合概率密度, 根据联合分布和条件分布的关系：
由于与
是独立的，所以
，而
是
,
给定时, 事件Accept的概率密度，即
于是联合概率密度为：
于是
得证。（注：证明过程参考了Warren的博客）
三、两个例子
例1.以均匀分布作为建议分布为正态分布设计一个采样程序。
function mainForRS1() %用接受-拒绝采样方法生成服从正态分布的随机数 clear all clc %绘制目标分布概率密度函数 x=-5:0.1:5; mu=0;sigma=1.0; y=Normpdf(x,mu,sigma); plot(x,y) hold on %采样 samples=SamplingNorm(20000,mu,sigma); %绘制样本直方图 histogram(samples,'NumBins',150,'Normalization','pdf','EdgeColor','b') end function samples=SamplingNorm(numberSample,mu,sigma) %以均匀分布作为建议分布， %用接受-拒绝采样方法生成服从正态分布的随机数 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %输入: % numberSample: 样本数量 % mu: 均值 % sigma： 标准差 %输出： % samples: 样本集 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %确定分布的范围[a,b] b=mu+5*sigma; % 均匀分布的上限 a=mu-5*sigma; % 均匀分布的下限 % x=a:0.1:b; % y=normpdf(x,mu,sigma); % plot(x,y) % % 样本集 samples = zeros(1,numberSample); %存放样本 %一个合适的M M=(b-a)/(sqrt(2*pi)*sigma); accepted=0; for i=1:numberSample while 1 %从辅助分布采样 x=a+(b-a)*rand(); % 计算接受概率 alpha=Normpdf(x,mu,sigma)/(M*uniformpdf(x,a,b)); %生成一个[0,1]上均匀分布随机数 u=rand(); if u<=alpha %接受这个样本 accepted = accepted + 1; samples(accepted)=x; break; % 接受后退出循环，继续下一个样本的生成 end end end end function pdf=uniformpdf(x,a,b) %区间[a,b]上的均匀分布(建议分布) if x>=a & x<=b pdf=1/(b-a); else pdf=0; end end function y=Normpdf(x,mu,sigma) %正态分布密度函数(目标分布) y=exp(-1/2*(x-mu).*(x-mu)/(sigma*sigma)); y=y./(sqrt(2*pi)*sigma); end运行效果图（样本直方图）：
例 2. 要采样的目标分布密度函数为：
这里我们用一个正态分布作为建议分布, 其中选取缩放常数
, 则
（蓝色）和
（红色）的曲线图形如下：
特别地，本例中的正态分布随机数的生成用例1的函数SamplingNorm获得。程序如下：
function mainForRS2() clear all clc %绘制目标分布概率密度函数与建议分布曲线 x=-4:0.1:6; y1=q(x); mu=1.2;sigma=1.0; M=3; y2=M*Normpdf(x, mu, sigma); plot(x,y1,x,y2) hold on % 样本集 numberSample=1e+5; %样本数 samples = zeros(1,numberSample); %存放样本 %一个合适的M M=3.0; accepted=0; for i=1:numberSample while 1 %从辅助分布采样 x=SamplingNorm(1,mu,sigma); %x=normrnd(mu, sigma); % 计算接受概率 alpha=q(x)/(M*Normpdf(x, mu, sigma)); %生成一个[0,1]上均匀分布随机数 u=rand(); if u<=alpha %接受这个样本 accepted = accepted + 1; samples(accepted)=x; break; % 接受后退出循环，继续下一个样本的生成 end end end histogram(samples,'NumBins',150,'Normalization','pdf','EdgeColor','b') end function y=q(x) %目标分布概率密度函数 y=(0.3*exp(-(x-0.3).^2)+0.7*exp(-(x-2).^2/0.3))/1.2113; end function y=Normpdf(x, mu, sigma) %建议分布概率密度函数（正态分布） y=1/(sqrt(2*pi)*sigma)*exp(-(x-mu).^2/(2*sigma*sigma)); end运行效果图（样本直方图）为：
四、接受-拒绝采样的不足
接受-拒绝采样的不足主要体现在以下几方面：
（1）当目标分布与提议分布形状差异大、常数M取值过大时，大量样本会被直接拒绝，有效样本生成速度极慢。
（2）在高维分布中，很难找到合适的提议分布来紧密包裹目标分布，接受概率会呈指数级下降。复杂分布下的实用性大幅降低。
（3）M值的确定，对使用者的经验要求很高。