ゆがんだコインがあるとしよう。表が出る確率 $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$ 回の投げが必要になる。

フォン・ノイマンの方法は、ランダムネス抽出器の祖先である。ランダムネス抽出器は、回路の電気的な雑音やマウスの動きのような不完全な偶然の源を、暗号が要求する一様なビットに変える。

練習：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$ 回の投げになる。

練習：一回投げではなぜだめか

ある人がこう提案する。「一回投げて、表なら、もう一回投げて二回目の結果を使う。」これは公平か。

公平ではない。二回目の投げもやはり偏っており、一回目が何であれ確率 $p$ で表が出る。一度に一回の投げしか見ない規則は、$p$ を知らないかぎり偏りを正せない。フォン・ノイマンの工夫が効くのは、二回の投げを比べ、「表、裏」と「裏、表」という二つの順序の対称性を使うからである。

出典： John von Neumann, “Various techniques used in connection with random digits”, National Bureau of Standards Applied Mathematics Series 12（1951）· Persi Diaconis、Susan Holmes、Richard Montgomery, “Dynamical bias in the coin toss”, SIAM Review（2007）。

ジョン・フォン・ノイマンの全トピック · ← モンテカルロ法：サイコロを振って計算する · 自己増殖オートマトン →

画像クレジット.