Editing Rejection sampling (section)

== Advantages over sampling using naive methods ==
Rejection sampling can be far more efficient compared with the naive methods in some situations. For example, given a problem as sampling <math display="inline">X\sim F(\cdot)</math> conditionally on <math>X</math> given the set <math>A</math>, i.e., <math display="inline">X|X\in A</math>, sometimes <math display="inline">X</math> can be easily simulated, using the naive methods (e.g. by [[inverse transform sampling]]):
* Sample <math display="inline">X\sim F(\cdot)</math> independently, and accept those satisfying <math>\{n\ge 1: X_n\in A\}</math> 
* Output: <math>\{X_1,X_2,...,X_N:X_i\in A, i=1,...,N\}</math> (see also [[truncation (statistics)]])
The problem is this sampling can be difficult and inefficient, if <math display="inline">\mathbb{P}(X\in A)\approx 0</math>. The expected number of iterations would be <math>\frac{1}{\mathbb{P}(X\in A)}</math>, which could be close to infinity. Moreover, even when you apply the Rejection sampling method, it is always hard to optimize the bound <math>M</math> for the likelihood ratio. More often than not, <math>M</math> is large and the rejection rate is high, the algorithm can be very inefficient. The [[Natural exponential families|Natural Exponential Family]] (if it exists), also known as exponential tilting, provides a class of proposal distributions that can lower the computation complexity, the value of <math>M</math> and speed up the computations (see examples: working with Natural Exponential Families).