| [ QuizWit ] in KIDS 글 쓴 이(By): pinkrose (쭈쭈바) 날 짜 (Date): 1999년 6월 24일 목요일 오후 03시 06분 29초 제 목(Title): 변태적 마이크로소프트문제... 예를 들어... 숫자가 1 2 3 4 5 6 7 이 있다면... 환상님 전략대로라면 먼저 4를 고르겠죠? 다음에 2나 6을 고르고... 그러면 답은 1,3,5,7 중의 하나에 숨겨놔야 한다는 겁니까? 이 전략을 상대방이 예측할 수 있다면.. 전 1,3,5,7 네 숫자에서만 답을 찾겠습니다. 하지만 이에 대한 역공으로 다시 2,4,6 속에 답을 숨겨놓을 수도 있죠. --------------------------------------------- 바로이겁니다. 역공에 역공에 역공... 이런식으로가면 끝이 없거든요. 그렇기때문에 모든 전략에 대한 확률적인 접근이 필요한겁니다. 문제자체가 빌게이트입장에서 추측하는기대치를 높이는것이기때문에 for an integer n , let X(#,n) be a random variable defined as as a number of step the candidate can guess 'n' in #th step. Then we have to solve Max_n E( X(#,n)). 사실 제가볼때 이문제 그렇게 잘정의된문제가 아니거든요 왜냐면 종대씨 지적대로 역공에 역공까지 생각해야하니까요. 만약에 캔디데이트가 무작위적으로 렌덤으로 uniform[1,100] 으로 정한다면 이문제 무척 쉽게 풀립니다. 캔디데이트가 유니폼으로 결정을 하더라도 빌게이트가 높다 낮다 힌트를주니까 unbalanced binary search( weighted binary search라고해야하나?) 를하게되거든요. 이경우의 n값을구하는건 쉽습니다. 그냥 X(#,n)의 확률디스트리뷰션만 알면되니까� 요. 어떠한 n에대해서도 X(1,n) = 1/100입니다. 왜냐면 한번에 맞출경우는 1/100이니까. 두번만에 맞출경우는.... 이런식으로 일단 확률분포를 구하고 기대치를 구하면 이기대치를 최고로 높이는 그러한 n을 구하면 이문제는 풀립니다. 그런데 문제는 캔디데이트가 정확한 발란스드 바이나리 써치를 할수도 있다는거지요. 왜냐면 언발란스드 바이나리 써치보다는 발란스드가 더빠르니까요. 그렇다면 발란스드 써치를 가정하고 이문제가 역시 풀립니다. 여기까지는 100% 확실한 이문제의 풀이방법인데, (이문제 통계저널에 실린문제고요, 출제자의 의도를 정확히 파악하고 나온문제의 문맥을 정확히 파악하면 --옛날 퀴즈보드에 포스팅되었을때하고 약간 다릅니다. 그때보다 좀더 엄격하게 문제가 define되어있으니까요.) 그다음부터는 솔직히 저도 짐작하는수준. 저같으면 역공의 역공을 다음과같이 풀겠습니다. 통계에서는 하이라키알 모델링이라는방법론이 있습니다. 혹은 베이시안 인퍼런싱이라고하는데, 마치 공중에다 다리한짝을 들고 구두끈을 잡아당겨서 하늘을 걸으려는 방법하고도 비슷한데, 이게 실제 works.믿기지 않겠지만요. 일단빌게이트는 캔디데이트가 발란스드 바이나리 써치로 추측을 한다고 가정을하고 기대치를 높이는 그러한 n을 구합니다. 이경우의 확률분포를 prior distribution이라고 합니다. 그다음 캔디데이트가 이걸 짐작하고 엉뚱한방법으로 추측을할수가 있습니다. 즉 under the assumption of prior distribution상에서 새롭게 확률분포가 나오게됩니다. 이걸 통계에서는 posterior distribution이라고합니다. 대부분은 여기서 그냥 끝내는데 그게 아니라 계속 꼬리를 물고 디스트리뷰션을 계속 생성시킬수가 있습니다. 역공에 역공에 역공을 하는식으로.. 무한대가면 아심토티칼리 converge 할수도 있고 안할수도 있고 그래요. 종대씨 지적이 옳기는옳은데 끝에 빌게이트가 역공에 역공을해서 다시 처음의 숫자들에 숫자를 숨긴다는건 약간 잘못되었습니다. 일반적으로 congugate family가아닐경우는 디스트리뷰션위에 디스트리뷰션위에 다시 디스트리뷰션을 하게되면 자기자신으로 돌아오지 않습니다. 예를들면 가우시안 디스트리뷰션일경우 프라이어가 가우시안이면 포스테리아도 가우시안이거든요. 이경우는 아무리 하이라키알 모델을 구성하더라도 여전이 가우스분포가 나오기때문에 아심토티칼리 converge하게되고 답 존재하게됩니다. (이문제 지난번의 염소와 자동차문제랑 접근법은 똑같습니다. 염소와 자동차문제에서도 사회자가 문짝을 염으로써 기존의 프라이어 디스트리뷰션이 변해서 포스테리어 디스트리뷰션으로 바뀌게되는거거든요. ) 제가보기엔 이문제 이렇게 이정도로 완벽하게 풀면 저널에 퍼블리쉬해야할꺼고요, 그냥 poblem corner이니까 캔디데이트의 경우는 그냥 최고전략이 발란스드 바이나리 써치고요, 빌게이트의 전략은 발란스드 바이나리 써치에 대한 방어전. 여기서 끈내야지요. (사실 이문제 제가 좀일반화시켜서 여기포스팅한거고요 실제 저널에는 빌게이트가 1,2,3,중 어떤숫자를 골라야 기대치를 최고로 높이는지 생각하라고 나와있었어요. ^^ ) 종대씨하고 두번째로 이렇게 토론하니까 옛날에 미쳐 생각못했던 여러가지를 새롭게 생각해보게되는군요. "인생은 예측불허. 그리하여 쭈쭈바의 의미를 찾는다" 쭈쭈바의 네딸들에서 "언제 오줌을 쌀건지는 예측불허. 그리하여 난 전봇대를 찾아헤멘다." 너의 쭈쭈바가 하늘을 날게하려면, 쭈쭈바에게 나는법을 가르쳐라. - McGill 수학과 1층 남자화장실에 쓰인 낙서. |