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

How do you randomly pick a number following a strange rule?

Imagine you're trying to pick a random day of the year that falls on a weekend, but you want to ensure it's a Saturday. How would you do that?

Think of days as points on a circle. To find a Saturday, you randomly pick a day and check if it's a Saturday. If not, you keep looking until you find one. This process is called rejection sampling, where you keep picking until you meet the condition.

Example

If you randomly select days, you might pick Tuesday, then Wednesday, then Thursday, and finally Saturday. You keep rejecting the days that aren't Saturdays until you hit one.

Remember this

Rejection sampling is like repeatedly choosing random days until you hit the one that fits your rule.

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

Related concepts

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

Why can't we always use the same samples to figure out what's happening in a complex system?

Metropolis–Hastings algorithm

Metropolis-Hastings algorithm samples from difficult distributions

DDIM does: deterministic sampling for faster generation with fewer steps

Ever feel like your text generator keeps repeating boring phrases?

Diffusion

Can you imagine a crowd spreading out evenly in a room?

Bloom filter

Ever searched for a word in a dictionary and hoped it wouldn't lead to a wild goose chase?

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

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

Swipe through 100 ML concepts daily

Open Pocket Polymath