비서 문제 (Secretary Problem)

Photo by Luca Bravo on Unsplash

여러분이 다음 뽑기 게임에 참가했다고 가정해 봅시다. 안을 볼 수 없는 상자가 여러분 앞에 놓여 있습니다. 여러분은 상자 안에 총 \(n\) 개의 공이 들어 있다는 것과, 공에는 서로 다른 숫자가 적혀 있다는 것을 알고 있습니다. 이제 여러분은 상자에서 공을 하나씩 무작위로 뽑고 공의 숫자를 확인할 것입니다. 만약 숫자가 마음에 든다면 여러분은 이 공을 선택할 수 있고, 만약 마음에 들지 않는다면 이를 버리고 새 공을 뽑을 수 있습니다. 다만 한 번 버린 공은 다시 주울 수 없죠. 가장 큰 숫자가 적힌 공을 선택해야 뽑기 게임에서 이긴다고 할 때, 과연 여러분은 어떤 전략을 취해야 할까요?

 

이 문제는 1950-60년대 여러 수학자들과 통계학자들 사이에서 매우 깊이 연구되었던 비서 문제(secretary problem)를 다른 식으로 표현한 것입니다. 잘 알려진 형태로 다시 써 보자면 다음과 같습니다. 이 문제에서 여러분은 인사 담당자이고, 현재 한 명의 비서를 뽑아야 하는 상황입니다. 총 \(n\) 명의 지원자가 지원을 했으며, 각 지원자는 서로 다른 적합도를 보입니다. 다만, 면접을 진행하기 전까지 여러분은 지원자의 적합도를 파악할 수 없습니다. 면접은 한 사람씩 진행되고, (야박하지만) 그 자리에서 당락을 결정해 줍니다. 즉, 현재 면접을 보는 사람을 떨어 뜨리면 다시 이 사람을 부를 수 없고, 반대로 합격을 시키면, 이후의 지원자는 면접을 보지 못합니다. 이런 상황에서 여러분의 목표는 만약 지원자가 균등한 확률로 일렬로 배치되었다고 했을 때 가장 적합도가 높은 지원자를 합격시키는 것입니다.

 

개인적으로는 지원자들이 랜덤 순열(random permutation)을 이룬다는 것보다는 처음 소개한 상자에서 공을 무작위로 고르는 예시가 좀더 현실적이라고 생각해서 아래 글에서는 상자에서 공을 꺼내는 예시를 기준으로 기술하였습니다.

---

생각해 볼 수 있는 방법 중 가장 간단한 방법은 다음과 같겠죠.

첫 번째 뽑은 공을 선택한다.

너무 단순한가요? 하지만 여전히 우리는 이 방법이 성공할 확률을 쉽게 계산할 수 있습니다. 공의 개수가 \(n\)이라고 하였으니 우리가 균등한 확률로 공을 뽑는다면 \( 1/n \)의 확률로 성공할 것입니다. 안타깝게도 이 방법은 그다지 좋아 보이지 않습니다. 만약 \(n\)의 크기가 엄청 크다면 그 확률이 0에 수렴할 것이기 때문이죠.

 

위 방법은 아무런 정보도 없이 "인생은 한 방이지!"라는 마음가짐으로 동작하는 것 같군요. 너무 멍청하죠. 그러면 다음과 같이 처음에 약간 손해를 볼지라도 유용한 정보를 갖춘다면 어떻게 될까요?

첫 번째 뽑은 공은 무조건 버리되 그 공의 숫자를 기억해 놓는다. 다음부터 만약 이번에 뽑은 공의 숫자가 기억해 놓은 숫자보다 더 크면 이를 선택하고, 그렇지 않으면 버리고 다음 공을 뽑는다.

이 방법이 성공할 확률을 계산해 보도록 하겠습니다. 이를 구하기 위해서는 위 방법을 약간 수정해 주어야 편합니다. 원래는 공을 하나 선택하면 더이상 공을 뽑지 않지만, 그냥 그 이후에도 공을 뽑고 버리기만 한다고 하겠습니다. 이렇게 바꾸어 주어도 여전히 두 방법이 선택하는 공은 동일하므로 수정된 방법을 통해서 성공할 확률을 계산하는 것으로도 충분합니다.

 

이제 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑고, 실제로 그 공을 선택까지 할 확률을 계산해 봅시다. 먼저 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑을 확률은 첫 번째부터 \(i - 1\) 번째까지는 해당 공을 뽑지 않고 정확히 \(i\) 번째일 때 그 공을 뽑을 때의 확률이므로

\[ \frac{n - 1}{n} \times \cdots \times \frac{n - i - 1}{n - i - 2} \times \frac{1}{n - i - 1} = \frac{1}{n} \]

이 된다는 것을 알 수 있습니다.

 

이번에는 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑았다는 조건 하에 그 공을 실제로 선택할 확률을 구해 봅시다. 일단 \(i = 1\)인 경우, 첫 번째 뽑은 공은 반드시 버리므로 그 확률은 0입니다. 반대로 \(i > 1\)인 경우를 보죠. 우리가 이 방법을 통해 정확히 \(i\) 번째 공을 선택하려면 이전에 뽑은 \(i - 1\) 개의 공 중에서 첫 번째로 뽑은 공이 가장 큰 숫자를 갖고 있어야 합니다. 직관적으로 생각해 봤을 때 이 확률은 \( \frac{1}{i - 1} \)이 될 것입니다. (엄밀한 증명은 아래에서 찾으실 수 있습니다.)

 

앞에서 발견한 사실을 통해서 우리는 가장 큰 숫자가 적힌 공을 정확히 \(i\) 번째에 뽑고, 실제로 그 공을 선택할 확률이 

\[ \frac{1}{n} \cdot \frac{1}{i - 1} \]

이라는 점을 알 수 있습니다. 모든 공에는 서로 다른 숫자가 적혀 있으므로, 가장 큰 숫자가 적힌 공을 한 번 뽑으면 그 전이나 후에 가장 큰 숫자가 적힌 공을 또 뽑을 수 없습니다. 그러므로 모든 \(i = 1, \cdots, n\)에 대해, 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑고 실제로 그 공을 선택하는 사건은 상호 배반(mutually disjoint)의 관계를 이룹니다. 따라서 이 방법이 성공할 확률은

\[ \sum_{i = 2}^n \frac{1}{n} \cdot \frac{1}{i - 1} = \frac{H_{n - 1}}{n} \approx \frac{\ln (n - 1)}{n} \]

이 된다는 것을 유추할 수 있습니다. 이때 \( H_{k} \)는 \( k \) 번째 조화수(harmonic number)를 나타내며, 충분히 큰 \(n\)에 대해서 \( H_k \approx \ln k \)라는 사실을 통해 마지막 관계를 도출하였습니다.

 

앞에서 첫 번째 공을 바로 선택하는 방법이 성공할 확률이 \(1/n\)이라고 하였으므로, 현재 고려하는 방법이 이전 방법보다 높은 확률로 성공한다는 사실을 알 수 있습니다. 하지만 여전히 충분히 큰 \(n\)에 대해서 위 확률은 0에 수렴합니다. 과연 0보다 큰 상수의 성공 확률을 갖는 방법은 없을까요?

---

첫 번째 방법보다 두 번째 방법의 성공 확률이 더 좋았습니다. 이는 분명 두 번째 방법이 첫 번째 공을 소모하되 이를 기준으로 그보다 작은 숫자가 적힌 공을 걸러냈기 때문일 것입니다. 따라서 두 번째 방법을 다음과 같이 확장 시켜 보도록 하겠습니다. 아래에서 \(r\)은 \(1\)과 \(n\) 사이의 어떤 정수이며, 이는 나중에 최적화할 것입니다.

\(r-1\) 번째 뽑은 공까지는 버리기만 한다. 대신 그때까지 뽑은 공의 숫자 중 가장 큰 값을 기억한다. 다음부터 만약 이번에 뽑은 공의 숫자가 기억해 놓은 숫자보다 크다면 그 공을 선택한다. 그렇지 않으면 버리고 다음 공을 뽑는다.

참고로 앞의 첫 번째 방법은 (기억해 놓은 숫자를 \(-\infty\)라고 했을 때) \(r = 1\)인 경우이고, 두 번째 방법은 \( r = 2 \)인 경우와 동일하게 동작한다는 것을 확인하시기 바랍니다.

 

이 방법이 성공할 확률을 구해 봅시다. 앞의 두 번째 방법을 분석할 때와 비슷하게, 먼저 이 방법도 비록 어떤 공을 선택한 후에도 상자에 공이 없어질 때까지 공을 뽑고 버리는 작업을 반복했다고 가정하겠습니다. 우리가 구해야 할 것은 이 방법을 통해 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑고 실제로 그 공을 선택한 확률을 구하는 것입니다. 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑을 확률은 \( 1/n \)이 된다는 것은 앞에서 논증하였습니다.

 

남은 것은 가장 큰 숫자가 적힌 공을 \(i\) 번째에 뽑았다고 가정했을 때, 실제로 해당 공을 선택까지 한 확률을 구하는 것입니다. 이는 \(i \geq r\)에 대해, \( i - 1 \) 번째까지의 공들 중에서 가장 큰 값을 가진 공이 처음 \(r - 1\) 번째 안에 뽑힐 확률과 동일하며, 앞에서의 직관에 따르면 그 확률은 \( \frac{r - 1}{i - 1} \)이라고 유추할 수 있습니다. 이번에는 이를 다음과 같이 더 강한 명제를 통해 엄밀히 증명해 보도록 하겠습니다.

정리 1. 가장 큰 숫자가 적힌 공을 선택할 확률

---

이 방법을 통해 처음 \(j\)번째까지 뽑은 공들 중에서 가장 큰 숫자가 적힌 공을 처음 \(\ell\)번째 안에 뽑을 확률은 \( \frac{\ell}{j} \)이다. (단, \( \ell \leq j \).)

[증명] 우리가 구하고자 하는 사건, 즉 처음 \(j\)번째까지 뽑은 공들 중에서 가장 큰 숫자가 적힌 공이 처음 \(\ell\)번째 안에 뽑힐 사건을 \(\mathcal{E}\)라고 하겠습니다. 크기가 정확히 \(j\)인 어떤 공들의 부분집합 \(W\)에 대해, 이 방법이 처음 \(j\)번째까지 뽑은 공들이 정확히 \(W\)와 일치한다고 가정하겠습니다. 그러면 이 방법은 공을 매번 균등한 확률로 뽑기 때문에, 임의의 \(k = 1, \cdots, j\)에 대해, \(W\)에서 가장 큰 숫자를 갖는 공이 \(k\)번째에 뽑힐 확률은 \(1/j\)가 됩니다. 따라서,

\[ Pr[\mathcal{E} \mid W] = \frac{\ell}{j} \]

라는 사실을 이끌어낼 수 있죠. 그러면

\[ Pr[\mathcal{E}] = \sum_{W : |W| = j} Pr[\mathcal{E} \mid W] \cdot Pr[W] = \sum_{W : |W| = j} \frac{\ell}{j} \cdot Pr[W] = \frac{\ell}{j}\]

가 되는 것을 보일 수 있습니다. ■

 

앞에서 확인한 사실들을 종합하면, 이 방법이 성공할 확률은

\[ \sum_{i = r}^n \frac{1}{n} \cdot \frac{r - 1}{i - 1} = \frac{r - 1}{n} \sum_{i = r}^n \frac{1}{i - 1} \tag{1} \]

이 됩니다. 작은 \(n\)에 대해서는 이 값을 직접 구하는 것이 어렵지 않습니다. 아래 표는 \(n = 1, \cdots, 9\)와 \( r \leq n \)에 대해서 이 방법이 성공할 확률을 나타낸 것입니다.

\(n \setminus r\)	1	2	3	4	5	6	7	8	9
1	1.000*
2	0.500*	0.500*
3	0.333	0.500*	0.333
4	0.250	0.458*	0.417	0.250
5	0.200	0.417	0.433*	0.350	0.200
6	0.167	0.381	0.428*	0.392	0.300	0.167
7	0.143	0.350	0.414*	0.407	0.352	0.262	0.143
8	0.125	0.324	0.398	0.410*	0.380	0.318	0.232	0.125
9	0.111	0.302	0.382	0.406*	0.393	0.353	0.290	0.208	0.111

표에서 별(*) 표시로 색칠된 칸은 \(n\) 중에서 가장 큰 확률을 갖는 \(r\)을 나타낸 것입니다. 이를 통해 상자 안에 공의 개수에 따라 적절한 \(r\)을 잡으면 40% 이상의 확률로 성공할 수 있다는 것을 확인할 수 있습니다.

 

그렇다면 큰 \(n\)에 대해서는 어떻게 될까요? 여전히 위와 같이 높은 확률로 성공할 수 있는 \(r\)이 존재할까요? 아니면 어떤 \(r\)을 골라도 0에 수렴하는 확률을 가질까요? 놀랍게도 거의 40%에 육박하는 확률을 유지할 수 있습니다. 위의 식 1을 다음과 같이 수정하여 줍시다.

\[ \frac{r - 1}{n} \sum_{i = r}^n \frac{n}{i - 1} \cdot \frac{1}{n} = \frac{r - 1}{n} \left[ \frac{1}{\frac{r - 1}{n}} \cdot \frac{1}{n} + \frac{1}{\frac{r}{n}} \cdot \frac{1}{n} + \cdots + \frac{1}{\frac{n - 1}{n}} \cdot \frac{1}{n} \right] \]

이제 \(x := \frac{r - 1}{n}\)으로, \( f(t) = \frac{1}{t} \)로, 그리고 \( \Delta t = \frac{1}{n} \)으로 치환해 보겠습니다. 그러면 위 식을 다음과 같이 고쳐 쓸 수 있습니다.

\[ x \left[ f(x) \cdot \Delta t + f(x + \Delta t) \cdot \Delta t + \cdots + f(x + (n - r) \Delta t) \cdot \Delta t \right] \]

여기서 괄호 안의 항은 \(x\)부터 \(1\)까지의 \(f(t)\)의 왼쪽 리만 합(left Riemann sum)에 해당한다는 것을 확인하시기 바랍니다. (고등학생 때 배운 정적분의 그것과 같습니다. 저는 배운지 좀 오래 되서 이를 다시 공부하느라 애를 좀 먹었네요.) \(f(t) = \frac{1}{t}\)는 단조 감소(monotonically decreasing)하므로, 위 식은

\[ x \int_x^1 \frac{1}{t} dt = - x \ln x \]

보다 큰 값을 이루게 됩니다. 이 하한을 미분하여 극댓값을 구하면 \( x = 1/e \)일 때, \( 1/e \)의 값을 갖는다는 것을 알 수 있습니다. 따라서 충분히 큰 \(n\)에 대해서도 \(r\)을 \( \frac{n}{e} + 1 \) 정도 되는 값으로 설정하면, \(1/e \approx 37\% \)의 확률로 이 방법이 성공한다는 것을 보일 수 있습니다.

---

이번 시간에는 비서 문제에 대해서 알아 보았습니다. 특히 충분히 큰 \(n\)에 대해서도 37%에 달하는 상수의 확률로 성공하는 방법을 공부하였습니다.

 

이 문제와 이를 해결하는 방법은 컴퓨터 과학에서도 매우 중요한 역할을 담당하고 있습니다. 먼저 앞에서 우리는 제시한 방법(또는 알고리즘)이 임의의 입력에 대해서 37%에 육박하는 성공 확률을 보인다고 증명하지 않았습니다. 만약 임의의 입력이었다면 우리는 앞의 방법을 망가뜨리는 입력을 쉽게 생각할 수 있었겠죠. 대신 특정한 확률 분포(여기서는 랜덤 순열)가 입력되었을 때 해당 확률로 성공한다는 것을 보였습니다. 이 분석 방법은 알고리즘의 확률적 분석(probabilistic analysis of algorithm)에 해당합니다. 이에 관한 자세한 내용은 아래 포스트를 참조하세요.

2020.11.28 - [알고리즘 & 확률/Basic] - 랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms)

랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms)

 

다른 한편으로 이 문제는 온라인 문제(online problem)의 특징도 보입니다. 처음에 모든 입력이 주어지지 않고 대신 시간이 흐르면서 하나씩 알려지고, 매번 번복할 수 없는 결정을 내려야 하기 때문입니다. 다만 앞에서 논의한 대로, 임의의 입력이 주어지는 대신, 어떤 확률 분포에 의해 정해지는 순서에 따라 입력이 들어옵니다. 이는 기존에 불공평한 상대방(adversary)을 상정하고 입력을 받는다는 온라인 문제의 정의와는 사뭇 다릅니다. 이를 구분하기 위해서 입력이 어떤 확률 분포에 따라 주어지는 모델을 랜덤 도착 모델(random arrival model)이라고 부르며, 기존의 상대방을 상정하는 모델을 상대방 모델(adversarial model)이라고 부릅니다. 랜덤 도착 모델의 온라인 문제 및 알고리즘은 개인적으로 아직 부족한 부분인데, 이를 잘 보완해서 언젠가 공유할 만한 내용이 있으면 포스팅하도록 하겠습니다. 온라인 문제 및 온라인 알고리즘과 관련한 내용은 아래 포스트를 참조하세요.

2020.03.14 - [온라인 알고리즘/Basic] - 온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

 

궁금하신 점이 있으시거나 글에 오류가 있다면 알려주세요. 고맙습니다. :)

 

참조

[1] Thomas S. Ferguson, "Who solved the secretary problem?." Statistical science 4, no. 3 (1989): 282-289.