乱数生成と情報源符号化 - なぜか数学者にはワイン好きが多い

タイトルは，

星守，乱数生成と情報源符号化，応用数理，Vol. 8，No. 2，pp. 38--52，1998

のものです．
この論文に，次のような例題が載っていました．

表と裏がでる確率が，それぞれp，1-pであるコインを使って，正確に1/2の確率で出現する0,1の2進列を生成したい．すなわち，偏ったコインを使って正しいコインをシミュレートしたい．ただし，pは未知であることに注意．

問題提起も，その基本的な解法も，フォン・ノイマンの1951年の論文だそうです．

表が出る確率pが大きかったら，コインを振った結果は表が多くなるはずで，例えば表表裏表裏表表表表裏表裏表表．．．みたくなるはずです．この結果から，表と裏の出る確率を同等にすると．

ノイマンによる解答は，次のようなものだそうです．

偏ったコインの出力列が，「表裏」なら0を，「裏表」なら1を出力し，「表表」「裏裏」のときは何も出力しない

なるほどぉ．．．

表が出る確率がp，裏が出る確率が1-pなら，「表裏」が出る確率はp(1-p)です．「裏表」が出る確率は，(1-p)pです．値としては同じですね．もちろん，「表表」の確率はp^2，「裏裏」は(1-p)^2です．

例で上で出した，「表表裏表裏表表表表裏表裏表表」（←表の方が出る確率が高い）でやってみると．．．

出力結果は，

01010101

ちょっと完璧すぎるくらい，0と1の出現確率が1/2になりました．
（サンプリングの仕方や入力の長さによりますから，こんな完璧には実際にはならないでしょう）

面白いですね．純粋数学では幾何学くらいしか関心が無かったのですが，もっとも苦手だった確率統計に凄く興味が沸いてきました．