치우친 동전으로도 공정한 0·1을 만들 수 있을까요? 교사는 네 번의 앞뒤 기록16개를 적은 뒤, 각 기록에 0·1·버림 중 하나를 미리 붙이게 해요. 앞면은 H, 뒷면은 T입니다. H의 확률 p는 0과1 사이지만 모르며, 네 번은 같은 p로 독립 시행해요. 더 던지거나 다른 추첨을 하지 않아요. 실제 동전을 평가하는 실험은 아니에요.
공정하다는 뜻은 기록을 버리지 않은 경우에 0과1의 확률이 각각1/2라는 거예요. 기록을 남길 확률은 양수여야 해요. 단 한 p가 아니라 모든 p에서 이를 만족하면서 가장 많은 기록을 남겨라. 규칙은 p에 따라 바꾸지 않아요. 앞면 k개인 기록 중 0을 붙인 수를 a_k, 1을 붙인 수를 b_k라 해 볼까요?
같은 k의 기록은 확률이 같아요. 왼쪽을 (1−p)의 네제곱으로 나누고 t=p/(1−p)로 놓으면, 모든 양수 t에서 0인 다항식이에요. 계수가 모두0이므로 앞면 개수별로 두 출력을 같은 수씩 배정해야 해요. 각 묶음의 크기는1·4·6·4·1입니다. 따라서 HHHH와 TTTT는 반드시 버리고 나머지14개는 모두 남길 수 있어요.
남기는 기록 수의 최대를 N_max, 그 최대를 이루는 규칙 수를 R, 최대 규칙의 기록을 남길 확률을 Q(p)라 해 볼까요?
크기4·6·4의 각 묶음에서 절반에0, 나머지에1을 붙이면 돼요. 예컨대 앞면2개 묶음은 HHTT·HTHT·HTTH에0, THHT·THTH·TTHH에1을 줘요. 다른 두 묶음도 절반씩 골라요. 0과1을 맞바꾼 규칙은 별개로 세어요. 교사는 총 개수만 같게 나눈 답에 앞면 개수별 균형도 요구해요. p=1/2에서만 공정한 규칙으로는 이 질문을 해결하지 못해요.
착안: NIST의 편향 동전에서 공정한 비트를 얻는 설명. 네 번으로 끝내는 규칙·최대와 전체 구성은 자체 교육 모형이에요.