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

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

경고

1년 이상 지난 글입니다. 정보가 오래되었을 수 있습니다.

많은 사람들이 몬테카를로 알고리즘을 알지만, 아주 소수만이 라스베가스 알고리즘과 연결지어 생각한다. 이름에서 짐작할 수 있듯이 둘은 모두 베팅과 보상을 기반으로 한다. 하지만 그럼에도 나는 이 두 알고리즘이 결국에는 시간과 정보가 서로 얽혀 있는 우주의 물리적 구조를 암시하며 시간과 정보는 서로 교환할 수 있을지도 모른다는 형언할 수 없는 느낌이 든다.

몬테카를로 알고리즘은 무작위 샘플링을 사용하여 복잡한 문제에 대한 대략적인 해를 구한다. 테이블에 다트를 던진다고 상상해보자. 무작위로 백만 개의 다트를 던지면 다트는 거의 균일하게 흩어질 것이다. 한 점을 선택해, 원을 그린 다음, 그 속 다트를 세어보면 원과 테이블의 면적 사이의 비율을 추정할 수 있을 것이다. 거기에서 원주율을 추산하는 것이다.

라스베가스 알고리즘도 비슷하지만, 조금 더 정교하다. 좋은 예로 QuickSort을 들 수 있다. QuickSort는 기준점을 무작위로 선택해, 기준점보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 나누고, 왼쪽 및 오른쪽 하위 집합에서 동일한 프로세스를 반복하는 것이다.

여기서 흥미로워진다. 우리는 두 경우 모두 어떤 무언가에 무작위하게 베팅했지만, 지지리도 운이 없을 때 손해보는 것이 다르다는 것이다.

  • 몬테카를로에서 운이 나쁘면 잘못된 결과를 얻는다. 예를 들어 던진 다트가 우연히 모두 원 안에 들어갔다고 상상해보자. 테이블과 원의 면적이 같게 나올 것이고, 완전히 잘못된 결과가 나온다. 즉 빠른 실행 시간을 약속 받는 대신 정확도에 리스크를 거는 것이다.
  • 라스베가스에서 운이 나쁘면 실행 시간이 훨씬 더 오래 걸린다. 예를 들어 QuickSort 매번 하위 집합에서 가장 작은 값을 선택한다고 상상해보자. 실행 시간이 어마어마할 것이다. 즉 높은 정확도를 약속 받는 대신 시간에 실행 시간에 리스크를 거는 것이다.

사실, 빠르고 정확하게 정답을 찾는 것은 우주의 P-NP 특성으로 인해 불가능하다(고 알려져 있다. 아직까진...) 따라서 이 두 가지 방법은 빠르고 정확한 결과를 얻기 위한 근사치이다. 하지만 정확도를 높이기 위해 실행 시간을 희생하고 실행 시간을 개선하기 위해 정확도를 희생할 수 있다는 점이 흥미롭지 않은가?

더 흥미로운 점은 둘이 사실은 교환 가능하다는 점이다. 몬테카를로에서 라스베가스까지 특정 신뢰 수준에 도달할 때까지 몬테카를로를 반복적으로 실행하여 몬테카를로를 라스베가스로 변환할 수 있다. 라스베가스에서 몬테카를로로 변환할 때는 라스베가스 알고리즘을 조기에 중지하고 잠재적으로 잘못된 결과를 받아들일 수 있다. 이 과정은 마치 NP 문제의 환원과 유사한 특성을 보이는 듯 한데, 아직 자세하게 공부해보진 않아 어떤 연결점들이 있는지는 불확실하다.

그렇다면 이것은 무엇을 의미할까?

어쩌면 시간과 정보는 동일한 물리적 속성이며, 우주의 정교한 기하학적 성질 때문에 두 개의 다른 값으로 관측되고 있는지도 모른다. 하지만 아직 입증되지 않았으며, 어쩌면 P-NP 문제에 대한 해답이 될지도 모른다.

Backlinks (0)

No backlinks found.