3월 8일 - optimal stopping

더 물색해야 하나 채택해야 하나. 언제 물색을 그만두고 채택해야 하나. 예를 들어 당신이 비서를 고용하려고 인터뷰를 한다고 생각해보자. 만약 너무 일찍 고용하면 나중에 나타날지도 모르는 더 좋은 비서를 놓칠지 모른다. 반면 계속 물색만하다보면 가장 나은 비서를 지나쳐버릴지도 모른다. 이럴 경우 어떻게 해야 가장 좋은 비서를 고용할 확률이 높을까. 

컴퓨터 프로그래밍에 사용되는 수학적 알고리즘 optimal stopping에 따르면, 확률상 가장 좋은 방법은 이것이다. 첫 37%까지는 괜찮은 사람이 나타나도 고용하지 않고 물색만 하다가 37% 이후에는 지금까지 만난 사람보다 괜찮은 사람이 나타나면 바로 고용한다. 이렇게 하면 가장 괜찮은 사람을 고용할 확률이 (신기하게도 똑같은 비율인) 37%라 한다. 

이 책에 나온 재밌는 예시가 있다. 만약 20살에서 40살 사이에 결혼을 하겠다고 맘먹은 사람이 있다고 치자. (숫자는 내가 더 간단하게 바꿨음) 이 사람은 20살때부터 괜찮은 배우자감이 있는지 찾기 시작했다. 이 optimal Stopping에 따르면 27.4살까지는 (20-40살의 37%에 해당하는) 이성을 만나고 사귀고 탐색하기만 하다가 27.4살부터 지금까지 본 사람보다 괜찮은 사람이 나타나면 결혼한다. 그렇게 한다면 내가 20살에서 40살사이 만난 이성 중 최상의 사람과 결혼할 확률이 37%가 된다. 이게 확률적으로 최상의 전략이다.

하지만 물론 27.4살 이후에 만난 사람이 무조건 나의 결혼신청에 응할리는 없다. 결혼신청에 응할 확률을 반반이라고 가정한다면 optimal stopping은 25%의 시점, 즉 25살 이후에 만난 가장 나은 사람에게 결혼신청을 하는게 가장 확률적으로 좋은 선택이다.

컴퓨터 프로그래밍에 사용되는 알고리즘을 적용해  우리가 흔히 일상에서 겪는 의사결정의 가장 적절한 선택방법을 탐색하는 책 “Algorithms to Live By”을 읽고 있다. 이는 첫 장에서 가장 기억에 남는 내용을 정리한 것이다. Optimal stopping의 다양한 변형과 응용도 더 자세히 설명돼있다. 저자의 “똑똑함”이 막 느껴지는 책이다.