얼마전 거꾸로가는 오-유 프로세스 이야기를 들고왔던 수학맨입니다.

오늘도 재미난 확률문제를 들고왔습니다. 꽤 잘 알려진 문제긴 합니다만 뭐 암튼.

최적멈춤문제, 영어로는 Optimal stopping.. 보다는 보통 Secretary problem 이라고 알려진 문제인데요, 이런 문제입니다.

1. n명과 순차적으로 소개팅을 합니다. 목표는 최고의 파트너를 찾는 것입니다!

2. 각각의 상대방을 만날 때 어떤 식으로든 수치화 할 수 있는 점수를 매길 수 있습니다. 점수의 분포는 당연히 소개팅 순서와 독립적입니다.

3. 우리는 신사이므로 썸을 타면서 다음 소개팅을 나가지 않습니다. 즉 직진하기로 했다면 남은 소개팅은 모두 취소됩니다.

4. 지나간 상대에게 질척이는 것은 좋지 않으므로 한 번 거절한 상대에게 다시 연락할 수 없습니다.

"최고의 파트너는 너님한테 관심이 없을텐데요" 같은 명치 강타는 접어두고, 왜 이것이 어려운 문제냐면

1. 초반에 결정할 경우: 지금 만난 사람이 아무리 좋아보여도, 남은 사람이 많다면 더 좋은 사람이 나타날 수 있음.

2. 후반에 결정할 경우: 전에 만났다가 거절한 상대방보다 나은 사람이 다시는 나타나지 않을 수 있음.

이 둘 사이에서 밸런스를 잡아야하기 때문입니다.

(k-탐색 전략)

전략적으로 접근해봅시다. 

1. 우리는 처음 k번의 소개팅 상대를 그냥 다 거절할겁니다. 아직은 사람을 배워가는 과정이니까요. 그리고 그 동안 만났던 사람들의 점수 중 가장 좋았던 사람의 점수를 기준점수로 정합니다.

2. 그리고 남은 n-k 번 동안 만남을 진행하면서 기준을 넘는 사람이 있다면, 바로 고백을 박는 겁니다.

최적의 k 값은 이 전략으로 n명중 최고의 파트너 α 를 만날 수 있는 확률이 최대가 되는 값일 겁니다.

(k-탐색 전략의 성공 확률)

 - α 가 몇 번째 소개팅 상대일지는 독립적이므로, α를 i 번째로 만날 확률은 단순히 경우의 수를 따져서 1/n 입니다.

 - α 가 1~k 에 있을 경우엔 안타깝지만 무조건 실패니까 생각할 필요조차 없습니다.

 - α 가 i = k+1 ~ n 번째 상대일 경우, 일단 α를 만나면 무조건 합격이긴 합니다. (α는 최고니까) 그렇기 때문에 k+1 부터 i-1 까지 만난 상대가 모두 불합격이기만 하면 됩니다. 이 확률을 대체 어떻게 구하나 싶은데요 (모든 순열을 고려??), 잘 생각해보면 i-1 개의 숫자 중에서 가장 큰 숫자가 k 번째 안에 있으면 됩니다. 순서와 점수는 독립이라고 했으니, 이 확률은 단순히 k / i-1 이지요.

마지막에 인덱스를 하나씩 밀어서 예쁜 1/i 를 만들어봤습니다. 이제 주어진 n에 대하여, 모든 k에 대한 값을 계산하고 최적의 k를 찾을 수 있습니다.

(n이 매우 클 때의 최적의 비율 x)

이 식은 사실 다음 적분의 구분구적법 표현 (그리고 x = k/n 은 전체 풀 중에서 탐색을 할 인원의 비율) 이 됩니다.

k/n 부터 n-1/n 까지, i/n 에서 폭이 1/n 이고 높이가 1/t = n/i 가 되니까 빨간 부분의 넓이가 1/i 이지요.

그래프는 위와 같습니다. 그리고 미분을 통해 정확한 최대값을 1/e = 0.367879.... 에서 가짐을 알 수 있죠.  이 전략의 성공 확률인 p값 역시 똑같은 1/e 입니다.

결론적으로 n이 매우 크다면, 전체의 약 36.8% 를 먼저 탐색하는 전략을 통해서 최적의 후보자를 찾을 수 있다는 것이 결론입니다.

n이 작을 경우에는 반드시 그렇지는 않습니다. 위에서 보시다싶이 합을 적분으로 근사하려면 n이 커야 하죠. 예를들어 n = 10 일 경우 4가 아닌 3이 최적의 숫자랍니다.

(Discussion, remarks)

1. 최적화 문제는 항상 어떤 objective function 을 설정하는가가 중요합니다. 위 문제의 경우 "최고의 파트너 알파를 찾으면 성공, 아니면 무조건 다 실패" 로 세팅을 한 경우구요, 평균점수라든가, 혹은 상위 몇% 이내면 OK, 아니면 상위 1%까진 100점, 5%까지 70점, 이런 식으로 구간별 차등 점수를 준다고 하면 또 다른 전략이 나올 수도 있습니다.

2. 이 문제는 강화학습, Reinforcement learning 에서 말하는 exploration vs exploitation 과 비슷한 맥락으로 느껴지기도 합니다.  RL 은 알파고나 다른 게임 AI 처럼 주어진 상황을 보고 최적의 선택을 하는 알고리즘인데, 트레이닝 과정에서 "아직 안 해본 선택" 과 "전에 해봤는데 잘 된 것 같은 선택" 중에 골라서, 아직 안 해본 좋은 선택이 있나 알아보거나, 예전에 했던게 진짜 좋은 선택이었던건지 확인하는 학습을 진행해야합니다.  저 둘 사이의 최적의 비율은 어떻게 될까요? 이때 "최적" 이라함을 어떤 방식으로 정의할까요?

3. 예전에 Random process 수업시간에 교수님이 그냥 재미로 해준 강의였는데, 얼마전에 9개월간 블라인드 셀소 나갔다는 의사분 썰 보고 생각나버렸습니다. 첫 사람을 별거 아닌 이유로 거절한 이후로 다시는 제대로 된 사람을 못 만났다는 ㅋㅋㅋㅋ