[통계학] 몇번째 선본 여자를 결혼상대자로 고를 것인가?

친구랑 새로운 연구주제에 대해 토의하다가 통계학의 유명한 문제중의 하나인 "Secretary problem" 혹은 "Marriage problem"(결혼 문제)을 문제 해결에 적용하면 좋겠다라는 결론을 얻었다. 예전에 키즈 bbs에서 읽어본 적이 있었던 문제라서 한번쯤 내 연구 주제에 써먹어봤으면 했었는데, 마침 잘 된것 같다.

결혼 문제의 정확한 정의와 답들을 알아보기 위해 구글 서치를 해 본 결과 이 문제의 전문가는 Thomas S. Ferguson이라는 사실을 알아내었다. 오늘 발견한 이 연구자의 서베이 논문[1]과 웹 페이지[2]가 무척 마음에 든다.

결혼 문제는 최대 선볼 횟수가 정해져 있을때 (혹은 무한번 선을 볼수 있다고 할때) 몇번째 선본 여자를 결혼상대자로 고르는게 가장 최적인지를 통계학적으로 푸는 문제다. 가장 쉬운 형태의 문제는 다음과 같이 정의된다.

1. 딱 한명의 아내를 선택한다.
2. 선볼 회수 $n$이 고정되어 있다.
3. 선은 무작위 순서로 이루어지며, 한 여자가 특정한 순서에 나올 확률은 다른 여자가 특정한 순서에 나올 확률과 같다.
4. 몇 회의 선을 보면 그때까지 선본 여자들에 대한 선호도 순위를 동점자 없이 결정할 수 있다. 결혼상대자는 그때까지 얻은 순위만 보고 결정한다.
5. 한번 거절하면 다시는 그 상대를 만나볼 수 없으며, 남자가 결혼을 결정하면 여자가 항상 승락한다.
6. 당신은 최고의 아내감이 아니면 만족하지 못한다. (최고의 아내를 얻게 되면 1, 아니면 0이라는 결과값을 얻는다.)

문제를 쉽게 풀기 위해 남자의 선택 유형을 다음과 같이 제한하자. 처음 $r-1$번 동안은 무조건 거절하고, $r$번째부터 나오는 여자가 최고순위를 가질 때 선택하기로 한다면, $r$을 몇으로 고르는 것이 가장 좋을까?

$n$이 충분히 크다면 답은 $n/e$로서 $0.37n$이고, 최고의 신부감을 만날 확률은 $1/e=0.37$이다. $n$이 작을때는 해석적인 답은 없지만, 급수형태의 답은 있으므로, 계산기를 두드리면 답을 얻을수 있다.

이 문제는 고등학교 확률 지식으로도 풀리는 문제다. $r$이 주어졌을때, 최고의 신부감을 고를 확률 $P_n(r)$은 다음과 같다.

$P_n(1) = 1/n$ ==> 한번도 거절하지 않고 선택하면 n명 중에 한명을 무작위로 선택하는 것이니 1/n이다.

$P_n(r) = sum_{j=r}^n (1/n) ((r-1)/(j-1))$
==> $r-1$번째까지는 이미 거절했으니, $r$번째부터 최고의 상대를 고를 확률을 계산하면 된다. $r$번째에 고른 상대가 최고 순위를 확률은 그냥 $1/n$이다. 그리고, $r+1$번째 고른 상대가 그러할 확률은 $1/n times (r-1)/r$인데, 이는 $r$번째 만난 상대는 반드시 $r-1$번째까지 만난 최고의 상대보다 순위가 낮아야 하기 때문이다 ($r-1$번째 상대까지를 순서대로 나열하고, $r$번째 상대를 이들 사이에 위치시킬때, 이 상대는 제일 오른쪽 끝자리를 제외하고는 어디에 넣어도 이 조건을 만족시킨다.) 비슷한 방법으로 $r+2,r+3,...$에 관한 확률을 구할 수 있다.

[1] T.S.Ferguson, "Who Solved the Secretary Problem?," Statistical Science, Vol. 4, No. 3, Aug. 1989, pp. 282-289.
[2] http://www.math.ucla.edu/~tom/Stopping/Contents.html