미지의 고정 p는 0<p<1/2이고, 매번 독립으로 1이 나올 확률이 p인 장치를 사용할 수 있어요. 미리 정한 유한 최대 횟수 N번 안에 반드시 끝내고 Y∈{0,1}을 내는 새 규칙을 만들려고 해요. 보조 난수도 허용해요. 그 분포는 p와 무관하고, 보조 난수는 입력 Bernoulli 전체 열과 독립이에요. 출력 규칙 자체도 p에 의존하지 않으며 p의 실제 수치를 몰라요. 모든 허용 p에서 P(Y=1)=2p로 만들 수 있나요? 2p는 이미 0~1 안에 있어요.
일찍 종료한 규칙도 남은 입력을 읽고 사용하지 않는 것으로 생각하면 N개짜리 패턴 w만으로 표현할 수 있어요. w가 고정됐을 때 보조 난수에 의해 1을 출력할 확률을 q_w∈[0,1]이라 둘게요. 보조 난수는 입력 전체 열과 독립이고 그 분포와 출력 규칙이 p와 무관하므로, 고정한 w에서 q_w도 p와 무관해요. 패턴에 들어 있는 1의 개수를 s(w)라 하면
이는 차수가 N 이하인 다항식이에요. (0,1/2)의 모든 p에서 F(p)=2p라면 F(p)−2p는 무한히 많은 근을 가져요. 0이 아닌 유한 차수 다항식은 그럴 수 없으므로 항등적으로 0입니다. 이 다항식 항등식에 p=1을 대입하면 F(1)=q_(모두1)=2가 돼요. q가 1 이하라는 조건과 모순이어서 어떤 미리 정한 유한 N도 불가능해요. 실제 장치에 허용 밖 p=1을 입력한 실험이 아니라, 성립해야 할 다항식 항등식을 검사한 거예요.
한 번 읽고 값 2X를 출력하면 평균은 2p지만 결과가 0 또는 2여서 이진 출력이 아니에요. 실수 추정값의 평균을 맞추는 규칙과 1이 나올 확률을 맞추는 장치를 구별해야 해요.
Huber의 실제 원문은 미지 확률 시행과 보조 난수로 새 Bernoulli 출력을 만들며 정지 횟수가 무작위일 수 있는 설정을 정의해요. 현재는 고정된 유한 상한이라는 별도 제약에서 불가능성을 직접 증명했어요. 이 결론을 무작위 정지시간을 가진 모든 다른 설계의 불가능성으로 넓히지 않으며 원문의 구현·성능 수치를 재현했다고 쓰지 않아요.
목표가 0~1 범위인지 확인한 뒤에도 어떤 입력 정보와 자원을 허용하는지 적어 봐요. 규칙의 조건부 출력확률은 p에 의존해 정할 수 없어요. 항등식 검산에서 허용 밖 값을 넣는 대수적 논증과 그 입력을 실제로 제공하는 장치를 분리해 설명해요.
착안 원문: Mark Huber, Nearly optimal Bernoulli factories for linear functions. 유한 횟수 상한의 조건과 다항식 불가능성 증명은 자체 문항이며 원문의 알고리즘을 구현하거나 성능을 측정한 결과가 아니에요.