최고의 배우자 찾기

일상생활 중에 여러 개 중에서 하나를 선택해야 되는 경우가 많다. 필기구를 사는 간단한 것에서부터 컴퓨터나 자동차를 사는 경우까지 다양하다. 선택할 때에 보통 선택 대상에 대하여 필요한 정보를 조사한 후, 비교, 평가하고 적절한 선택 기준에 따라 선호도가 가장 높은 것으로 최종 결정하게 된다. 이때 선택 대상 전체의 정보가 모두 주어진 경우에는 전체를 비교한 후에 결정하면 되지만, 일부 대상에 대한 정보가 주어지지 않은 경우에는 최선의 것을 선택하는 일이 결코 쉬운 일이 아니다.

그런데 일상생활 중에는 불완전한 정보 속에서 중요한 결정을 내려야 되는 일이 적잖이 있다. 예를 들어, 배우자를 선택하는 일이 그렇다. 단순화시켜 생각하면, 배우자를 선택할 때 이성을 한사람씩 만나서 일정 기간 동안 사귀고, 그 이성을 배우자로 선택할 것인지 아닌지를 결정하게 된다. 이때 상대가 모든 면에서 완벽하게 마음에 들면 별 고민을 하지 않겠지만, 마음에 드는 면도 있고 마음에 들지 않는 면도 있는 경우에는, 지금의 이성을 배우자로 결정해야 되는지 아니면 더 마음에 드는 이성을 만나기 위해 지금의 이성과 헤어지고 다른 이성을 만나도록 해야 되는지 고민하게 될 것이다.

이와 같이 불완전한 정보 속에서 선택해야 되는 경우에 어떤 좋은 방법이 있는지에 대하여 알아보도록 하자.

최고의 배우자 선택하기

예를 들어 어떤 여자가 남자 100명 중에서 1명을 배우자로 선택한다고 생각해보자. 여자는 남자를 1명씩 순서대로 만나며, 만나서 일정기간 사귄 후에 그 남자를 배우자로 선택하거나 선택하지 않는다. 선택할 경우에는 그 남자와 결혼하고, 선택하지 않을 경우에는 그 남자를 두 번 다시 만날 수 없으며, 다음 남자를 만난다. 이 때, 여자가 어떻게 하는 것이 가장 좋은 남자를 배우자로 선택할 수 있는 전략일까?

위의 문제는 비서문제^{the secretary problem}라고 불리는 다음 문제와 같은 문제이다.

이 문제는 다음과 같이 정리할 수 있다.

1. \(n\)장의 카드에 \(n\)개의 서로 다른 수 \({ a }_{ 1 }\), \({ a }_{ 2 }\), \(\cdots \), \({ a }_{ n }\)이 적혀 있고, \({ a }_{ 1 }>{ a }_{ 2 }>\cdots { >a }_{ n }\)이라 하자.
2. 이 카드들을 숫자가 안 보이게 뒤집어서 섞은 후 무작위로 한 줄로 나열하였다.
3. 앞에서부터 \(k-1\)장을 뒤집어 보고 이 중 가장 큰 수를 \(M\)이라 하자. 남은 카드를 순서대로 한 장씩 뒤집어 나가다가 \(M\)보다 큰 수가 나타나면 그 카드를 선택한다.
4. 이렇게 할 때 가장 큰 수 \({ a }_{ 1 }\)이 선택될 확률이 최대가 되도록 하는 \(k\)의 값은 얼마인가?

예를 들어 \(n=4\)인 경우를 생각해보자. 편의상 4장의 카드에 적힌 숫자가 \({ a }_{ 1 }=4\), \({ a }_{ 2 }=3\), \({ a }_{ 3 }=2\), \({ a }_{ 4 }=1\)이라 하자. 4개의 숫자가 나열될 수 있는 모든 가능한 경우에 대하여, \(k=2\)와 \(k=3\)일 때 최댓값을 선택할 경우를 따져보면 다음과 같다.

위 표로부터 \(k=2\)일 때, 최댓값이 선택될 확률은 \(\frac { 11 }{ 24 } \)이고, \(k=3\)일 때, 최댓값이 선택될 확률은 \(\frac { 10 }{ 24 } \)임을 알 수 있다.

이제 확률이 최대가 되는 \(k\)의 값을 구해보자. 우선 \(j\)를 \(k\le j\le n\)인 정수라 하자. \(j\)번째 숫자가 최댓값일 확률은 \(\frac { 1 }{ n } \)이다. 그리고 처음 \(j-1\)개의 숫자들 중에서 최댓값이 처음 \(k-1\)개 중에 있을 확률은 \(\frac { k-1 }{ j-1 } \)이다. 그러므로 \(j\)번째에 최댓값 \({ a }_{ 1 }\)을 선택할 확률은 \(\frac { k-1 }{ n(j-1) } \)이다. 따라서 \(k-1\)장을 버리는 전략에서 최댓값 \({ a }_{ 1 }\)이 선택될 확률 \({ \phi }_{ n }(k)\)는 다음과 같다.
\begin{align*} \phi_{n}(k)&=\sum _{ j=k }^{ n }[j\text{번째에 최댓값이 선택될 확률}] \\&=\sum _{ j=k }^{ n }{ \frac { k-1 }{ n(j-1) } } =\frac { k-1 }{ n } \sum _{ j=k }^{ n }{ \frac { 1 }{ j-1 } }\quad \cdots \quad (1)\end{align*}  주어진 \(n\)에 대하여 식 (1)의 값이 최대가 되도록 하는 \(k\)의 값을 구하면 된다. 우선 \(n\)이 충분히 클 때, \(r\)의 근삿값을 구하기 위해 \(n\)이 무한대로 커진다고 하자. \(x=\frac { k }{ n }\)이라 하면, 위의 식 (1)은 다음과 같이 된다. \[{ \phi }_{ n }(k)=-x\ln { x } \quad \cdots \quad (2)\] 이때, 미분을 이용하여 식 (2)의 함숫값이 최대가 되도록 하는 \(x\)의 값을 구하면 \(x=\frac { 1 }{ e }\)이고, 그때 최댓값이 선택될 확률은 \({ \phi }(\frac { 1 }{ e } )=\frac { 1 }{ e } \approx 0.3679\)이다. 따라서 \(n\)의 값이 클 때, 전체의 약 37%를 그냥 보내는 전략이 \({ a }_{ 1 }\)을 선택할 확률이 최대가 된다.

식 (1)에 부등식을 적절히 적용하여 계산하면, \({ \phi }_{ n }(k)\)의 값이 최대가 되도록 하는 \(k\)의 값을 \({ k }^{ \ast }\)라 할 때 다음 부등식을 만족함을 보일 수 있다.
\[\frac { n-\frac { 1 }{ 2 } }{ e } +\frac { 1 }{ 2 } -\frac { 3e-1 }{ 2(2n+3e-1) } \le { k }^{ \ast }\le \frac { n-\frac { 1 }{ 2 } }{ e } +\frac { 3 }{ 2 }\quad \cdots \quad (3)\] 여러가지 \(n\)의 값에 대한 \({ k }^{ \ast }\)의 값이 <표 2>에 제시되어 있다.

위의 결과를 활용하면 가장 마음에 드는 배우자를 선택하는 전략은 다음과 같다.

예를 들어 어떤 사람이 앞으로 자신이 만날 수 있는 이성이 대략 50명 정도일 것으로 예상한다고 할 때, 위의 표에서 \(n=50\)일 때, \({ k }^{ \ast }\)의 값이 19이므로 18명의 이성은 어느 정도 사귄 후에 선택하지 않고 헤어진다. 그 후 19명 째 이성부터는 그 이성이 그 이전에 만났던 이성 중 어떤 이성보다도 더 좋으면 배우자로 선택하고, 그렇지 않으면 헤어지고, 다른 이성을 만난다.

대략 전체 인원수의 37% 정도의 사람은 만나면서 연애의 감(?)을 익히고, 일생의 동반자에게 필요한 자신의 기준을 설정하도록 한다. 그리고 그 이후의 사람 중에서 그때까지의 사람보다 더 좋은 사람을 만나게 되면 무조건 선택하는 전략이 최고의 배우자를 선택할 가능성이 가장 큰 전략이다.

비서 문제의 역사

이 문제의 기원은 명확하지 않다. 1960년 2월에 가드너^{Martin Gardner}가 Scientific American에 쓴 글에서 이 문제가 처음으로 출판된 매체에 알려졌고, Scientific American 1960년 3월에 이 문제의 풀이의 개요가 게재되었다. 그리고 1963년에 American Mathematical Monthly에 문제가 실렸고, 1964년에 풀이가 게재되었다. 그런데 Mosteller는 1955년에 이 문제를 Andrew Gleason으로부터 배웠다고 하니 이 문제의 기원에 대해서는 좀 더 확인되어야 할 것들이 있다. 어쨌거나 이 문제가 출판될 때까지 많은 사람들이 이 문제를 알고 있었던 것은 분명한 것으로 보인다.

독일의 천문학자 케플러^1571-1630의 아내는 1611년에 콜레라로 사망했다. 그의 첫 번째 결혼은 중매결혼이었는데 결혼 생활이 전적으로 행복했던 것은 아니었던 것 같다. 그래서 그는 두 번째 결혼 상대자는 자신이 결정하기로 마음먹었다. 그는 아내 후보와의 면접을 마련해두고, 11명 이상의 후보 중에서 아내를 선택하기로 하였다. 2년여 동안 많은 노력과 정열을 쏟아 면접을 본 후 케플러가 가장 선호했던 후보는 4번째 사람이었다. 그러나 케플러가 11명의 후보를 모두 면접하느라 시간이 너무 흐른 뒤였고, 그녀는 케플러의 제안을 거절했다. 최종적으로 케플러와 결혼한 후보는 5번째 후보였다.

케플러가 만약에 11명의 후보들에 대하여 위의 배우자 선택 전략을 사용하였다면 어떻게 되었을까? 안타깝게도 그렇게 했더라도 4번째 후보가 아내로 선택되지는 않는다. 왜냐하면, 위 전략에서 후보가 11명일 때, 면접하고 그냥 보내는 사람의 수가 4명이기 때문이다. 이런 점에서 4번째 여성은 수학적으로 보더라도 케플러의 운명의 여인은 아니었다고 할 수 있다. 그러나 케플러의 전기 작가들에 따르면 케플러의 두 번째 결혼 생활은 첫 번째보다 더 행복했다고 하고, 케플러는 두 번째 결혼 후에 뉴턴의 만유인력의 법칙의 경험적 토대를 제공하는 4개의 큰 업적을 이루었다. 그리고 두 번째 아내는 1620년에 케플러의 어머니가 마녀로 화형에 처해지는 것을 구했다고 한다. 최고점의 배우자와 결혼하지 못했다고 해서 너무 크게 실망할 필요는 없는 것 아닌가 싶다.

실용적 선택법

위의 결과는 앞으로 만날 사람들에 대한 정보가 전체 인원수 밖에 없는 상황에서 어떻게 그 상상 속의 명단 가운데 제일 좋은 사람을 선택할 수 있는가 하는 실용적이지만 매우 어려운 문제에 대한 해법의 실마리를 제시한다는 점에서 값진 결과이다.

그러나 실제로 이 정리를 적용하려고 할 때에는 뜻밖의 심각한 문제에 부딪히게 된다. 위 정리에서 최댓값이 되도록 하는 값은 37%인데, 몇 명을 그냥 보내야 되는지를 알기 위해서는 앞으로 만나게 되는 이성이 모두 몇 명인지, 즉 \(n\)의 값을 알아야 된다. 그런데 불행히도 자신이 앞으로 몇 명의 이성을 만나게 될지를 알 수가 없다. 그래서 위 정리를 실제 상황에서 사용하기에 곤란한 점이 있다.

최고의 배우자를 선택하기 위한 37% 전략이 앞으로 만날 이성이 몇 명인지 정확하게 알지 못한다는 문제점 때문에 실제로 적용하는 데에 한계가 있기는 하지만, 어느 정도 수긍할 만한 추산과 감각으로 적용할 수 있는 여지가 있고, 또 성공한다면 최고의 배우자를 선택하게 된다는 점에서 매우 매력적인 방법이다. 그러나 이 전략은 결정적인 문제점을 품고 있다. 그것은 이 방법의 성공확률이 37%로 절반도 안 되는 낮은 확률이라는 점이다. 즉, 위의 37% 전략으로 배우자를 선택하는 시도를 했을 때, 최고의 배우자를 선택하는 데에 성공하는 것은 37%, 즉, 3번 중에 1번 정도뿐이라는 점이다. 면접을 통해 아내를 정했던 케플러가 이 전략을 사용했다고 해도 최고점의 배우자를 선택하지 못했다는 역사적인 사례도 있다. 이런 낮은 성공확률은 많은 사람들로 하여금 실제 상황에서 이 전략을 실행하기를 주저하게 만든다. 성공할 확률보다 실패한 확률이 2배정도 되기 때문이다. 실제로 적용할 만한 전략이 되기 해서는 성공확률이 더 높아야 될 필요가 있다.

무엇인가를 선택한 결과로 1등, 즉, 가장 좋은 것을 얻게 되면 더 없이 좋겠지만, 가치관에 따라서는, 어느 정도 좋은 것을 얻게 되더라도 만족할 수 있다. 가령, 상위 10%에 속하는 것을 얻게 되었을 때에도 상당히 만족스러워 할 수 있다. 게다가 그 방법이 성공 확률이 높으면 만족도는 더욱 높아질 것이다.

실제로 1997년에 Todd는 컴퓨터 프로그래밍을 통하여, 상위 10%에 속하는 배우자를 선택하는 것을 목표로 한다면, 14%의 후보를 보낸 후에, 그 후부터는 이전보다 더 좋은 후보가 나타나면 배우자로 선택하는 전략을 택할 때 성공확률이 83%로 가장 높다는 결과를 얻었다.

그리고 상위 25%에 속하는 배우자를 선택하는 것을 목표로 한다면, 7%의 후보를 보낸 후에, 그 후부터는 이전보다 더 좋은 후보가 나타나면 배우자로 선택하는 전략을 택할 때 성공확률이 92%로 가장 높다는 결과를 얻었다. 이 결과는 최고의 1명, 즉, 상위 1%에 속하는 배우자를 선택하기 위한 37% 전략의 성공확률이 37%에 불과한 것과 비교하면 엄청나게 좋은 성공확률이다. 최고의 배우자를 선택해야 된다는 것을 양보한 대신에 매우 높은 성공확률을 얻는 것으로, 어쩌면 실제 상황에서의 실용성 면에서 보면 이 전략이 훨씬 더 긍정적이라고 하겠다. 무턱대고 최고만을 고집할 것이 아니라, 실현 가능성도 함께 고려하고, 어느 정도 이상이면 자족할 줄 아는 지혜가 중요하다고 하겠다.

* 이 글은 <이승훈 교수의 실용수학>(이승훈, 경문사)의 내용을 보완한 것입니다.