A rejection sampler for a truncated normal accepts only 3% of proposals; why?

## How rejection sampling works You want draws from a density `f` that you can evaluate but not invert. Choose a proposal density `g` you can sample easily, and a constant `M` with `f(x) <= M*g(x)` for every `x`. Then repeat: 1. Draw a candidate `X` from `g`. 2. Draw `U` from Uniform(0,1). 3. Accept `X` if `U <= f(X) / (M*g(X))`; otherwise discard it and start again. The accepted values are exact draws from `f`. The geometric picture is the cleanest way to hold it: the curve `M*g` is a blanket lying over the curve `f`. You throw points uniformly under the blanket and keep only those that also fall under `f`. Points uniform under a density's curve have that density as their horizontal marginal, which is why the survivors are distributed as `f`. ## Where the acceptance rate comes from Averaging the acceptance probability over the proposal gives P(accept) = integral of g(x) * f(x)/(M*g(x)) dx = (1/M) * integral of f(x) dx = 1/M since `f` integrates to 1. So the acceptance rate is `1/M` exactly, and the number of proposals needed per accepted draw is geometric with mean `M`. Reading it as areas: acceptance equals the area under `f` divided by the area under the blanket. A blanket 33 times too big yields a 3% rate. ## Why a truncated normal punishes a box envelope A truncated normal restricts a normal to an interval `[a, b]` and renormalises. The simplest envelope is a uniform box over `[a, b]` whose height is the maximum of the density on that interval. When `[a, b]` straddles the peak, the density fills a decent share of the box and the rate is respectable. When `[a, b]` sits out in a tail, say from 2.5 standard deviations upward, the density at the left edge dwarfs the density at the right edge, so the box height is set by the edge value while most of the box sits over near-zero density. The ratio of areas collapses and the sampler grinds. The same failure appears whenever the envelope's shape does not track the target's shape: a heavy-tailed proposal over a concentrated target, or a wide proposal over a sharply peaked one. ## Diagnosing and fixing it Measure the empirical acceptance rate first; it estimates `1/M` directly and tells you how much waste there is. Then: - **Tighten the envelope.** Use a proposal whose shape follows the target rather than a flat box. For a tail region of a normal, a shifted exponential envelope tracks the decay and lifts acceptance dramatically. - **Lower M to the true bound.** A conservative `M` chosen "to be safe" costs proportionally. `M` should be the smallest constant for which the inequality still holds everywhere, since acceptance is exactly `1/M`. - **Split the region.** Piecewise envelopes over sub-intervals fit far more tightly than one global blanket. - **Avoid rejection altogether.** For a truncated distribution with an invertible CDF the inverse-transform route is exact and wastes nothing: map a uniform onto the retained probability range, `X = F^-1(F(a) + U*(F(b) - F(a)))`, and every draw is accepted. ## The bias question A low acceptance rate is a cost, not a correctness problem. Provided the envelope really does dominate the target everywhere, accepted draws are exactly distributed as `f` regardless of how many were rejected. Three ways to convert the cost into a genuine bias, all of which show up in real code: - **A broken bound.** If `f(x) > M*g(x)` for some region, the ratio exceeds 1 there, that region is silently under-sampled, and the output is wrong. The bound must be verified analytically, not assumed. - **Reusing rejected proposals.** Clamping a rejected value to the boundary, or keeping it anyway when time runs out, piles mass where it does not belong. - **Capping the retry loop.** Returning the last candidate after a fixed number of failures biases the output toward whatever the proposal favours, and it does so hardest exactly where acceptance is lowest. ## The dimension problem Acceptance degrades sharply as dimension grows, because the envelope's excess volume compounds along every axis: a blanket that is 10% too generous per dimension is roughly `1.1^d` too generous overall. In high dimensions plain rejection sampling becomes unusable, and that dimensional collapse is a standard motivation for entirely different sampling machinery. ## What to say out loud Give the accept rule, state that acceptance equals `1/M` and that `M` is the expected number of proposals per draw, diagnose the loose envelope as the cause, offer a tighter proposal or the inverse-CDF route as the fix, and confirm that the accepted sample is unbiased.