A.S.: そう、「ダイス」の単数は「ダイ」らしいですね。 940>
1 から 5 までの一様な乱数を返す関数があるとして、1 から 7 までの一様な乱数を返す関数を設計しなさい。
アルゴリズムと統計学の交差があなたの好みなら、遠慮なく挑戦してください！
アルゴリズムと統計学の交差があなたの好みなら、遠慮なく挑戦してください。 さらに挑戦したいのは、アルゴリズムを時間的に束縛されたものにすることです。 私はこれが楽しいエクササイズであることに気づきましたが、ここには基本的な限界があることに気づきました。 現実世界のダイスは、自然法則と環境の不完全性に支配されており、この抽象的なモデルの近似に過ぎません (良いものではありますが)。 少なくとも7つの結果を持つランダムジェネレータを作るために、5面ダイスを少なくとも2回振る必要がある。 2回転がすと5^2=25の結果が得られ、これは7の倍数ではないが、最初の21の結果を3等分の7つのグループに割り当てることができる。 しかし、残りの4つの結果になった場合、手順をやり直さなければなりません。
上の図で、円はプログラムの「状態」を表し、中のテキストは転がったダイスの最も新しい値です。 そして、緑のボックスは、最終状態 (= サイコロを 2 回振った後) に応じて割り当てる出力を表します。 84%の確率で、2回サイコロを振った後に出力が得られ、アルゴリズムが終了します。 見ての通り、ループが存在し、アルゴリズムが無限になります。 つまり、どんなに大きな整数でも、1つの出力値を計算するために、小さいがゼロではない確率で、出目の総数がその量を超えてしまうのである。 したがって、アルゴリズムの統計的精度に妥協しない限り、厳しい時間要件を持つリアルタイムアプリケーションは問題外である。
この解決策の変形は、再起動する前に最初にサイコロを3つまで振る。 これで、最大3個のサイコロを振ってから終了する確率は95.2%である。 なぜなら、ほとんどの場合、最初の2回のロールの後、すでにショートカットを取ることができ、これらの中間状態を直接出力にマッピングすることができるからである。 940>
情報理論に詳しい方は、5面ダイス（= rand5）の1回の出目でlog2(5) ≒ 2.32 bitsの情報が、7面ダイス（= rand7）の1回の出目でlog2(7) ≒ 2.81 bitsの情報が得られることを考えてみてください。 その結果、極限状態では、rand7の値1つに対して、log(7)/log(5) ≒ 1.21回のrand5の呼び出しが必要であることが判明した。 この限界に近い正確な実装はかなり複雑であり、この記事の範囲外である。 rand7を複数回呼び出す間に状態情報を保存する必要があり、私が考えているアルゴリズムは、時間だけでなくメモリもまだ無制限である。 この後者の問題を解決する方法を喜んでお知らせください！
A bounded solution
1から5までのランダムジェネレータのみが与えられたときに、1から7の間の完全に均一なランダム値を計算する、境界のあるアルゴリズムというものは存在しない。 上の非有界解のファミリーを考えてみましょう。 私がほのめかしたように、どの時点でも必ず「取り残された」状態（1〜6の範囲）があり、アルゴリズムが再起動することになります。 これは、5 と 7 が素数であり、5 の累乗が 7 の倍数になることはないからです。どんなにフェルマーの小定理を使いたくとも、基本的な数論がこの系列の有界解を不可能にしているので、その試みは 1 回ごとのエラーに終わります。 もしかしたら、状態図をアレンジして、可変長の経路と7n個の終了状態を持つ有界のアルゴリズムを作ることができるかもしれませんね。
- すべてのパスの長さ（= rand5 の呼び出し回数）が同じではないので、これらの終了状態が等しくなるとは限りません。 もちろん、これは正式な証明ではありませんが、この問題についての直感をつかんでいただければと思います。 このように、ある問題が非常に現実的に見えても、このような数学的な事実につまずくことがあるのです。 このように分析した結果、4面ダイスから8面ダイスをシミュレートすることが可能かどうか、わかりますか？