5億回のコイントスの結果を100回のコイントスで得るための方法

ある日、ツイッターで「大量のトークンを生成した後にそのトークンの数だけコイントスを行う処理をした場合どうなるのか？」という内容のツイートを見ました。
例えば、「名演撃、ラクドス」などが挙げられます

これを解決するためにはどうすればいいのでしょうか？一つ面白い方法を見つけたので解説します。

まず、「コイントスを行い何回表がでるか」という問題ですが、この答は二項分布と呼ばれる分布に沿います。

例えば、コインを3回投げてn回表がでる確率は
n=0 : 1/8
n=1 : 3/8
n=2 : 3/8
n=3 : 1/8
となっています。これはCombination(3,n)に対応しています。
で、nを非常に大きな値にした場合、これは正規分布に沿うことがわかっています。
今回は、このことを用いて5億回のコイントスの結果を得ることとしましょう

まず、最初に以下の手段について合意をしていただく必要があります。

・自分は破壊不能持ちの「血の芸術家」をコントロールしている
・対戦相手のライフが51である
・「血の芸術家」以外に100体のトークンをコントロールしている
・この状態で「名演撃、ラクドス」を戦場に出した
この状況下では「100回のコイントスを行い、51回以上裏が出たら自分の勝ち」という状況です。
また、100回コイントスを行い、51回以上裏が出る確率は50%です。
ですので「コイントスを一度だけ行い、裏がでたなら、少なくとも51回は裏が出たこととし、自分の勝ちとする。表が出た場合は、適正な方法で0~50までの数値を選ぶ」

というものです。
この方法は(どの値が出たかは厳密には決まらないものの)コイントスを行う回数を1/2の確率でたった1回に抑えることが出来ます。

これを少し応用してみましょう。
と、その前に今回の問題を解決するうえで重要な資料を貼っておきます
https://www.koka.ac.jp/morigiwa/sjs/standard_normal_distribution.html
標準正規分布表ですね

カンの良い人はこの時点でおおむね気づいていると思いますが、今回は「乱数生成を繰り返して「何回発生したか」の範囲を絞り込んでいく」という手段になります。
具体的にみて行きましょう。
例えば、5億回のコイントスを行ったとき、そのうち表が出た回数は25％区切りにすると以下のようになります。
(この値は、標準正規分布表を使用することで求めることが出来ますが、ここでは求め方は割愛します。)
0~249,992,400回の範囲の結果になる確率が25%
249,992,401~250,000,000回の範囲の結果になる確率が25%
250,000,001~250,007,600回の範囲の結果になる確率が25%
250,007,601~500,000,000回の範囲の結果になる確率が25%
となります(計算間違ってたらごめんなさい)
25％刻みの中から一つを選ぶ。つまり、4つの範囲から一つを選ぶのはコントス2回でできますから、比較的容易なことです。
例えば、コイントスを2回行った結果が(表・裏)で、その際の範囲を249,992,401~250,000,000回と決めていたのであれば、
「たった2回のコイントスで5億回のコイントスの結果を7600通りまで絞り込んだ」ということになります。
この作業を繰り返して範囲内の数値を1000通り以下に抑え込めば、あとは10回程度のコイントスで結果を確定させることが出来るわけです
(厳密には、ここで絞り込んだ1000通りの結果は出現率が全て等価というわけではありませんが、5億回の結果と言うことを考えればその出現率の差は極めて小さいわけですから無視していいと言えそうです。)
つまり、範囲を絞り込むのに高々10～30回ぐらい、その後範囲内の数値から選ぶのに10回ぐらいコイントスをすればよいということとなり、5億回のコイントスの結果を50回ぐらいのコイントスで(それなりの精度で)取得することが出来るというわけです。

おわり