rejection sampling does: samples from target by accepting/rejecting proposals

Rejection sampling generates observations from a target distribution

Rejection sampling is a technique used to generate observations from a target distribution by using an auxiliary distribution that is easy to sample from. The method involves generating samples from this auxiliary distribution and then accepting or rejecting them based on a criterion related to the target distribution. This process allows for the generation of samples from complex distributions that may not have a simple analytical form.

Example

Suppose we want to sample from a target distribution with density function f(x). We choose an auxiliary distribution with density function g(x) that is always less than or equal to f(x) for all x. We then generate samples from g(x) and accept them with probability f(x)/g(x). If a sample x is accepted, we use it as a sample from the target distribution; otherwise, we reject it and repeat the process.

Remember this

Rejection sampling is important because it allows for the generation of samples from complex distributions that may not have a simple analytical form, enabling various applications in numerical analysis and computational statistics.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

importance sampling does: reweights samples from proposal to estimate target expectation

Importance sampling estimates target expectations using samples from a different distribution

Metropolis–Hastings algorithm

Metropolis-Hastings algorithm samples from difficult distributions

Resampling (statistics)

Bootstrapping samples with replacement to estimate distributions

DDIM does: deterministic sampling for faster generation with fewer steps

DDIM accelerates image generation by deterministically sampling intermediate steps

classifier-free guidance does: interpolates between conditional and unconditional generation

"Classifies samples as either conditioned or unconditioned, guiding generation towards desired outcomes."

denoising score matching does: learns to denoise, which equals learning the score

Propensity score matching (PSM) reduces bias in treatment effect estimates

Swipe through 100 ML concepts daily

Open Pocket Polymath