최적 순차 탐색

가게를 한 곳씩 돌며 가장 좋은 값을 찾는 장면입니다.

한 곳을 더 볼 때마다 비용이 듭니다. 그래서 기준값을 하나 미리 정해 둡니다. 기준보다 좋은 제안이 오면 바로 삽니다. 기준보다 못하면 한 곳 더 둘러봅니다. 그 기준이 아래 식의 유보가치입니다.

예를 들면, 👕 옷을 사러 가게를 돌아다닙니다. 한 곳을 더 둘러보면 🚌 버스비로 1,000원이 듭니다. '5만 원보다 싸면 바로 산다'고 기준을 정해 둡니다. 6만 원이면 그냥 나옵니다. 4만 8천 원이면 바로 삽니다.

c=E[(X−r)+]=(M−r)22M,r∗=M−2Mcc = E[(X - r)^+] = \frac{(M - r)^2}{2M}, \qquad r^* = M - \sqrt{2Mc}
V(r)=M+r2−cMM−r,V(r∗)=r∗V(r) = \frac{M + r}{2} - \frac{cM}{M - r}, \qquad V(r^*) = r^*

예제

X∼Uniform[0,100]X \sim \text{Uniform}[0, 100], 탐색 비용 c=4c = 4라 하자.

무차별 조건 c=E[(X−r)+]c = E[(X - r)^+]에서 유보가치 r∗r^*를 유도하고, 최적 정책의 기대 탐색 횟수와 V(r∗)=r∗V(r^*) = r^*를 수치로 확인하라.

c=E[(X−r)+]=∫rMx−rM dx=(M−r)22Mc = E[(X - r)^+] = \int_r^M \frac{x - r}{M}\,dx = \frac{(M - r)^2}{2M}
r∗=M−2Mcr^* = M - \sqrt{2Mc}
c=4c = 4, M=100M = 100 — r∗≈71.72r^* \approx 71.72.
증명 보기

  1. rr을 제시받고 한 번 더 탐색하는 것의 기대이득은 ∫r100(x−r)/100 dx=(100−r)2/200\int_r^{100} (x - r)/100\,dx = (100 - r)^2/200이다. 비용 c=4c = 4와 같게 놓으면 (100−r)2=800(100 - r)^2 = 800, 즉 r∗=100−800≈71.72r^* = 100 - \sqrt{800} \approx 71.72이다.

  2. 한 라운드에서 중단할 확률은 P(X≥r∗)=(100−r∗)/100≈0.2828P(X \ge r^*) = (100 - r^*)/100 \approx 0.2828이므로, 중단까지의 탐색 횟수는 기댓값 1/0.2828≈3.541/0.2828 \approx 3.54인 기하분포를 따른다.

  3. V(r∗)=(100+r∗)/2−4⋅100/(100−r∗)≈85.86−14.14=71.72=r∗V(r^*) = (100 + r^*)/2 - 4 \cdot 100/(100 - r^*) \approx 85.86 - 14.14 = 71.72 = r^* — 무차별 조건이 성립하는 지점에서는 탐색의 가치가 손에 쥔 제안과 정확히 같다.

    V(r∗)=M+r∗2−cMM−r∗=r∗V(r^*) = \frac{M + r^*}{2} - \frac{cM}{M - r^*} = r^*

X∼Uniform[0,100]X \sim \text{Uniform}[0, 100], c=8c = 8일 때 r∗r^*를 구하고, V(r∗)=r∗V(r^*) = r^*가 정수 연산으로 정확히 성립함을 보여라.

r∗=100−2⋅100⋅8=100−40=60r^* = 100 - \sqrt{2 \cdot 100 \cdot 8} = 100 - 40 = 60
c=8c = 8, M=100M = 100 — r∗=60r^* = 60, 기대 탐색 횟수 2.52.5.
증명 보기

  1. 2Mc=1600=4022Mc = 1600 = 40^2이므로 r∗=100−40=60r^* = 100 - 40 = 60이다. 중단 확률은 40/100=0.440/100 = 0.4이고 기대 탐색 횟수는 1/0.4=2.51/0.4 = 2.5이다.

  2. V(60)=(100+60)/2−8⋅100/40=80−20=60=r∗V(60) = (100 + 60)/2 - 8 \cdot 100/40 = 80 - 20 = 60 = r^* — 소수점 오차 없이 정확히 일치한다.

18. 정보의 경제학