Squeezed Rejection Sampling

Why This Matters

Standard rejection sampling requires evaluating the target density $f(x)$ for every proposed sample. When $f$ is expensive to compute (think multivariate posteriors, normalizing constants involving special functions, or densities defined through numerical integration), each evaluation dominates the runtime.

Squeezed rejection sampling reduces the number of expensive evaluations by adding a cheap lower bound. If the proposal clearly falls in the accept region or clearly falls in the reject region, you skip the expensive evaluation entirely.

Mental Model

In standard rejection sampling, you have an envelope $Mg(x) \geq f(x)$ and you accept a proposal $x$ with probability $f(x) / (Mg(x))$. You always need to evaluate $f(x)$.

Now add a squeeze function $s(x)$ satisfying $s(x) \leq f(x)$ for all $x$. Draw $x \sim g$ and $u \sim \text{Uniform}(0, Mg(x))$. If $u \leq s(x)$, accept without evaluating $f$. If $u > Mg(x)$, reject without evaluating $f$ (this never happens by construction). If $s(x) < u \leq Mg(x)$, then and only then evaluate $f(x)$ and accept if $u \leq f(x)$.

The squeeze handles the easy cases. You only pay for $f$ when the sample lands in the uncertain strip between $s(x)$ and $Mg(x)$.

Formal Setup

Definition

Squeeze Function

Given a target density $f(x)$ and an envelope $Mg(x) \geq f(x)$, a squeeze function is any function $s: \mathcal{X} \to [0, \infty)$ such that:

$0 \leq s(x) \leq f(x) \leq Mg(x) \quad \text{for all } x \in \mathcal{X}$

The squeeze must be cheap to evaluate relative to $f$.

Definition

Squeezed Rejection Sampling Algorithm

1. Draw $x \sim g(x)$ from the proposal distribution.
2. Draw $u \sim \text{Uniform}(0, 1)$.
3. If $u \leq s(x) / (Mg(x))$, accept $x$ (no evaluation of $f$).
4. Else if $u \leq f(x) / (Mg(x))$, accept $x$ (evaluate $f$).
5. Else reject $x$ (evaluate $f$).
6. Return to step 1.

Main Theorems

Theorem

Correctness of Squeezed Rejection Sampling

Statement

Squeezed rejection sampling produces independent samples distributed exactly according to the target density proportional to $f(x)$. The acceptance probability is identical to standard rejection sampling: $1/M$.

Intuition

The squeeze only determines when you evaluate $f$. It never changes the accept/reject decision. When you do evaluate $f$, the decision is identical to standard rejection sampling. So the output distribution is unchanged.

Proof Sketch

Partition the probability space into three events for a proposal $(x, u)$ where $u \sim \text{Uniform}(0, Mg(x))$:

Event A: $u \leq s(x)$. Accept. Since $s(x) \leq f(x)$, we have $u \leq f(x)$, so standard rejection sampling would also accept.

Event B: $s(x) < u \leq f(x)$. Accept after evaluating $f$. Same decision as standard.

Event C: $u > f(x)$. Reject after evaluating $f$. Same decision as standard.

In all three events, the accept/reject decision matches standard rejection sampling. The squeeze only changes which event triggers the evaluation.

Why It Matters

The fraction of proposals requiring $f$-evaluation is:

$P(s(x) < u \leq Mg(x)) = 1 - \frac{\int s(x) \, dx}{\int Mg(x) \, dx}$

A tight squeeze (close to $f$) means most proposals are resolved cheaply.

Failure Mode

If the squeeze is loose ($s(x) \approx 0$), nearly every proposal falls in the uncertain strip and you evaluate $f$ anyway. The overhead of computing $s(x)$ then makes squeezed rejection sampling slower than standard rejection sampling. The squeeze must be both cheap and tight.

Canonical Examples

Example

Squeeze for the normal distribution

Suppose $f(x) \propto e^{-x^2/2}$ and the proposal is a double exponential (Laplace) distribution. A common squeeze for the standard normal is the piecewise linear function that interpolates $f$ at a grid of points, staying below $f$ everywhere. For example, between grid points $x_i$ and $x_{i+1}$, the squeeze is the linear function connecting $(x_i, f(x_i))$ and $(x_{i+1}, f(x_{i+1}))$. Since $f$ is log-concave, the linear interpolant stays below $f$. With 10-20 grid points, this squeeze resolves over 95% of proposals without evaluating $\exp(-x^2/2)$.

Common Confusions

Watch Out

The squeeze does not change the acceptance rate

Adding a squeeze does not accept more proposals. The overall acceptance probability remains $1/M$. The squeeze only reduces the number of proposals that require evaluating $f$. It trades $f$-evaluations for cheaper $s$-evaluations.

Watch Out

The squeeze need not be a density

The squeeze $s(x)$ is not required to integrate to 1 or even to be a proper density. It is just a lower bound on $f(x)$. Any non-negative function that stays below $f$ works.

Summary

• Add a cheap lower bound $s(x) \leq f(x)$ to skip expensive evaluations
• Correctness is immediate: the squeeze never changes the accept/reject decision, only when $f$ is evaluated
• Savings depend on the tightness of the squeeze: $\int s(x) \, dx / \int Mg(x) \, dx$
• If $f$ is cheap to evaluate, the overhead of computing $s$ is not worth it
• Log-concave densities admit natural piecewise linear squeezes

Exercises

ExerciseCore

Problem

Suppose the squeeze resolves 90% of proposals without evaluating $f$, and evaluating $f$ takes 100 times longer than evaluating $s$. What is the approximate speedup of squeezed rejection sampling over standard rejection sampling?

Hint

Reveal Solution

ExerciseAdvanced

Problem

For a log-concave density $f$, explain why a piecewise linear interpolant through points $(x_i, f(x_i))$ lies below $f$ between grid points. State the precise condition on $f$ that makes this work.

Hint

Reveal Solution

References

Canonical:

• Devroye, Non-Uniform Random Variate Generation (1986), Chapter 7
• von Neumann, "Various Techniques Used in Connection with Random Digits" (1951), original rejection sampling paper

Current:

• Robert & Casella, Monte Carlo Statistical Methods (2004), Chapter 2.3

• Gelman et al., Bayesian Data Analysis (2013), Chapters 10-12

• Brooks et al., Handbook of MCMC (2011), Chapters 1-5

Next Topics

• Adaptive rejection sampling: automatically refine the envelope and squeeze for log-concave densities
• Importance sampling: reweight samples instead of rejecting them