최적 멈춤 문제(Optimal stop problems)
0. 최적 멈춤 문제¶
최고의 남편감을 찾는 여성의 경우를 생각해 봅시다. 남자들을 한 명씩 만나가면서 데이트하고 청혼을 받아 들이면 남편 찾기가 끝납니다. 반대로 청혼을 받아들이지 않으면 그 남자는 다시는 볼 수 없습니다.
당신이 청혼을 너무 일찍 받아들이면 뒤에 남아있는 남자들 중 최고의 남편감이 있을 것이고 반면 너무 늦게 청혼을 받아들이면 앞에 있었던 더 좋은 남편감을 놓치게 될수도 있게 됩니다. 그렇다면 언제 탐색을 멈춰야 최고의 남편감을 구할 수 있을까요?
최적 멈춤 문제라고 불리는 이 문제의 답은 약 37% 으로 수학적으로 증명되었습니다. 즉, 전체 남자의 37%의 수만큼 데이트를 하고 앞서 데이트한 남자들보다 뛰어난 남편감이 나타나면 바로 청혼을 받아 들이는 것이 최적의 전략입니다.
1. 왜 37% 일까?¶
총 10명의 남자가 있다고 생각해봅시다.
- 1번째 남자 : 지금까지 본 사람 중 최고의 남편감일 확률은 100%
- 2번째 남자 : 지금까지 본 사람 중 최고일 확률은 $\frac{1}{2}$
- 5번째 남자 : 지금까지 본 사람 중 최고일 확률은 $\frac{1}{5}$
- 10번째 남자 : 지금까지 본 사람 중 최고일 확률은 $\frac{1}{10}$
다시말해 데이트를 계속 하면 오히려 확률을 낮아지고 있다는 것을 알 수 있습니다. 따라서 일정한 수를 살펴보고 커트라인 점수를 정하고, 그 이후 점수를 초과한 남자의 청혼을 받아들이는 전략을 사용해야 합니다.
남자의 수 $n$, 최초 $r$ 명의 지원자를 탈락 시킬때 최상의 선택 확률은 아래 표와 같습니다. 즉, $n$이 커지면 확률 $P$가 37%에 가까워 진다는 것을 알 수 있다. 수학자들은 남자의 수 $n$에 대하여 최적의 데이트 전략은 $\frac{1}{e}$ 명 살펴보기임을 이미 증명 했습니다. 정확하게는 $\frac{1}{e} = 0.3678794$ 입니다. 수학적 증명 확인하기
| n | r | P |
|---|---|---|
| 1 | 0 | 1.000 |
| 2 | 0 | 0.500 |
| 3 | 1 | 0.500 |
| 4 | 1 | 0.458 |
| 5 | 2 | 0.433 |
| 6 | 2 | 0.428 |
| 7 | 2 | 0.414 |
| 8 | 3 | 0.410 |
| 9 | 3 | 0.406 |
| 10 | 3 | 0.398 |
2. 확률을 시각화하기¶
위의 표를 파이썬으로 시각화해서 직관적으로 최적의 전략을 살펴봅니다.
2.1. 최고의 지원자를 선택할 확률¶
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
def choose_candidate(n, reject=np.e):
candidates = np.arange(1, n + 1)
np.random.shuffle(candidates)
if reject == np.e:
stop = int(round(n / reject))
else:
stop = int(round(reject * n / 100))
best_from_rejected = np.min(candidates[:stop])
rest = candidates[stop:]
try:
return rest[rest < best_from_rejected][0]
except IndexError:
return candidates[-1]
best_candidate = []
for r in range(5, 101, 5):
sim = np.array([choose_candidate(n=100, reject=r) for i in range(100000)])
best_candidate.append(np.histogram(sim, bins=100)[0][0] / 100000)
plt.figure(figsize=(10, 6))
plt.scatter(range(5, 101, 5), best_candidate)
plt.plot(range(5, 101, 5), best_candidate)
plt.xlabel("% of candidates rejected")
plt.ylabel("Probability of choosing best candidate")
plt.axvline(100 / np.e, ls="--", c="black")
위의 그림에서 알 수 있듯이 약 37%의 지원자들을 살펴보고 결정했을때 최고의 남편감을 선택할 확률이 가장 높습니다. 다만 그 성공 확률은 35% 로 일반적인 관점에서 만족스럽지 않습니다.
그렇다면 욕심을 조금 줄여 상위 5% 10%, 25%의 남편감을 찾겠다는 목표 변경하면 성공 확률이 어떻게 될까요?
2.2. 다양한 목표에 따른 성공 확률¶
def choose_candidate(n, reject=np.e):
candidates = np.arange(1, n + 1)
np.random.shuffle(candidates)
if reject == np.e:
stop = int(round(n / reject))
else:
stop = int(round(reject * n / 100))
best_from_rejected = np.min(candidates[:stop])
rest = candidates[stop:]
try:
return rest[rest < best_from_rejected][0]
except IndexError:
return candidates[-1]
def get_best_candidates(best_n=1):
best_candidate = []
for c in [1] + list(range(5, 101, 5)):
sim = np.array([choose_candidate(100, reject=c) for i in range(10000)])
best_candidate.append(len(sim[sim <= best_n]) / 100)
return best_candidate
plt.figure(figsize=(10, 6))
for i in [1, 5, 10, 25]:
plt.scatter(range(0, 101, 5), get_best_candidates(i), label=str(i))
plt.plot(range(0, 101, 5), get_best_candidates(i), label=None)
plt.xlabel("% of candidates rejected")
plt.ylabel("Probability of choosing best candidates")
plt.legend(title="No. of best candidates")
위 그림의 결과를 정리하면 아래 표와 같습니다.
| 선택 목표 | 거절 비율 | 성공 확률 |
|---|---|---|
| 최고의 남편감 | 37% | 37% |
| 상위 5% 남편감 | 22% | 57% |
| 상위 10% 남편감 | 14% | 85% |
| 상위 25% 남편감 | 7% | 92% |
만약 상위 25% 남편감을 목표한다면 성공확률이 무려 92% 까지 높아진다는 것을 알 수 있습니다.
그리고 상위 10%에 속하는 남편감을 선택하는 것이 목표라면 14%의 남자들과 데이트를 한 뒤 이전 보다 더 좋은 남자가 나타났을 때 선택하면 성공 확률이 85%가 됩니다.
정리하자면 최고의 남편감을 목표로 하면 성공 활률이 37% 불과하지만 상위 10%를 목표로 하면 성공확률은 85%로 급격하게 올라갑니다.
여기서 우리가 배울 수 있는 것은 실제 실용적인 측면에서 무턱대고 최고만을 고집할 것이 아니라 성공 확률을 고려해 목표에 대한 욕심을 조금 줄이는게 좋다는 것입니다.