2022년 8월 1일 월요일

결혼 상대는 후보 10명중 4명째에서 선택하는 것이 최적 임을 증명하라(베이지안 확률과정)

(인터넷에서 과거에 있었던 글인데 출처는 불명입니다. 혹시 아시는 분은 말씀주시길)

다음 링크는 이 문제를 재서술한 것: 

https://jinseob2kim.github.io/propose.html



상황 가정


: 한 여성에게 100명의 남자가 순차적으로 프로포즈 한다

: 첫번째 프로포즈 허락하면 나머지 99명은 못 본다, 마찬가지로 99번 거절하면 100번째와 결혼해야 한다.

: 100명의 남자의 분포는 랜덤이다. 즉, 어떤 남자가 왕자인지 모른다.

: 여자는 r번째까지는 튕기고 r+1 번째 남자부터는 r번째까지 본 남자를 기반으로 고려할 때가장 괜찮다면 결혼한다.

문제: 여성은 몇 명을 튕긴 후 선택해야 가장 괜찮은 남자와 결혼할 수 있을까?



해결:

베이지안 조건부 확률 접근


B : 여자가 왕자를 선택할 확률.

A1 : 왕자가 1번째로 프로포즈해 올 확률.

A2 : 왕자가 2번째로 프로포즈해 올 확률.

.......

A100 : 왕자가 100번째로 프로포즈해올 확률.


이 경우 왕자를 선택할 확률=P(B) 은 다음과 같다

(참고: P(B/A1)란 A1이라는 사건이 일어났다는 가정하에 B가 일어날 확률, 즉, 왕자가 1번째로 프로포즈 하고 여자가 이를 받아들일 확률)


P(B) = P(A1)*P(B/A1) + P(A2)*P(B/A2) + ... +P(A100)P(B/A100)    _____________  식(1)


우리의 목표(=몇명까지 튕기는게 합리적인가?)는 왕자를 만날확률=P(B)를 최대화시키는 것이다. 즉, MAX[P(B)]이를 위해 여성이 r명까지는 튕기고 그 다음부터 만나는 남자 중 제일 멋진 남자와 결혼하기로 결정했다고 가정하자.


그러면 P(B/A1)=0, P(B/A2)=0, ..... , P(B/Ar)=0 이다. r명까지는 튕기기로 했기 때문이다.

남자의 분포는 랜덤이므로 P(A1)=P(A2)=...=P(A100)= 1/100   로 모두 같다.


P(B|Ar+1)=1 이다. r+1번째에 왕자가 프로포즈했다면 이 남자는 지금까지 튕긴 r번째 남자들보다는 확실히 더 나을 것이므로 당연히 여자는 이를 선택할 것이다.


이를 토대로 P(B|Ar+2)를 구해보자


만약 r+2번째가 왕자인데 r+1번째 남자가 기존 r명보다 괜찮아서 r+1번째 남자의 프로포즈를 ok한다면, 이는 여자에게 실패다.


따라서 r+1번째 남자가 기존 r명의 남자보다 떨어지는 남자여야 실패 확률이 줄어든다.


이를 다시 정리하면 r+1번째까지 만난 남자 중 제일 괜찮은 남자가 r+1번째 남자만 아니면 된다. 왜? r번째까지는 무조건 튕길 것이기 때문이다.1,2,3,...,r,r+1번째 중 r+1번째만 아니면 되니까 확률은 r/(r+1)이다.


P(B/A(r+1)) = 1 = r/r   (r+1번째로 백마탄 왕자가 프로포즈 해 왔다면 r명까지 튕긴 여자는 이전에 본 r명보다 더 멋진 남자를 바로 만나버린 거니까 백마탄 왕자 픽업할 확률은 100%)

P(B/A(r+2))=r/(r+1)

P(B/A(r+3))=r/(r+2)

...

P(B/A(99))=r/99

P(B/A(100))=r/100


이 결과를 앞의 식(1)에 대입하면


P(B)=1100×(1+rr+1+rr+2++r99+r100=1100x=r100rx


계산의 편의를 위해 적분을 통해 근사값을 구하자


P(B)=1100x=r100rxr100100r1xdx=r100×(ln100lnr)


(답)

r = 100/e = 약 37


한 여자에게 프로포즈하는 남자의 숫자가 100명이라고 하면 여자는 최초 37명까지는 튕겨볼 수 있어도 38번째부터는 튕겨서는 안되며 나름 괜찮다 싶으면 잡아야 한다.

현실적으로 여성에게 프로포즈 하는 남자가 5명쯤 된다면 최초 한 명은 튕겨볼 수 있으나 2번째 남자가 프로포즈해 올 경우 첫번째 남자보다 낫기만 하다면 프로포즈를 받아들이는 것이 합리적이다



 


댓글 없음:

댓글 쓰기