Understanding Rejection Sampling method

A visual representation in R

Rejection sampling is a computational technique whose aim is generating random numbers from a target probability distribution f(x). It is related to the general field of Monte Carlo methods, whose core is generating repeated random sampling to make a numerical estimation of unknown parameters.

Some words about Randomness

One might ask why a random variable with probability density f(x) cannot be easily generated by a computer algorithm. Well, the fact is that those latter are deterministic by nature, hence it is unfeasible to pretend randomness from them. Indeed, computer algorithms generate so-called pseudo-random numbers: those algorithms pick them from a ‘list of numbers’ which is huge, but ordered, in the same way, every time. Hence, the source of randomness is the starting point. You can easily visualize it if, when creating random numbers with any software (here, I’ll use R), you specify the starting point (called ‘seed’):

set.seed(123)
 sample(0:200,10,replace=T)

Output: 57 158  82 177 189   9 106 179 110  91
#let's generate other two samples, one without seed:

sample(0:200,10,replace=T)
Output: 192  91 136 115  20 180  49   8  65 191

#and one with the same seed as above:
 set.seed(123)
 sample(0:200,10,replace=T)

Output: 57…