Sampling Methods

Inverse Transformation Sampling

Sample from $D$ with density $f(x)$ and CDF $F(x)$, given $U \sim \mathrm{Unif}(0,1)$. Find $T$ such that $T(U) = X \sim D$.

$$\mathbb{P}(X \le x) = \mathbb{P}(T(U) \le x) = \mathbb{P}(U \le T^{-1}(x)) = T^{-1}(x)$$

So $F(x) = T^{-1}(x)$, i.e. $T = F^{-1}$. Sample from $U$ and plug into $F^{-1}$: the result is a sample from $D$. If $F$ is not invertible, use the generalized inverse $F^{\leftarrow}(u) = \inf\{x : F(x) \ge u\}$ (see random variables).

Rejection Sampling

Sample from $P$ with density $f(x)/Z$. Choose a proposal $G$ with density $g(x)$ such that

1. the support of $G$ contains the support of $P$,
2. $G$ is possible to sample,

and choose $M$ such that $f(x) \le M g(x)$ for all $x$.

Algorithm Sample $s$ from $G$, and accept $s$ with probability $\frac{f(s)}{M g(s)}$.

$$P(s | \text{Accept}) = \frac{P(\text{Accept} | s)\, P(s)}{P(\text{Accept})} = \frac{\frac{f(s)}{M g(s)}\, g(s)}{\int g(s) \frac{f(s)}{M g(s)}\, ds} = \frac{f(s)/M}{\frac{1}{M}\int f(s)\, ds} = \frac{f(s)}{Z} = \text{density of } P$$