偏りのあるコインを使ってより厳密に五分五分の確率を判定するにはどうすればいいのか？

コインを投げた時に表が出る確率と裏が出る確率は理論上等しく2分の1になります。ここで、表が出る確率が2分の1にならない「偏りのあるコイン」を想定した時、「偏りのあるコインを使って2分の1という公平な確率を表現するためにはどのように操作すればいいのか」という問題について、データサイエンティストのマートン・トレンチェニ氏がPythonを使って解説しています。

Bytepawn - Marton Trencseni – Fair coin from biased coin
https://bytepawn.com/fair-coin-from-biased-coin.html

コインを投げた時に表(2進数で0)が出る確率をp、裏(2進数で1)が出る確率を(1-p)と表現する場合、偏ったコインだとp≠(1-p)となります。

この偏ったコインの確率であるpと(1-p)を使って確率2分の1の乱数をより公平に出力できるようなアルゴリズムについて、トレンチェニ氏は以下の3つの解法を考案しています。

・ノイマンの確率論的解法
ノイマンの確率論的解法はその名の通り、20世紀を代表する数学者であるジョン・フォン・ノイマンの確率論に基づいた方法で、偏ったコインを2回投げた結果が表裏＝[01]なら「0」、裏表＝[10]なら「1」を返します。そして、[00]あるいは[11]なら再試行します。この解法は、[01]と[10]はどちらも同じp(1-p)という確率で発生するというのがポイント。

この解法をPythonでコーディングしたものが以下になります。

def probabilistic(biased_coin):
    while True:
        s, w = biased_coin(), biased_coin()
        if s == 0 and w == 1:
            return 1
        elif s == 1 and w == 0:
            return 0

ノイマンの確率論的解法は2回のコイン投げの結果だけを見るので、理解しやすく実装も容易。また、直前の2回の投げ結果だけを記憶すればよいので、メモリ使用量が少なくて済みます。そして、長期的には完全に公平な結果を生成できることが数学的に証明されています。ただし、再試行される可能性が高いため、入力に対する出力の割合が低くなるのが弱点。特に偏りが大きい場合は効率が著しく低下するため、コインの偏りによっては適していない方法といえます。

・統計的解法
統計的解法は、コインをN/2回投げて偏りを測定し、その平均を推定値p₁とします。そしてさらにN/2回投げて得られた二回目の推定値をp₂とします。そして、p₂＞p₁であれば「1」を、p₁＞p₂であれば「0」を返します。要するにコインをN回投げた時に、前半の方が後半よりも表の出る回数が多かったら「1」を、後半の方が多かったら「0」が出力されるという処理です。正規分布に従えば、「p₂＞p₁となる確率」と「p₁＞p₂となる確率」は同じになります。

コードは以下の通り。

def statistical(biased_coin, N):
    while True:
        num_flips = int(N/2.0)
        s = sum([biased_coin() for _ in range(num_flips)])/num_flips
        num_flips = N - num_flips
        w = sum([biased_coin() for _ in range(num_flips)])/num_flips
        if s < w:
            return 1
        elif s > w:
            return 0

統計的解法は比較的簡単に実装できますが、完全な公平性は保証されません。また、Nを大きくすると精度は上がりますが、効率は下がります。

・順列解法
順列解法はHacker Newsにあったコメントに基づいた解法です。コインをN回投げて表が出たら[0]、裏が出たら[1]を記録して、最終結果となるN桁のビット列を入力する時、そのビット列が辞書順で逆のビット列よりも大きければ「1」を、小さければ「0」を返します。ただし、ビット列とその逆順が同じ場合は再試行します。

例えば、N=5の場合は[10011]や[00101]など、2⁵=32通りのビット列が得られます。N=5で表が3回出たケースだと、[11000][10100][10010][10001][01100][01010][01001][00110][00101][00011]という10通りのビット列が考えられます。[00011]が入力された場合、逆順の[11000]よりも小さいので出力結果は「0」となります。ただし、[10001]と[01010]は逆順にしても同じになる回文パターンなので除外され、再試行されます。

この順列解法をPythonで表現するとこんな感じ。

def permutations(biased_coin, N):
    while True:
        inst = ''.join([str(biased_coin()) for _ in range(N)])
        revr = inst[::-1]
        if inst > revr:
            return 1
        elif inst < revr:
            return 0

表が出た回数がk回とすると、特定のビット列が得られる確率はp^k(1-p)^N-kとなります。重要なのは、表が出た回数＝kを持つすべてのビット列は同じ確率で出現するということです。つまり、同じkを持つすべてのビット列のペアにおいて、元のビット列が中央値より大きい確率と小さい確率が常に等しくなります。この方法はコインの偏りを調べる必要がなく、理論的には完全に公平な結果を生成できる点が特徴ですが、回文パターンのビット列が出た場合に再試行が必要となるなため、やはり効率面では劣る可能性があります。

トレンチェニ氏は、ノイマンの確率的解法、統計的解法、順列解法という3つの解法を実装して比較した結果、すべての方法は正確性と効率性で同等であると評価。一見異なる原理に基づいているように見える3つの解法は、本質的には同じアルゴリズムを別の視点から表現しているに過ぎないと論じています。

そして、トレンチェニ氏は「偏りのあるコインを使って2分の1という公平な確率を表現する問題」をより一般化した「決定論的乱数抽出」の概念について説明しています。

Bytepawn - Marton Trencseni – Randomness extractors: making fair coins out of biased coins
https://bytepawn.com/randomness-extractors-making-fair-coins-out-of-biased-coins.html

決定論的乱数抽出の主な目的は、偏りや相関のある入力ビット列から、統計的に均一で予測不可能な出力ビット列を生成することです。「決定論的」という言葉はその過程が再現可能であること、つまり同じ入力に対して常に同じ出力が得られることを意味します。

トレンチェニ氏は決定論的乱数抽出の核として、「エントロピーの濃縮」を挙げています。情報理論におけるエントロピーは、情報の不確実性や予測不可能性の度合いのこと。完全にランダムなビット列だと、各ビットのエントロピーは1ビットになり、次のビットが0か1かを全く予測できませんが、偏りのあるビット列では各ビットのエントロピーが1未満になります。

例えば75％の確率で表が出るコインを10回投げた場合、それぞれの結果は表が多く出る傾向にあり、完全なランダムではありません。そこで、1つ1つの結果ではなく、10回の結果をまとめてチェックすることで、よりランダム性の高い情報を取り出すというのがトレンチェニ氏のアイデアです。10回分の結果を1回分にまとめてしまうので元の情報量は減ってしまいますが、ランダム性はより高まるというわけです。

トレンチェニ氏はこのエントロピーの濃縮を応用した「パリティ抽出」を考案しています。これは、偏りのあるビット列をN個ずつにまとめ、そのビット列に含まれる1の数が偶数なら「0」を、奇数であれば「1」を出力するという方法です。

例えば入力ビットが[0101 1110 1010]で、N＝4で処理を行う場合、[0101]は1が2個なので「0」、[1110]は1が3個なので「1」、[1010]は1が2個なので「0」となり、結果として「010」が出力されます。Nの値が大きいほど出力のランダム性は向上しますが、その分出力ビット数は減少します。

また、トレンチェニ氏は、入力ビットが「マルコフ連鎖」によって生成される場合、ノイマンの確率的解法を適用して生成されるビット列から公平な乱数を抽出する「Blum抽出」も紹介しています。

Blum抽出のポイントは、偏ったコインを投げた結果それぞれに対して、最後に出た結果を覚えておくという点です。もし表の次に裏が出たら1を出力、裏の次に表が出たら0を出力、同じ結果が続いたら何も出力せず、結果を更新します。この方法はコインの偏りを知らなくても使うことができ、出力される0と1の数は元の投げの回数より少なくなりますが、その分だけ公平性が高まります。

トレンチェニ氏は、入力ビット列の構造について何もわからない完全に一般的な場合だと、均一な乱数を生成することは不可能だと述べた上で、「パリティ抽出器やBlum抽出器などを使うことで、入力源に関する部分的な情報や仮定があれば、効果的な乱数抽出が可能」と論じています。

これらの方法の有効性を実証的に検証するため、生成された出力ビット列の乱数性を統計的にテストする必要があるとして、自作の乱数抽出器のコードとテストした結果をGitHubで公開しています。

playground/Randomness Extractors.ipynb at master · mtrencseni/playground · GitHub
https://github.com/mtrencseni/playground/blob/master/Randomness%20Extractors.ipynb