1. 몬테칼로 알고리즘, 몬테칼로 시뮬레이션
ㅇ 불확실한 상황 하에서, 난수를 이용한 문제 해결법 또는 시뮬레이션 방식
- '결정론적인 해답'을 얻기 어려운 '복잡한 문제'를, '무작위성'(확률통계)를 이용해 풀어봄
. 특정 확률분포로부터, 무작위로 난수를 수없이 발생시켜, 근사적인 해를 구함
ㅇ 명칭의 유래 : 암호명
- 맨해튼 프로젝트(원자폭탄 개발)에 참여했던, 존 폰 노이만과 스태니슬로 울람이,
. 중성자 확산 문제를 풀기 위해 고안
- 몬테칼로 (Monte Carlo) : 모나코 몬테카를로 지역에 위치한 유서 깊은 도박장 겸 공연장
. 난수 기반 계산을 도박에서의 "무작위성"에 비유하는 의미로, 알고리즘 암호명에 이를 붙임
ㅇ 수학적 아이디어
- "복잡한 문제" → "평균값 문제로 변환" → "표본평균으로 근사"
. 어떤 값 θ를 직접 계산하기 어려울 때, (단 한 번의 과정으로 정확한 해를 구하기 어려울때)
. 확률변수의 기댓값 형태로 변환 후,
. 수많은 난수 샘플들의 평균으로 근사
- 수학적 표현
[# E[f(X)] \approx \frac{1}{N} \sum_{i=1}^{N} f(x_i) #]
. {#x_i#} : 확률분포에서 생성된 난수 샘플
. {#N#} : 반복 횟수
.. N → ∞ 이면, 실제값에 수렴 (대수의 법칙)
ㅇ 특징
- 해석적 해가 없어도 적용 가능
. 정확한 해가 아니라 확률적 근사값을 얻어냄
- 수렴 속도 : O(1/N) (느리지만 안정적)
. 정확한 답을 보장하는 알고리즘들이 너무 많은 시간,복잡성이 요구
. 비록 근사적인 확률적 답 만을 주지만, 시간적 보장은 가능함
- 단순성 : 알고리즘 구조가 비교적 단순
. 특히, 반복 계산이 많아, 병렬 컴퓨팅에 적합
- 차원이 높아질수록 (고 차원 적분 등), 오히려 유리