靴飛ばしで公平なコイントスを

こんにちは。

コイントスってありますよね。コインを指ではじいて表か裏かを見る行為です。

均等な形のコインなら表と裏の出る確率は1/2で等しく、お互いがコイントスに同意した場合、公平な勝負となるわけです。

コイントスはじゃんけんと比べて、より公平、八百長がしにくい、といった特徴があり、サッカー、テニス、ラグビーといったスポーツのルールでも使われています。

ところで、歪んでいるコインでも、実質表と裏が1/2ずつの公平なコイントスができることをご存じでしょうか。

フォン・ノイマンの方法

コインの表と裏を、H (Head)とT (Tail)で表すことにします。連続で投げた結果、たとえば3回投げた結果を、HTTのようにつなげて表すことにします。

また、実際のコインの表裏と区別するために、結果としての表と裏を、表判定、裏判定と表現することにします。表扱い、裏扱い、と同じ意味です。

このとき、偏りのあるコインで公平な1/2の結果を得る方法は以下になります。

偏りのあるコインによる公平なコイントスの方法

2回コイントスして、結果が「HT」なら表判定、「TH」なら裏判定とする。「HH」や「TT」の場合は再び2回コイントスして、「HT」か「TH」が出るまで繰り返す。

この手法を正式な場で初めて示したのは、あのフォン・ノイマンとされています。（現在のコンピュータの理論面を考えた人です）

1951年の論文「Various Techniques Used in Connection With Random Digits」の中で触れられています。

この手法は、表と裏に偏りがあるコインでも、2回投げた時の「HT」と「TH」の確率が等しいことを利用しています。

面白いのは、「どのように偏りがあるか」ということを知らなくても使えることです。ただし、表と裏の出る確率はどちらも0ではないことが前提です。

この方法によって、天気を占う靴飛ばしや、そこら辺に落ちてる葉っぱの裏表であっても、ほぼ均等な1/2の結果を得ることができるようになります。森の中、着の身着のままの時に、分かれ道で迷っても安心です。

さて、この方法で無事、偏りのあるコインでも1/2の結果を出せるわけですが、この話はいくつかの方向に発展させることができます。

この方法はどのぐらい効率的なのか。より効率的な方法はあるのか、一番効率的な方法は何か
サイコロなど出る目の数が3種類以上になったらどうか

この記事では、これらの問いを考えていきます。

補足

フォンノイマンの方法について、少し補足しておきたいことがあります。

フォンノイマンの方法では、2回ずつコイントスをする必要があります。

たとえば「HHT」のように出たとしても、2回目と3回目の結果から表判定としてはいけません。その理由は、2回目と3回目の結果をひっくり返してみると分かります。ひっくり返すと「HTH」となりますが、これも1回目と2回目で表判定となってしまいます。

（全部をひっくり返した「TTH」は、表の数が違うので、確率も異なります。）

3回投げて表が2回出るパターンは3パターンですが、そのうちの2つを表判定とすると、表に偏ったコインだった場合に、表判定になりやすくなってしまうのです。

効率について：何回はじけばいいのか

フォンノイマンの方法では「HH」や「TT」はやり直しになり、それだけ多くコイントスをすることになります。

偏りのあるコインを実際に使う場面があるかは別として、できるだけコイントスの回数が少ない方が望ましいでしょう。

そこで、コイントスの回数がより少なくて済む方法がないか考えます。

まず手始めに、フォンノイマンの方法を使った時のコイントスの平均回数を計算してみましょう。

問1

偏りのあるコインで公平なコイントスを再現するフォンノイマンの方法では、判定が出るまでに平均何回コイントスをすることになるか。

コインの表が出る確率をpとします（0<p<1）。裏の出る確率は(1-p)です。

コインを2回投げて、「HT」「TH」になる確率はそれぞれ $p(1-p)$ なので、コインを2回投げて判定が決まる確率は、合わせて $2p(1-p)$ となります。

統計学上、確率rの事象が起きるまでの平均試行回数はその逆数1/rになるため、1回の試行でコインを2回投げることを考慮すると、フォンノイマンの方法での平均コイントス回数Eは、

$E=\dfrac{1}{2p(1-p)}\times 2=\dfrac{1}{p(1-p)}$

となります。

p=0.5の公平なコインなら平均4回、p=0.2の偏ったコインなら平均6.25回、コイントスが必要になります。

一般に、コインの表裏に偏りがあるほど、平均回数は増えます。それもそのはず、たとえばp=0.0001だったら、まず、表が出るまでに時間が掛かりますから。

答1

コインの表が出る確率をpとしたとき、平均 $\dfrac{1}{p(1-p)}$ 回。

もっと効率的な方法

では、もっとコイントスの回数が少なくて済む、効率的な方法はあるでしょうか。

問2

フォンノイマンの方法よりも、コイントスの回数を真に減らせる方法はあるだろうか。

コインを3回投げた結果を見てみましょう。フォンノイマンの方法で判定が付かない組合せは、「HHH」「HHT」「TTH」「TTT」の4通りです。

Hの数が一致する事象が等確率で起きます。Hの数が同じ、等確率の事象が2つ以上残っていれば、表判定と裏判定で分配することができるのですが、この4通りはすべてHの数が異なっています。そのため、3回投げた場合の判定条件をこれ以上増やすことはできません。

コインを4回投げた結果を見てみましょう。フォンノイマンの方法で判定が付かない組合せは、「HHHH」「HHTT」「TTHH」「TTTT」の4通りです。今度はHとTの数が一致しているケースがあります。「HHTT」「TTHH」です。これらをそれぞれ「HT」と「TH」のように捉えて、表判定、裏判定とすれば、やり直しのケースを減らすことができます。

答2

ある。

「HHTT」や「TTHH」を、「HT」や「TH」と同様に扱う方法はさらに拡張出来ます。

コインを8回投げた結果のうち、今の拡張を含めても判定が付かない組合せは、「HHHHHHHH」「HHHHTTTT」「TTTTHHHH」「TTTTTTTT」の4つです。

（「HHTT」等の判定も4つ区切りで行うことに注意してください）

今度は「HHHHTTTT」と「TTTTHHHH」でHの数が一致していますね。なので、これらを「HT」「TH」と同様に、表判定と裏判定の条件にすることができます。

4区切り、8区切り、16区切り、……と以下同様に判定条件を増やすことができます。

このアイデアは、2022年の篠原拓也氏のコラムでも言及されています。しかし、その記事の参考文献がまだ確認できておらず、篠原氏の考案なのかは分かりません。

歪んだコインの活用法－フィフティ・フィフティの確率をどう作る? |ニッセイ基礎研究所

拡張した方法

今さっきの拡張した方法を、そのまま「拡張した方法」と呼ぶことにします。

改めて、その判定方法をまとめておきましょう。

拡張した方法

いずれかの判定が出るまでコイントスする。
コイントスの結果列を先頭から2つ区切りで見た時に、「HT」があれば表判定、「TH」があれば裏判定とする。
先頭から4つ区切りで見た時に、「HHTT」があれば表判定、「TTHH」があれば裏判定とする。
先頭から8つ区切りで見た時に、「HHHHTTTT」があれば表判定、「TTTTHHHH」があれば裏判定とする。
以下同様。

拡張した方法の効率

この拡張した方法は、コイントスの結果を覚えておかなければならない代わりに、より早く結果を出せます。

すると、どの程度コイントスの回数が減ったか気になるところです。

問3

拡張した方法では、判定が出るまでに平均何回コイントスをすることになるか。

色々触ってみた感じ、複雑な式になりそうです。

n区切りまでの拡張のみを採用した場合の平均コイントス回数を $E_n$ とおきます（ $n=2^m$ ）。すべての拡張を採用した場合の平均コイントス回数を $E'$ とおきます。

フォンノイマンの方法での平均回数は $E_2$ のことで、 $E_8$ は、2つ区切り、4つ区切り、8つ区切りのルールを採用した場合の平均回数です。

$E_2=\dfrac{1}{p(1-p)}$

4つ区切りまで採用した場合

$E_4$ から少しずつ計算します。

$E_4=2\times 2p(1-p)+4\times p^2 (1-p^2)+4\times (1-p)^2\{(1-(1-p)^2\}+(4+E_4)\{p^4+(1-p)^4\}$

この式を説明すると、

最初の2回が「HT」か「TH」の場合に2回で決まる
最初の2回が「HH」で、続く2回が「HH」以外なら、4回で決まる
最初の2回が「TT」で、続く2回が「TT」以外なら、4回で決まる
それ以外の「HHHH」と「TTTT」の場合には、 $4+E_4$ 回で決まる

といった具合です。

一応このぐらいの式なら、紙での計算もできますが、数式を整理してくれるサイトを使うと便利です。そういうサイトの例としては、「Wolfram Alpha」があります。

Wolfram|Alpha Examples: 数学

今回は検算に利用しました。結果は、

$E_4=\dfrac{2(1-p+p^2)}{p(1-p)(2-p+p^2)}$

となりました。もちろんこの値は、0<p<1において、 $E_2$ より小さくなります。

p=0.5の公平なコインなら平均約3.43回で、p=0.2の偏ったコインなら平均約5.71回でした。それぞれ、最初の方法と比べて約0.6回分、約0.5回分減っています。

下のリンクでpの値を変えて $E_4$ を計算できます。

x=2p(1-p)2+p^2(1-p^(2))4+(1-p)^(2)(1-(1-p)^(2))4+(p^(4)+(1-p)^(4))(4+x), p=0.2 - Wolfram|Alpha

8つ区切りまで採用した場合

$E_8$ はというと、Wolfram Alphaに計算してもらいました。（方程式は下にあるリンクを参照してください）

$E_8= -\dfrac{4 (p^2 - p + 1)^3}{p (p−1)(p^6−3p^5+11p^4−17p^3+18p^2−10p+4) }$

見た目を $E_4$ に合わせると以下のようになります。

$E_8= \dfrac{4 (1-p+p^2)^3}{p (1-p)(4-10p+18p^2-17p^3+11p^4-3p^5+p^6) }$

p=0.5の公平なコインなら平均約3.40回で、p=0.2の偏ったコインなら平均約5.70回でした。それぞれ、4つ区切りまで採用した方法と比べて約0.02回、約0.01回分減っています。

微々たる削減です。8区切りの「HHHHTTTT」や「TTTTHHHH」が活躍する機会は滅多にないことが分かります。

下のリンクでpの値を変えて $E_8$ を計算できます。

x=2p(1-p)2+p^2(1-p^(2))4+(1-p)^(2)(1-(1-p)^(2))4+p^4(2p(1-p))6+(1-p)^4(2p(1-p))6+p^6(1-p^2)8+(1-p)^6(1-(1-p)^2)8+p^4(1-p)^2 8+(1-p)^4 p^2 8+(p^8+(1-p)^8)(8+x) - Wolfram|Alpha

裏の出る確率(1-p)をqにおいたバージョンもあります。

q=1-p, x=2pq 2+p^2 (1-p^2) 4+q^2(1-q^2)4+(p^4+q^4)(2pq)6+p^6(1-p^2)8+q^6(1-q^2)8+p^4 q^2 8+q^4 p^2 8+ (p^8+q^8)(8+x), p=0.2 - Wolfram|Alpha

すべての区切りを採用した場合

さて本題の $E'$ ですが、厳密な式の形で求めるのは私の手には余ります。ですが、およその値なら、 $E_8$ が十分に表してくれています。

$E_8$ は上界として機能します。つまり、 $E'\lt E_8$ です。

先ほど見たように、 $E_4$ と $E_8$ の差は、最大で0.02程度でした。pが0.5のときが、最も拡張した方法の恩恵を受け、pが0や1に近づくほど恩恵は小さくなります。

また、 $E_{16}, E_{32}, \dots$ と、大きい区切りになっていくほど、その恩恵の割合は非常に小さくなっていきます。なぜなら、大きい区切りほど、それが現れる確率が指数的に低くなるからです。

たとえば、16区切りの採用を考えます。「HHHHHHHHTTTTTTTT」の採用によってどのぐらい $E_8$ より平均回数を減らせるかというと、もともと $16+E_8$ の回数必要だったのが、 $16$ になるため、 $（この事象の確率）\times E_8$ だけ平均回数を減らせることになります（正確には、これは先頭の場合のみですが、先頭以外で役に立つ可能性も指数的に減少します）。 $E_n$ というのは、簡単に下界も求めると、 $3\lt E_n\le E_2$ を満たす値です。つまり、定数以下の値です。指数減少と定数以下の式の積は、指数減少する式です。

ごちゃごちゃ書きましたが、大きい区切りのルールで減らせる平均コイントス回数は、指数的に減少していくことが分かります。

そして、その指数現象効果は、 $E_2, E_4, E_8$ の結果から、 $10^{-1}$ 以下と考えられ、 $E_8$ と $E'$ の差は、 $E_4$ と $E_8$ の差の上界0.025と、 $E_2$ の最大値4をかけて、せいぜい0.01以下と言えます。

答3

平均約 $\dfrac{4 (1-p+p^2)^3}{p (1-p)(4-10p+18p^2-17p^3+11p^4-3p^5+p^6) }$ 回。

厳密解との誤差はせいぜい0以上0.01以下。

計算機を使おう

数学的な解答はこれでいいんですが、今の時代はコンピュータがあるので活用していきましょう。

実際に、「拡張した方法」による判定をシミュレーションして、平均コイントス回数を計算します。プログラムのPythonのソースコードは以下になります。

test関数の引数のpが表の出る確率、cがシミュレーション回数です。特に読みにくい所はないと思います。

from random import random

def toss(p):
    assert(0 < p < 1)
    return 0 if random() < p else 1

# O(len(lst))
def judge(lst):
    k = 2
    while True:
        if k > len(lst):
            break
        if len(lst) % k == 0:
            a = [0] * (k // 2) + [1] * (k // 2)
            if lst[-k:] == a or lst[-k:] == a[::-1]:
                return True
        k *= 2
    return False

def test(p, c = 1000000):
    sum = 0
    for i in range(c):
        res = 2
        lst = []
        lst.append(toss(p))
        lst.append(toss(p))
        while not judge(lst):
            lst.append(toss(p))
            res += 1
        sum += res
    return sum / c

print(test(0.2))

さて、p=0.5とp=0.2で1000000回シミュレーションした実行結果は以下の通りです。

p=0.5の時、3.402522.
p=0.2の時、5.698784.

$E_8$ の値は、

p=0.5の時、 $E_8=3.401574\cdots .$
p=0.2の時、 $E_8=5.697534\cdots .$

です。 $E_8$ の式でおよその平均回数がちゃんと求められていることが分かります。

今回のシミュレーションの結果は、 $E_8$ より大きい値になっていますが、これは乱数による誤差の影響です。

最も効率的な方法

ところで、この「拡張した方法」は恐らく、不明な偏りのあるコインで公平なコイントスを再現する最も効率的な方法です。

命題1「拡張した方法は最も効率が良い」

2区切り、4区切り、8区切り、……（以下同様）……で見て判定する「拡張した方法」は、偏りのあるコインで公平なコイントスを再現する方法の中で、最もコイントスの回数が少なくて済む方法である。

直感としてはそうなんですが、証明はまだまとまっていません。この記事が結構長くなってしまったので、証明するにしても別の記事で行うことになりそうです。

もちろん、読者の皆さんに証明していただければ結構なことですけど。

他の発展問題

今回の話はコイントス、つまり0か1かの話でしたが、これが増えたらどうでしょうか。

問い

偏りのある6面サイコロで、公平な6面サイコロを再現するにはどうすればいいか。

すぐに思いつく方法としては、次の2つの方法があると思います。

出目のうち2種類をコインの表裏のように扱い、コイントスでの方法を適用して公平な2分の1の結果を得る。その3回の結果を2進数として読み、1～6をサイコロの結果に対応させる（0と7はやり直し）。また、2種類以外の出目が出た時はやり直す。
フォンノイマンの方法と同様に、6回振って1～6が1回ずつ出た時の、最初に出た数を採用する。

すべての目の出る確率が0でない時、これら2つの方法で公平な6面サイコロを再現できます。

1つ目の方法は、コイントスをサイコロ代わりにする方法を、偏りのあるサイコロに無理やり適用する方法です。やり直しが非常に多くなりそうです。また、偏りのあるサイコロは恐らく出やすい目と出にくい目があるので、振っていく中で、使う2種類の目を変えていく必要もあると思います。

2つ目の方法は、ノイマンテクニックの一般化といったところです。この方法の欠点は、ある目だけが極端に出にくい場合、その影響を受けてしまうことです。

こちらの問題についても、扱うとしたら別の記事で、になると思います。

まとめ

偏りのあるコインで公平なコイントスを再現する方法に、フォンノイマンの方法がある。その方法では、p=0.5のときに平均4回、p=0.2のときに平均6.25回のコイントスが必要になる。
フォンノイマンの方法を拡張して、必要なコイントスを減らすことができる。
拡張した方法での、およその平均コイントス回数を計算できる式を求めた。
拡張した方法では、p=0.5のときに平均約3.40回、p=0.2のときに平均約5.70回のコイントスが必要になる。
拡張した方法によって削減できる平均コイントス回数は多くて0.6回である。
拡張した方法は、おそらく最も効率の良い（コイントス回数が少なくて済む）方法である。（未証明）
発展問題として、コインを6面サイコロにした問題が考えられる。

感想

つい記事が長くなってしまうんですよね。これでいいのか悪いのか。

内容については、直感に従っていたと思います。たとえば、「HHTT」「TTHH」の判定を入れるとして、このような結果列が出るには、それなりに表と裏が均等に出る必要があるわけです。ですけど、表と裏がそれなりに均等に出るなら、「HT」「TH」の判定で十分事足りるわけですね。

こうやって工夫してもコイントスの回数は1回減るか減らないかなので、それなら、前のコイントスの結果を気にせずに使える、フォンノイマンの方法の方が使い勝手が良くて便利だと言えるわけです。だから、フォンノイマンも、分かりやすさを重視して、これ以上の効率化を明記しなかったのかもしれません。

参考文献

https://mcnp.lanl.gov/pdf_files/InBook_Computing_1961_Neumann_JohnVonNeumannCollectedWorks_VariousTechniquesUsedinConnectionwithRandomDigits.pdf
フォンノイマンの方法の原論文です。
John von Neumann「Various Techniques Used in Connection With
Random Digits」1951．
歪んだコインの活用法－フィフティ・フィフティの確率をどう作る? |ニッセイ基礎研究所
同じ問題を考察している記事の一つです。