문제는 여기: https://arca.live/b/math/51620797
4. 앞면이 나올 확률이 1/2016인 동전만을 사용하여, 성공률이 정확하게 0.2016인 시행을 만들어라.
이 문제는 "길이가 무제한인 시행"을 이용하면 된다. 시행의 길이는 무제한이라도 길이의 기대값은 유한이므로 시행을 무한히 계속하게 되지는 않는다.
길이가 무제한인 시행의 간단한 예는 다음과 같다.
(문) Fair coin(앞면이 나올 확률 = 뒷면이 나올 확률 = 1/2)을 이용해서 성공률이 1/3 인 시행을 만들라.
(답) 동전을 2번 던져서 모두 앞면이면 성공, 앞면 한 번에 뒷면 한 번이면 실패라고 한다. 두 번 모두 뒷면이면 다시 던진다.
(성공할 확률은 무한급수의 합으로 구할 수도 있지만, 실패할 확률이 성공할 확률의 2배이므로 성공할 확률은 당연히 1/3 이다.)
이제 길이가 무제한인 시행을 이용해서 임의의 동전을 이용해서 성공률이 0과 1 사이의 임의의 유리수인 시행을 만든다.
(1) 임의의 동전을 이용해서 fair coin 을 시뮬레이션한다.
- 첫 번째가 앞면이고 두 번째가 뒷면이면 F, 첫 번째가 뒷면이고 두 번째가 앞면이면 B 로 간주한다.
- 두 번 모두 앞면이거나 두 번 모두 뒷면이면 처음부터 다시 던진다.
이렇게 하면 F 와 B 가 나올 확률은 서로 같으므로 각각 1/2 이다.
(2) 시뮬레이션된 fair coin 을 이용해서 성공률이 주어진 유리수인 시행을 만든다.
주어진 성공률을 n/m 이라 하자. (n과 m 은 양의 정수, 0 < n < m)
k 는 2^k ≧ m 을 만족하는 자연수라 하자. 이제 fair coin 을 k 번 던져서 각각 앞면이 나오면 1, 뒷면이 나오면 0을 쓴다.
그러면 0과 1로 이루어진 길이 k 인 문자열을 얻는다. 이를 2진수로 간주하고, 그 값을 v라 한다.
- v가 n보다 작으면 성공, n 이상이고 m 보다 작으면 실패로 한다.
- v가 m보다 크면 처음부터 다시 던진다.
0 ≦ v < 2^k 이고 각 v값이 나올 확률은 1/2^k 로 모두 같으므로 이 시행이 성공할 확률은 n/m 이다.
