증명 귀찮아서 안할까 했는데

인터넷 문화는 귀찮아서 안한다 = 쫄튀 느낌이 있어서...

---------------------------------------------------------------

 

확률 문제에서 가장 중요한 건 사건의 설정.

일단 r-1 번까지 보고 r 부터 판단을 내리는 경우니까 r을 독립변수로 사건을 설정할 수 있음

P(r)에 대해서 생각해보기 전에

가장 괜찮은 녀석을 번호를 i번째라고 생각하자.

그러면 얘는 1번부터 N번까지 중에서 아무데나 있을 수 있지.

이 전략 (r-1까지는 재끼고 r부터는 r-1까지 애들 중에서 가장 큰 애들보다 더 큰 애가 있으면 바로 선택한다.)이 성립하려면

i가 어디 있든 간에 i는 선택되고 i는 최고로 괜찮은 녀석이여야 함.

 

사건을 설정해서 i가 선택되는 게 A i가 최고로 괜찮은 녀석인 게 B라고 하면

(식1)이라고 생각할 수 있음

여기서 A와 B는 조건부확률로 (식2)라고 생각할 수 있음

여기서 B의 사건은 1/N이지 (N명 중에서 i번째 친구가 최고로 괜찮은 녀석일 확률)

그리고 r-1까지 중에서 만약 i가 최고면 처음 스크리닝 과정에서 걸러지니까 얘네들은 선택될 일이 없음

그래서 P(r)을 다시 쓰면 (식3) 이렇게 되고 (여기서 C는 i 이전에 두 번째로 괜찮은 녀석이 있을 확률.)

(왜냐하면 두번째로 괜찮은 녀석이 r-1 이전에 있지 않으면 우리가 원하는 경우가 나오지 않잖아)

정리하면 이렇게 됨 (식4)

여기서 이 값을 근사하기 위해서 N을 충분히 크게하면

이 적분 꼴로 근사가 되서 (식5)

(4에서 5 근사 과정은 중간에 r, i에다가 1씩 더한 어떤 두 문자로 치환해서 생각하면 편할거임)

확률은 이 모양으로 나옴

여기서 확률을 연속함수로 표현했으니까 이거의 최대값을 구하면 됨.

미분해서 최대인 지점은 x=1/e 인 지점임.

따라서 1/e까지 스크리닝 하고 선택하는 게 최고의 방법이라는 것이 증명됨

 

 

ps. 놀라운 사실은 N이 무한으로 갈때만 성립하는 게 아니라 1에서부터 전부 성립하다는 것이 증명되어 있음

그 증명은 노가다로 몇 개만하면 됨...

-------------------------------------------------------------------

라텍스 쓰기 귀찮아서 편한 한컴으로 식은 정리했음

식은 위에서부터 1~5

(식 3에서 n이 아니라 N)