2. A Simple Monte Carlo Program

• 주의 사항

1. 이 글은 RayTracing:The Rest of Your Life를 공부하며 작성한 글이다.
2. 모든 사진, 글은 RayTracing:The Rest of Your Life에서 가지고 왔다.
3. 영어 해석, 이론적으로 틀린 내용이 존재할 경우가 매우 크다. (지적해주시면 감사합니다.)
4. 글을 쓰는 능력이 매우 안좋으니 이해해주세요. 연습 중 입니다.

---

Estimating Pi

먼저 우리는 우리가 흔히 아는 $\pi$를 Monte Carlo Estimation을 사용하여 예측하는 실습을 진행하는 설명이 나온다. 여기서 나오는 MC program은 통계적 수치로 해서 answer을 추측해낸다.

Monte Carlo Estimation을 공부했던 기억으로 가진 Sample을 가지고 수렴하는 성질을 이용해서 값을 구해내는 방법으로 알고 있다.

그래서 이 Monte Carlo Estimation은 더 수행하면 할 수록 더 정확한 값을 획득할 수 있다. 이제 한번 우리가 예전에 배웠던 $\pi$를 계산해보자.

위의 사진처럼 사각형안에 원이 있다고 가정을 해보자. 그러면 우리는 사각형 안에 있는 point를 Random하게 뽑는다고 가정한다. 그러면 우리가 선택한 point들이 원에 있을 비율은 원의 넓이가 넓을 수록 증가한다. 더 정확하게 말하자면 사각형의 넓이와 원의 넓이의 비율이어야 한다. 즉 아래와 같이 나타낼 수 있다.

여기서의 $r$은 원의 반지름을 나타낸다. 우리는 위의 식으로 한번 실습을 진행해보자.

위와 같이 확률이 나오는 것을 확인할 수 있다. 하지만 우리가 아는 $\pi$는 3.14....이다. 조금 샘플 수가 부족한 것일 수도 있다.

sample수를 더 올려보니 조금 더 비슷하게 나오는 것을 확인할 수 있다.

Stratified Samples (Jittering)

우리는 위에서 꽤 빠르게 $\pi$와 비슷하게 값을 구해낼 수 있었다. 그리고 그것은 샘플 수가 많아질 수록 나중에 가면 조금 느리게 수렴하는 것을 확인할 수 있다. 이것은 Law of Diminishing Returns 의 예이다.

Law of Diminishing Reutrns 란 경제학의 용어로서, 일정한 영역에 대해서 추가로 샘플 수를 추가해도 값의 수렴하는 하는 정도를 못따라가는 것이라고 이해하면 좋다.

이것은 MC Estimation의 최악의 단점이라고 한다. 그래서 우리는 Random으로 샘플링을 하는 것 보다 stratifying하게 나누어서 샘플링을 하는 방법(종종 jittering 이라고 한다.)을 사용하여 수렴하는 정도를 완화할 수 있다. 아래의 사진 같이 하는 것이다.

그러면 우리는 위에서 실습한 코드를 바꾸어서 해보자.

#include "rtweekend.h"

#include <iostream>
#include <iomanip>

int main() {
    int inside_circle = 0;
    int inside_circle_stratified = 0;
    int sqrt_N = 10000;
    for (int i = 0; i < sqrt_N; i++) {
        for (int j = 0; j < sqrt_N; j++) {
            auto x = random_double(-1,1);
            auto y = random_double(-1,1);
            if (x*x + y*y < 1)
                inside_circle++;
            x = 2*((i + random_double()) / sqrt_N) - 1;
            y = 2*((j + random_double()) / sqrt_N) - 1;
            if (x*x + y*y < 1)
                inside_circle_stratified++;
        }
    }

    auto N = static_cast<double>(sqrt_N) * sqrt_N;
    std::cout << std::fixed << std::setprecision(12);
    std::cout
        << "Regular    Estimate of Pi = "
        << 4*double(inside_circle) / (sqrt_N*sqrt_N) << '\n'
        << "Stratified Estimate of Pi = "
        << 4*double(inside_circle_stratified) / (sqrt_N*sqrt_N) << '\n';
}

위에서 코드를 보면 알수 있듯이 grid를 만들어서 샘플링을 진행하는 것을 확인할 수 있고 조금 더 우리가 아는 $\pi$에 가깝게 나타낼 수 있다.