ゆがんだコインがあるとしよう。表が出る確率 $p$ はわからない。$0.7$ かもしれないし、$0.55$ かもしれない。これを使って、完全に公平な、五分五分のくじ引きができるだろうか。 乱数をつくる者の「罪の状態」について語ったのと同じ 1951 年の論文で、フォン・ノイマンは短く意外な答えを与えた。 工夫 コインを二回投げる。 表、裏と出たら「表」とする。 裏、表と出たら「裏」とする。 表、表か裏、裏と出たら、それは忘れて、もう二回投げる。 なぜ公平なのか。二回の投げは独立なので、 $$P(\text{表、裏}) = p\,(1-p), \qquad P(\text{裏、表}) = (1-p)\,p.$$$p$ が何であっても、これらは同じ数である。同じ結果の組は捨てられ、残った結果の中では表と裏がまったく同じ確率をもつ。コインがどれだけ偏っているかを知る必要はない。投げどうしが互いに影響しないことだけが必要なのだ。 代償 代償は組を捨てることだ。一組が使える確率は $2p(1-p)$ である。公平なコイン $p = \frac12$ なら、一組が使える確率は $\frac12$ で、結果一つあたり平均 $2$ 組、つまり $4$ 回の投げが要る。ひどく偏ったコインでは代償が急に大きくなる。$p = 0.9$ なら、一組が使える確率は $2 \times 0.9 \times 0.1 = 0.18$ しかなく、結果一つあたり平均およそ $11$ 回の投げが必要になる。 フォン・ノイマンの方法は、ランダムネス抽出器の祖先である。ランダムネス抽出器は、回路の電気的な雑音やマウスの動きのような不完全な偶然の源を、暗号が要求する一様なビットに変える。 コインは決して完全には公平でない 2007 年、数学者パーシ・ダイアコニス、スーザン・ホームズ、リチャード・モンゴメリーは、親指でふつうにはじいて投げたコインが、投げ始めと同じ面を上にして落ちる確率は半分より少し高く、およそ 51% であることを示した。2023 年には、35 万回を超える投げの実験がこの効果を確かめた。各組の二回の投げが独立であるかぎり、フォン・ノイマンの工夫はこの偏りを取り除く。 練習：70% のコイン$p = 0.7$ として、各種類の組の確率と、結果一つあたりの平均投げ回数を計算せよ。 $P(\text{表、表}) = 0.49$、$P(\text{裏、裏}) = 0.09$、$P(\text{表、裏}) = P(\text{裏、表}) = 0.21$。一組が使える確率は $0.42$ である。最初に使える組までの組数の平均は $\frac{1}{0.42} \approx 2.4$、つまり結果一つあたりおよそ $4.8$ 回の投げになる。