Rejection sampling

Background

Rejection sampling draws samples from a target density $f$ you can evaluate but not easily sample. On a bounded interval $[x_{\min}, x_{\max}]$ with $f(x) \le f_{\max}$, you throw darts uniformly under the bounding box $[x_{\min},x_{\max}]\times[0, f_{\max}]$ and keep the $x$ of darts that land under the curve. The accepted $x$ values are distributed exactly according to $f$.

Problem statement

Implement rejection_sample(f, xmin, xmax, fmax, n, seed=0) returning n samples from f:

1. Propose $x \sim \mathcal U(x_{\min}, x_{\max})$ and $u \sim \mathcal U(0, f_{\max})$.
2. Accept $x$ if $u \le f(x)$, else reject.
3. Repeat until n samples are accepted.

Use np.random.default_rng(seed).

Input

• f — callable target density (unnormalized is fine), evaluable on $[x_{\min}, x_{\max}]$.
• xmin, xmax — float interval bounds.
• fmax — float, an upper bound on f over the interval.
• n — int, number of accepted samples to return.
• seed — int, RNG seed.

Output

An np.ndarray of shape (n,): accepted samples, all within [xmin, xmax].

Examples

Example 1

Input:  f(x) = 2x on [0, 1], fmax = 2, n = 10000
Output: ~10000 samples whose mean ≈ 0.667 (the mean of the triangular density 2x)

Explanation: darts under the line $y=2x$ are kept; larger $x$ is accepted more often, so the samples concentrate toward 1, with mean $\int_0^1 x\cdot 2x\,dx = 2/3$.

Constraints

• Accept exactly when $u \le f(x)$ (uniform height test against the curve).
• Keep proposing until n samples are accepted; all returned values lie in [xmin, xmax].
• fmax must dominate f on the interval for correctness.

Notes

• Efficiency depends on the acceptance rate = (area under $f$) / (box area); a loose $f_{\max}$ wastes many proposals.
• Rejection sampling needs no inverse CDF — only the ability to evaluate $f$ and bound it.