A-R Algorithm

acceptance-rejection algorithm

이상한 분포에 균일 분포를 씌운 뒤 모래를 뿌려서 안쪽에 있는 것만 accept하고 바깥 쪽에 있는건 reject하는 정도만 알고 있었고, 자세한 logic은 몰랐는데 이번에 알게 되었다.

​

가령,

 

아래와 같은 이상한 pdf가 있고 저 분포를 따르는 data를 sampling하고 싶다고 가정하자.

그러나, 우린 저 pdf의 분포를 모르기 때문에 근사시키는 방법을 사용해서 sampling을 시도해야 한다.

그래서 이 과정에서 균일 분포 등 우리에게 친숙한 분포를 사용한다.

 

step1) 저 x축에서 unif(0,1)을 따르는 data들을 10000개 정도 sampling한다.

x축에 표시해둔 눈금이 unif(0,1)에서 뽑아낸 data point라고 생각하자.

균일분포에서 추출한 것이므로 data들이 고르게 분포돼 있는 걸 알 수 있다.

 

step2) 저 별표를 x축에서의 fixed point라고 하고, fixed point를 기준으로 y축도 마찬가지로 unif(0,a)를 따르는 data point들을 10000개 정도 sampling한다.​

 

step3) then, 저런 식으로 data가 sampling 되는 데, 이때 초록색 부분만 accept하고 나머지 핑크색 부분은 reject한다.

 

이런 식으로 눈금 쳐진 모든 x축의 data point들에 대해서 이 process를 수행하고, 선택된 data point들의 histogram을 그리면,

 

 

이런식으로 그려진다.

그리고 최종적으로 이 data들의 표본평균을 구하여 원래 분포의 평균을 대체하면 된다.