Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 11

Rejection sampling: the gamma example and the curse of dimension

To sample Ga(α, λ) with a non-integer shape, propose from Ga(k, λ′) with k = ⌊α⌋ (a sum of k exponentials) and accept a draw x with probability p(x)/(C q(x)), where C is the largest value of p/q. The comparison function Cq (red, dotted) touches the target (teal) at one point, and the acceptance rate is 1/C. The book uses λ′ = λ − 1, which is valid but loose; the rate that minimises C is kλ/α. The right panel shows the other lesson of the section: for a Gaussian target and a Gaussian proposal whose standard deviation is a factor ρ too large, the acceptance rate is ρ−D in D dimensions.

Shape α

Rate λ

Proposal rate λ′

Proposals n

Scale ratio ρ (right panel)

Try these

Left: n proposals, accepted draws in the histogram. Right: curve 1/C = ρ−D; dots are simulated acceptance rates of 4000 proposals each (D up to 30; below the axis range they are not shown).

In the lecture notes