몬테카를로와 라스베가스 알고리즘

몬테카를로 알고리즘은 많이들 알지만, 이걸 라스베가스 알고리즘이랑 묶어서 생각하는 사람은 아주 드물다. 이름에서 짐작하듯 둘 다 베팅과 보상에 기대는 알고리즘이다. 근데 나는 이 두 알고리즘이 결국 시간과 정보가 서로 얽혀 있는 우주의 물리적 구조를 슬쩍 보여 주는 것 같고, 시간과 정보를 서로 바꿔 쓸 수 있을지도 모른다는, 말로 설명하기 어려운 느낌이 든다.

몬테카를로 알고리즘은 무작위 샘플링으로 복잡한 문제의 대략적인 답을 구한다. 테이블에 다트를 던진다고 해 보자. 무작위로 백만 개를 던지면 다트는 거의 고르게 흩어진다. 한 점을 골라 원을 그리고 그 안의 다트를 세면, 원과 테이블의 면적 비율을 추정할 수 있다. 거기서 원주율을 추산하는 거다.

라스베가스 알고리즘도 비슷한데, 조금 더 정교하다. 좋은 예가 QuickSort다. QuickSort는 기준점을 무작위로 골라서 기준점보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누고, 왼쪽과 오른쪽 하위 집합에서 같은 과정을 반복한다.

여기서부터 재밌다. 두 경우 모두 무언가에 무작위로 베팅했는데, 지지리도 운이 없을 때 잃는 게 다르다.

• 몬테카를로에서 운이 나쁘면 틀린 결과가 나온다. 예를 들어 던진 다트가 우연히 전부 원 안에 들어갔다고 해 보자. 테이블과 원의 면적이 같다고 나올 거고, 완전히 틀린 답이 나온다. 빠른 실행 시간을 보장받는 대신 정확도에 리스크를 거는 셈이다.
• 라스베가스에서 운이 나쁘면 실행 시간이 훨씬 길어진다. 예를 들어 QuickSort가 매번 하위 집합에서 제일 작은 값을 고른다고 해 보자. 실행 시간이 어마어마할 거다. 높은 정확도를 보장받는 대신 실행 시간에 리스크를 거는 셈이다.

사실 빠르면서 정확하게 답을 찾는 건 우주의 P-NP 특성 때문에 불가능하다(고 알려져 있다. 아직까진...). 그래서 이 두 방법은 빠르고 정확한 결과에 다가가려는 근사치다. 근데 정확도를 높이려고 실행 시간을 내주고, 실행 시간을 줄이려고 정확도를 내줄 수 있다는 게 재밌지 않나?

더 재밌는 건 둘을 서로 바꿀 수 있다는 점이다. 몬테카를로를 특정 신뢰 수준에 닿을 때까지 계속 돌리면 라스베가스가 된다. 반대로 라스베가스 알고리즘을 일찍 멈추고, 틀렸을 수도 있는 결과를 받아들이면 몬테카를로가 된다. 이 과정이 NP 문제의 환원이랑 비슷해 보이는데, 아직 자세히 공부해 보진 않아서 어떤 연결점이 있는지는 잘 모르겠다.

그럼 이게 무슨 뜻일까?