Rejection Sampling

Using proxy distribution $q$ to sample target distribution $p$ .

When we can calculate p values but it's difficult to sample from the entire p distribution

A technique that draws samples from a proposal distribution and determines the final sample based on evaluating the validity of these samples. Only assumption is that you know how to sample a density

q

such that

p \le Mq

where

M

is a known constant.

Sample $X'$ from q

Sample $U \sim \mathcal{U}(0,1)$

If $U\lt \frac{p(X')}{Mq(X')}$ , accept $X'$ else go back to 1 (
Importance sampling like approach but only for criteria)

On average,

M

iterations needed to obtain one point sampled from

f

M

is better to be smaller.

Because the acceptance probability

\alpha

\alpha = \int\frac{p(x)}{Mq(x)}dx =\frac{1}{M},

on average you need

\frac{1}{\alpha} = M

iterations to obtain one accepted samples.

Rejection sampling

In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type of exact simulation method. The method works for any distribution in R m {\displaystyle \mathbb {R} ^{m}} with a density.

https://en.wikipedia.org/wiki/Rejection_sampling

Rejection Sampling

Using proxy distribution qqq to sample target distribution ppp.

Recommendations

Using proxy distribution $q$ to sample target distribution $p$ .