fixedpoint.jp

不公平なサイコロを公平なサイコロの代わりにするには (2019-12-15)

出目の確率が公平でないかもしれない6面体サイコロが与えられたときに、公平なサイコロを振ったときのように等確率で1から6までの整数を出す乱数を生成する方法があります。

ただし、与えられたサイコロを何度振ってもよく、毎回出る目の確率は変わらないものとします。

ここで紹介する方法は、John von Neumannが[1]で紹介している「表裏が不公平に出るコインを投げることで公平なコイン投げと同等のことができる」という方法の応用です。

方法A

  1. 与えられたサイコロを6回振る。
  2. 6回分の出目が全て異なっていた(つまり、順番は問わないが1から6までの目が各1回出た)場合、最後に出た目を採用する。
  3. そうでない場合は、1に戻ってやり直し。

ただこの方法だと、出にくい目のために何度も繰り返しサイコロを振る羽目になるという欠点があります。それどころか、与えられたサイコロで実は特定の目が出ないという場合にはうまくいきません。

そこで、次のような改良した方法も考えられます。こちらなら、出ない目が3つまであっても問題ないだけでなく、むしろ出ない目がちょうど3つあるときは乱数生成に必要となるサイコロを振る回数の期待値が減ります。

方法B

まず与えられたサイコロを試しに何度か振り、比較的出やすそうな出目を3つ事前に選んでおく(以下では、選んだ3つの出目をそれぞれ\(n_1\)、\(n_2\)、\(n_3\)とよぶ)。

  1. 与えられたサイコロを3回振る。
  2. 出目が順に\(n_1\)、\(n_2\)、\(n_3\)だった場合、「1」を採用する。
  3. 出目が順に\(n_1\)、\(n_3\)、\(n_2\)だった場合、「2」を採用する。
  4. 出目が順に\(n_2\)、\(n_1\)、\(n_3\)だった場合、「3」を採用する。
  5. 出目が順に\(n_2\)、\(n_3\)、\(n_1\)だった場合、「4」を採用する。
  6. 出目が順に\(n_3\)、\(n_1\)、\(n_2\)だった場合、「5」を採用する。
  7. 出目が順に\(n_3\)、\(n_2\)、\(n_1\)だった場合、「6」を採用する。
  8. どれでもない場合は、1に戻ってやり直し。

参考

[1] John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.

© 2006-2023 fixedpoint.jp