저번 주말은 바람은 많이 불었지만, 날씨는 정말 화창했다. 산책도 하고 점심도 먹을 겸, 딸내미를 유모차에 태우고 집 앞 산책로를 따라 꽤 걸어가서 온천천 카페거리에 도착했다.
예전과 달리 새로 오픈한 가게들이 많아져서, 전체를 한 바퀴 쭉 둘러보며 최고의 가게를 찾아 점심을 먹으려 했는데, 바람도 세고 꽤 걸어서 그런지 딸래미가 점점 짜증을 내기 시작했다.
카페거리를 끝까지 다 둘러본 후 가장 괜찮아 보이는 곳을 선택하는 게 최적이겠지만, 현실적으로는 적당히 탐색하고 딸래미의 투정이 심해지기 전에 적당한 곳을 골라야 했다.
그때 문득 이런 생각이 들었다. 전체를 다 탐색하지 못하는 상황에서, 언제 어떻게 선택을 해야 가장 좋은 결과를 얻을 수 있을까?
최적 정지 문제
집에 돌아와 퍼플렉시티에게 물어보니, 이 상황은 바로 ‘최적 정지 문제(Optimal Stopping Problem)’와 같다고 한다.
최적 정지 문제란 연속적으로 관찰되는 데이터나 사건들 중에서, 특정 시점에 결정을 내려야 할 때 최적의 선택을 보장하는 정지 시점을 찾는 문제다.
대표적인 예시로 ‘비서 문제(Secretary Problem)’가 있다.
비서 문제
100명의 지원자를 한 명씩 차례로 면접 본다.
면접 직후 채용 여부를 즉시 결정해야 하며, 한 번 탈락시킨 지원자는 다시 채용할 수 없다.
한 명을 채용하면 나머지 지원자는 더 이상 면접을 볼 수 없다.
어떻게 해야 최고의 지원자를 뽑을 확률이 가장 높을까?
최적 정지 이론에 따르면, 답은 ‘37’이다.
즉, 100명 중 처음 37명은 무조건 탈락시키고, 이후 38번째부터는 앞서 본 지원자들 중 최고보다 더 나은 사람이 나오면 바로 채용하는 것이 최적의 전략이다. 이 방법을 따르면 최고의 지원자를 뽑을 확률이 약 37%로, 이는 수학적으로도 증명되어 있다
왜 37%인가? (수학적 배경)
퍼플렉시티에게 물어본 결과 단순화한 증명은 아래와 같다고 한다.
처음 r명을 기준 집단으로 삼아 불합격시키고, 이후 기준 집단의 최고 순위보다 높은 후보자가 나타나면 선택한다.
최고의 후보자가 k번째에 있을 때 선택될 확률은 r/(k-1)이다.
전체 확률 P(r)은 모든 k에 대한 평균값이다. n이 충분히 클 때는 적분을...
