골드만 삭스 퀀트 면접 문제 중

브레인 티저가 올라오는 블로그 CSE Blog를 가끔 보는데, 이 블로그에 따르면 골드만 삭스 퀀트 면접문제에 이런 질문이 나왔다고 한다.

Value of Pi – Estimation using Dice in CSE Blog

주사위 하나로 원주율을 추정하시오.
Estimate the value of pi using a dice.

아무래도 뷔퐁의 바늘 문제 비스무리하게 풀지 않을까 싶다. 근데 바닥에 선 그어서 던져 푸는 거 말고 쌈빡한 아이디어 없을까?

 


2014.4.8
주사위 숫자와 계산만으로 기대값이 원주율에 수렴하는 방법에 대해 곰곰 생각해봤는데, series를 이용하면 될 것 같다. 설명의 편의상 라이프니츠 공식을 쓰고 있긴 하지만, 더 빠른 수렴 공식에도 적용가능하다.

1이 나올 때까지 주사위를 던진 회수를 확률변수 X라고 하면, 확률분포는 P(X=n)= \left( \frac{5}{6} \right)^{n-1} \cdot \frac{1}{6} 이 된다. 그래서 이를 반복 시행하여 \frac{24}{2X-1}\left( -\frac{6}{5}\right)^{X-1} 의 값을 반복 계산한다. 이 시행의 평균값은 다음과 같이 원주율에 수렴하게 된다.

\displaystyle \begin{gathered} E\left(\frac{24}{2X-1}\left( -\frac{6}{5}\right)^{X-1} \right) \hfill \\ \qquad = \sum_{n=1}^{\infty} \frac{24}{2n-1}\left( -\frac{6}{5}\right)^{n-1} \left( \frac{5}{6} \right)^{n-1} \cdot \frac{1}{6} \\ \qquad = 4 \sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2n-1} \hfill \\ \qquad = \pi \hfill \end{gathered}

뭐 그냥 원주율이 되도록 앞에 식을 끼워 넣은 것에 지나지 않지만… -_-

본인이 생각한 방법이 하나 더 있다. 주사위를 여섯 번 던졌을 때 나온 숫자를 a, b, c, d, e, f라 하면 다음 식이 성립하는 사건을 X라 하자.

\displaystyle \left( \frac{a-1}{6}+\frac{b-1}{6^2}+\frac{c-1}{6^3}\right)^2 + \left( \frac{d-1}{6}+\frac{e-1}{6^2}+\frac{f-1}{6^3}\right)^2 <1

전체사건에서 X가 일어난 비율을 4배하면 원주율에 수렴한다. 왜 그럴까? ㅋㅋ 그 이유는 기하학적으로 위 식이 사실 6진법으로 소수점 이하 세 자리수까지 [0,1]x[0,1] 박스안의 임의의 한 점을 선택해서 단위원 안의 점인지 확인하는 계산이기 때문이다. 따라서 확률은 사분원의 넓이가 된다. 정확도를 높이고 싶으면 자리수를 늘리면 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중