Accept-Reject Sampling

Sample and Sampling

Sample

A sample is an outcome of a random experiment. When we sample a random variable, we obtain one specific value out of the set of its possible values. That particular value is called a sample.

The possible values and the likelihood of each are determined by the random variable's probability distribution.

Sampling

Mathematically performing sampling is the same as performing an inverse function operation of CDF(cumulative density function.

Why sampling is difficult?

• Mathematically, sampling is calculating the inverse function of the CDF
• Calculating CDF for a given PDF requires an integral operation
• Calculating the CDF is not easy to obtain an inverse function
• Thus, performing sampling numerically accurately is difficult

Proposal distribution $g(x)$

• The proposed distribution utilizes a distribution that allows us to sample easily: such as uniform distribution
• If possible, similar distribution to the target distribution is preferable

Sampling Process

$q(x)$ is proposal distribution

$p(x)$ is target distribution

1. Multiply constant M to proposal distribution for $Mq(x)\geq p(x)$ 

2. Generate $x_{0}$ from q

3. Generate sample $u$ from a uniform distribution between $\left [ 0, Mq(x_{0}) \right ]$

4. If $u$ site within A, reject. Or $u$ site within B, accept. 

$$\frac{p(x_{0})}{Mq(x_{0})} > random \ value \ from [0, 1]$$

5. Repeat this accept-reject process numerously, samples from reject sampling follows approximately $p(x)$

Reference

https://mathinsight.org/definition/random_variable_sample

https://www.youtube.com/watch?v=7wtVFfwAps4 

https://angeloyeo.github.io/2020/09/16/rejection_sampling.html