Sampling Methods

Quota Sampling

Inverse Transform Sampling

Inverse CDF transformation of “Bit Shuffling” creates arbitrary $X_i\sim f_{\theta }(x)$

Reminder: If the CDF of $X_i$ is $F_X(x)$, then the PDF of $X_i$ is $f_X(x)=\stackrel{\text{if it exists...}}{\frac{d}{dx}{F}_X(x)}$

$$\begin{array}{rl}{F}_X(x)=\stackrel{{\int }_{-\infty }^x{f}_{\theta }(\tilde{x})d\tilde{x}}{Pr\left(X_i\le x\right)}& =\stackrel{\text{ If the inverse exists...}}{\stackrel{\text{Suppose }{X}_i=F_X^{-1}(U_i)}{Pr\left(F_X^{-1}(U_i)\le x\right)}}\\ & =Pr\left(F_X(F_X^{-1}(U_i)\le F_X(x)\right)\\ & =Pr\left(U_i\le \underset{\in [0,1]}{F_X(x)}\right)=F_X(x)\\ & ⟹F_X^{-1}(U_i)\sim f_{\theta }(x)\end{array}$$

Good “Bit Shuffling” $U_i\sim U(0,1)$ Pseudorandomness is indistinguishable from (actual true) Randomness

Rejection Sampling

$$\begin{array}{rl}\mathbb{P}(X\text{ accepted})& =\mathbb{P}\left(U\le \frac{f(X)}{cg(X)}\right)\\ & =\int \mathbb{P}\left(U\le \frac{f(X)}{cg(X)}\right|X=x)g(x)dx\\ & =\int \frac{f(x)}{cg(x)}g(x)dx\\ & =\frac{1}{c}\int f(x)dx\end{array}$$

$\int f(x)dx=1$, so $\mathbb{P}(X\text{ accepted})=\frac{1}{c}$

Rejection sampling changes the univariate sampling problem $X\sim f_{\theta }(x)$ into a two-dimensional problem $(\tilde{X},U)\sim \tilde{f}(\tilde{x},u)={\tilde{f}}_{\tilde{\theta }}(\tilde{x})\tilde{f}(u)$ that samples according to the desired probabilities

$$\begin{array}{rl}Pr\left(\tilde{X}\le x|U\le \frac{f_{\theta }(\tilde{X})}{c{\tilde{f}}_{\tilde{\theta }}(\tilde{X})}\right)& =Pr\left(\tilde{X}\le x,U\le \frac{f_{\theta }(\tilde{X})}{c{\tilde{f}}_{\tilde{\theta }}(\tilde{X})}\right)/Pr\left(U\le \frac{f_{\theta }(\tilde{X})}{c{\tilde{f}}_{\tilde{\theta }}(\tilde{X})}\right)\\ & ={\int }_{-\infty }^x{\int }_0^{\frac{f_{\theta }(\tilde{x})}{c{\tilde{f}}_{\tilde{\theta }}(\tilde{x})}}{\tilde{f}}_{\tilde{\theta }}(\tilde{x})dud\tilde{x}/{\int }_{-\infty }^{\infty }{\int }_0^{\frac{f_{\theta }(\tilde{x})}{c{\tilde{f}}_{\tilde{\theta }}(\tilde{x})}}{\tilde{f}}_{\tilde{\theta }}(\tilde{x})dud\tilde{x}\\ & ={\int }_{-\infty }^x\frac{f_{\theta }(\tilde{x})}{c}d\tilde{x}/{\int }_{-\infty }^{\infty }\frac{f_{\theta }(\tilde{x})}{c}d\tilde{x}={\int }_{-\infty }^x{f}_{\theta }(\tilde{x})d\tilde{x}\\ & \\ & =F_{\theta }(x)⟹CDF\end{array}$$