Rejection Sampling with Vertical Weighted Strips
Rejection sampling is a classical algorithm (Neumann 1951) to generate variates from a target distribution where a constructive sampling method—e.g., by composing other random variables—may not be apparent. A benefit of rejection sampling is that accepted draws follow the target distribution exactly. However, coming up with a good proposal for rejection sampling can take some creativity. A poor choice can result in extremely low acceptance rates where practically no draws are accepted from a very large number of candidates.
Raim, Livsey, and Irimata (2024+) explore an approach to construct proposals by regarding the target as a weighted density and majorizing the weight function. This yields another weighted density whose unnormalized form can be used as an envelope in the acceptance ratio. If designed consciously, the normalized form can also be used to draw candidate variates to complete the rejection sampler. An improved proposal can be obtained by partitioning the support and majorizing within each region. Here the proposal is a finite mixture. The method is referred to as “vertical weighted strips” because it can be regarded as an extension of the vertical strips method (Devroye 1986, chap. VIII; Martino, Luengo, and Míguez 2018, sec. 3.6), with the weighted form introducing an additional degree of flexibility for algorithm development.