microsoft-어려운 확률 문제

  • #153943
    인터뷰문제 70.***.211.168 9770

    저번주에 Microsoft SDE 전화 인터뷰를 봤습니다. 처음에는 제 전공을 물어보다가 테크닉에 관한 문제를 낸다고 하더군요..
    그래서 받았던 문제 하나가 확률 문제입니다. 머리가 멍하니 생각이 안나더라구요. 확률에 대해서 배운지도 너무 오래되서요..

    문제는 이렇습니다

    동전을 100k 그리고 10k 던졌을때 네가 이길 확률은 어느쪽이 더 높은지? 100k 던졌을때인지 10k 던졌을때인지? (이기는조건: hat이 60% 이상이 나오면 이기는 겁니다). hat과 tail이 나올확률은 각각 1/2이고 독립입니다.
    예를들면 두번 던졌을때는 1/4이고 3번 던졌을때는 4/8 이고 4번 던졌을때는 5/16가 되겠죠

    문제를 공유해보려고 올려봅니다. 명쾌한 해답을 아시는 분의 답변도 듣고 싶고요. 인터뷰 끝나고 고민해도 잘 안풀리네요. 어떤 공식이 있을것 같은데 말입니다.

    • 일자리구함 211.***.50.67

      이거 풀면 거기 들어갈수 있는건가요? ㅎㅎ
      암튼 답은 10K 입니다. 확률은 횟수가 증가할수록 원래 가져야 할 수치로 수렴할테니 가면 갈수록 50%로 수렴하겠죠 즉 100K로 갈수록 Hat이 60%이상 나올 확률은 없어진다는 얘깁니다. bdc

    • . 71.***.94.58

      똑같지 않나요?
      어차피 정규분포를 따를 텐데, hat이 60% 이상 나올 확률은 동일할 것 같습니다.

    • 씨애틀 131.***.0.74

      딴지인데요. head 아닌가요.

    • 답은 74.***.190.210

      10K입니다. 두 경우 모두 시행수가 충분히 많기 때문에 이항분포가 정규분포로 근사하고 평균은 동일하고 분산이 다릅니다. 실제로 확률을 구해보면 10K의 경우가 100K 보다 작습니다. 물론 차이가 Practically insignificant합니다만…

    • 이어서 74.***.190.210

      완전 동일하지는 않지만 비슷하면서 유명한 문제가 Gambling과 관련해 존재하는데 1)독립적으로 시행되는 2)승률이 플레이어에게 불리하게 설정된 게임의 시행수가 늘어날 수록 가진 돈을 다 잃을 확률이 높아집니다. 주어진 경우가 바로 이에 해당합니다.

    • 실제로 74.***.190.210

      유명한 세팅은 $100 가지고 카지노를 향하는 남자가 있는데 다음 날까지 $1000을 벌어 마피아게게 갚지 않으면 죽게 됩니다. 오직 $1000을 다 갚아야만 살 수 있습니다. 승율이 50% 미만이 게임을 계속한다고 가정할 때 어떻게 베팅하는 것이 최선일까요? $10씩 꾸준히 또는 항상 가지고 있는 최대 액수를? 답은 후자

    • 키히 118.***.214.137

      느낌이 팍 오도록 예를 들어보자면, 과장해서, 10번 던져서 6번 이상 앞이 나올 확률과 10만번 던져서 6만번 이상 앞이 나올 확률을 비교한다고 생각하면 이해가 빠를 것입니다. (첫번째는 의외의 수(bias)가 한번만 일어나도 되지만, 두번째는 만번이나 더 일어나야 하는 것이지요)

      @ 그리고 이항분포는 충분히 간단한 식이라서 정규분포로 근사하지 않아도 10% bias될 확률을 계산하는 것이 어렵지 않습니다.
      1만번 시행에서 이길 확률은 sum_{x=from 6000 to 10000} {0.5^x * 0.5^(10000-x)}
      10만번 시행은 sum_{x=from 60000 to 100000} {0.5^x * 0.5^(100000-x)}

    • sk 131.***.0.106

      면접내용은 저거 푼다 못푼다가 요지가 아니죠.
      일단 인터뷰이는 대부분 못 풀텐데, 저 문제를 어떻게 접근할 수 있는지를 볼겁니다.

    • 지나가다 71.***.81.70

      10,000번 던진다고 해서 이길 확률이 있다고 보기는 어렵겠네요. Fair 한 coin이고, Fair한 trial 이라면, 100k, 10k, k면 1000이라고 할 때 1,000,000번 던지나, 10,000번 던질 때 1/2로 Head, 1/2로 tail이 나올 것입니다. 즉 99.9% 진다는 것이며, 위에 어느분이 쓰신대로 차이가 practically insignificant하네요.