Monte Carlo Method_201701
Monte Carlo Method
Monte Carlo방법의 소개에 앞서, Monte Carlo가 무엇인지 알아보자. Monte Carlo는 Monaco의 동쪽에 위치한 도시이다. 도시의 전경은 아래 그림에서 볼 수 있듯이 탁 트이고 바다가 보이는 아름다운 도시다.
이렇게 아름다운 전경을 가진 도시이면서, 동시에 밤이되면, 세계적으로 유명한 도박의 도시가 되는 재미있는 도시이다.
출처: http://casinojourneys.com/monte-carlo
Monte Carlo 방법의 유래는 밤의 Monte Carlo에서 따온 것이 아닐까 싶다. Monte Carlo 방법이란, 풀기 어렵고 곤란한 것들을 직접 여러번 수행해 보거나, randomness를 이용해 결과를 얻고 분석하는 방법이다. 여러번 수행해야 하기에 주로 computer based algorithm을 사용하게 된다. 현재 Monte Carlo 방식은, 여러 복잡한 물리적 현상을 해석하는데도 쓰이고, 다차원 문제나 유체역학 그리고 AlphaGo와 같이 이후의 수를 확인해 보아야 하는 문제 (Monte Carlo Tree Search) 등에서 널리 쓰이는 방식중 하나이다.
단순히 말로만 표현해 놓으면, 이해가 잘 안되니, 실제 예제를 만들고 풀어보며 어떤 방식인지에 대해 생각해보자. 가장 대표적인 문제로는, 원주율 구하는 문제가 있다. 원주율을 Monte Carlo 방식을 사용 직접 구해보도록 하자. 반지름이 1인 원에 점을 마구 찍는다고 생각을 해보자. 실제로 사람이 점을 찍기에는 한계가 있으니 컴퓨터에게 이용 점을 1000개 아니 10000개를 찍도록 시켜보자. (컴퓨터에게 시키는 과정은 MATLAB을 사용하였다) 임의의 점 10000개를 위해 매트랩에서 기본적으로 제공하는 난수 생성 함수인 rand 함수를 이용 (난수가 정말 난수라 할수 있느냐와 같은 문제도 있긴 하지만 일단은 정말 난수라 가정하자) 10000개의 서로 다른 점을 찍었다. 결과는 아래의 그림과 같다.
그렇다면 이제 반지름이 1인 원을 위에 그리고, 원 안에 찍힌 점의 갯수는 몇개일 지 확인해보자. 원 안쪽에 위치한 점의 갯수는 7862개, 원 밖에 위치한 점의 개수는 2138개 라는 결과를 얻을 수 있었다.
이 결과를 이용해 어떻게 원주율을 구할 수 있을까 생각해보자. 전체 넓이는 4, 원의 넓이는 pi이다. 즉 전체넓이중에 원의 넓이가 차지하고 있는 비율은 pi/4라 할 수 있다. 그리고 점은 정말 균등하게 아무곳에나 찍혀있는 것이므로, 넓이에 비례해서 찍혔을 것이다. 즉 전체 넓이에 10000개가 찍힌 것이고, 원의 넓이에 7862개가 찍힌 것이다. 즉 점으로 생각해 봤을때 전체 넓이중, 원의 넓이가 차지하는 점의 양은 7862/10000이라 할 수 있다. 따라서 pi/4=0.7862라 할 수 있고, 이를 통해 pi=4*0.7862=3.1448 정도 될것이라 추론이 가능하다.
만일 더 정확한 pi값을 생각해 보고싶다면 simulation의 숫자를 늘리면 좀더 정확한 pi값에 근접할 것이다.
위 간단한 simulation을 하기 위한 code를 아래에 첨부한다. 직접 실행해 보면 쉽게 이해 할 수 있을 것이다.
<Code1>
theta=0:0.01:2*pi;
r = input('radius r: ') % radius
sim_n = input('simul: ') % simulation number
x_cir=r*sin(theta);, y_cir=r*cos(theta); % 반지름이 r인 원
x_axis = 2*r.*rand(1,sim_n)-r; % 임의의 x축 성분
y_axis = 2*r.*rand(1,sim_n)-r; % 임의의 y축 성분
plot(x_cir,y_cir,'Linewidth', 5)
hold on
plot(x_axis,y_axis,'.')
axis equal
xlim([-r r]), ylim([-r r])
length_or = sqrt(x_axis.*x_axis+y_axis.*y_axis); % 원점으로 부터의 거리
inside = length_or(length_or<=r); % 반지름 안에 해당하는 원소의 개수만 남긴다
in=length(inside);
out=sim_n-in;
ratio = in/sim_n;
area_by_montecarlo = ratio*r^2*4
이와같은 방법으로 주사위 던지는 문제도 해결할 수 있다. 주사위를 3번 던진 합이 과연 어떤 분포를 따를지 궁금하다고 하자. 그리고 어떤 방식으로 풀어야 할지도 모른다고 하자. 그렇다면 역시 가장 좋은 방법은 주사위를 여러번 던져보는 것이다. 하지만 직접 우리가 손으로 던지기엔 손이 매우 아플것으로 예상되므로, 역시 컴퓨터를 이용해 주사위를 굴리고 분포를 그려보도록 하자. 주사위를 3번씩 100번 굴려보도록 하자. 그때의 결과는 아래 그림과 같다.
뭔가 아직은 분포가 수학적 답과는 조금 거리가 있어보인다. 그렇다면 주사위를 더 굴려보도록 하자. 이번에는 3번씩 1000번 굴려보자. 1000번 굴린 결과는 아래와 같다.
이제 뭔가 점점 분포에 다가서는 것으로 보인다. 그렇다면 마지막으로 10000번 굴렸을때의 결과를 보자.
거의 좌우 대칭으로 실제 분포처럼 표현하고 있는것을 알 수 있다. 시작할때 아무것도 몰랐지만, 직접 주사위를 던져봄으로써 어떠한 분포가 펼쳐 질지 Monte Carlo 방식으로 알아본 것이다.
이와 같이 여러 풀기 어려운 문제들을 random한 input, 혹은 직접 해봄으로써 결과를 내는 방식이 Monte Carlo 방식이다.
<Code2>
clf, clear
n=input('시행횟수:');
impl=floor(6*rand(3,n)+1);
impl=sum(impl);
for i=3:1:18
num=sum(impl(:)==i)/n;
stem(i,num)
hold on
end
xlabel('세번 던진 주사위 눈의 합'), ylabel('빈도(나온 횟수/ 전체)')
xlim([3 18])