Summary

• Rejection Sampling은 Sampling 기법의 하나로, 특정 Distribution을 따르는 수를 임의로 생성하는 기법이다.
• Proposal Distribution $g(x)$에 Scale Factor M을 곱해서 $f(x)$을 덮은 다음(envelope) 여기에 Uniform Distribution을 곱해서 각 수의 발생확률을 균일하게 가져간다.
• $u * M* g(x) \le f(x) → u \le {f(x) \over {M*g(x)}}$
• 이 식은 Decision의 기준인데 $u$가 Uniform Distribution으로 모든 $x$에 대해서 균일한 확률을 가지고 있다면, 적어도 ${f(x) \over {M*g(x)}}$는 균일확률보다 크거나 같을 수 밖에 없을 것이다. 존재하기 때문이다.
• M은 $g(x)$가 $f(X)$에 아주 가까울 수 있도록 조절하기 위한 factor이다.
• 쉽게 생각하면 Target Distribution을 Cover할 수 있는 Distribution을 Propsoal Distribution으로 한 다음에, 이를 가지고 Density를 비교하면서 겹치는 영역에서 Sampling을 하는 방식이다.

# Target Function
def f(x):
	return 6*x*(1-x)
# Proposal Function
def g(x):
	return x/x
def random_g(n:int):
	return np.random.uniform(0,1,n)

M=1.5 #constant
n=1000 #size of the sample we want to draw from f(x)

def acceptance():
	n_accept=0
	final_sample = np.zeros(1001)
	while(n_accept<1000):
		x = random_g(1)
		u = np.random.uniform(0,1,1)
		if (u*M*g(x)<=f(x)):
			n_accept=n_accept+1 
			final_sample[n_accept]=x
	return final_sample
vals = acceptance()

References

• Understanding Rejection Sampling method