ボタンを押すと数が出て、それはランダムだとみなされます。問う価値があるのは、何がそれを生んだかです。2つの答えのうち一方は検証可能で、もう一方はそうではありません。
本物のランダム性はどこから来るのか
真のランダム性は、以前の状態によって決まらない物理過程から生まれます。
- 放射性崩壊 — 原子が崩壊する正確な瞬間は予測できません
- 熱雑音 — 抵抗器の中のランダムな電圧変動
- 大気雑音 — 雷活動による背景の静電気
- 量子測定 — 本質的に不確定な結果
これらはランダム性の近似ではありません。過去についてどれだけ知っていても結果が決まらないという意味で、ランダムなのです。
コンピュータは代わりに何をするのか
コンピュータはこれらをどれも直接観測できないため、ハードウェア生成器がそれらをサンプリングします。生のバイトは /dev/urandom や同等のオペレーティングシステムの源から来ており、それ自体が物理過程を種にしています。これが真の乱数生成器です。
はるかに一般的なのは擬似乱数生成器です。乱数に見えるだけの数列を生み出す決定論的アルゴリズムです。
next = (previous × multiplier + increment) mod modulus重要な性質は微妙なものではありません。アルゴリズムとシードを知っていれば、その数列がこれから生むすべての値を計算できます。おおよそではなく、正確にです。
だからこそ、ほとんどすべてのウェブサイトが使う Math.random() は、重要な用途には適しません。その出力は内部状態で決まります。観測した出力からその状態を復元すれば、将来のすべての出目が予測可能になります。
最もよく挙げられる例は、線形合同法生成器の完全な状態が、連続する少数の出力から復元できるというものです。Pythonの既定であるMersenne Twisterは、再構成に624個の出力を要します。そして624は数秒で到達する数です。
Xorshiftや同様の高速な生成器も、形は違えど同じ性質を持ちます。統計的な品質は優れていますが、状態が分かれば完全に予測可能です。
実際に重要な中間の選択肢
これはほとんどの説明が飛ばす部分であり、実際に答えを決める部分です。
現代のウェブプラットフォームは、呼び出しごとに生の /dev/urandom を使うわけではありません。使うのは暗号学的に安全なPRNGです。決定論的アルゴリズムですが、ハードウェアエントロピーを種にしており、出力を観測しても状態を復元できないように設計されています。
この区別は正確に述べておく価値があります。両者は混同されるからです。
| ハードウェアTRNG | CSPRNG | 通常のPRNG | |
|---|---|---|---|
| 物理エントロピーに基づく | はい | はい | いいえ |
| 状態が分かれば決定論的 | いいえ | はい | はい |
| 出力が状態を明かす | いいえ | いいえ | はい |
| 賞品抽選に適する | はい | はい | いいえ |
CSPRNGは、あなたが使うあらゆるソフトウェアが決定論的であるのと同じ意味で決定論的です。それを許容できるのは、すでに出力したものから状態を復元できない点にあります。
ブラウザはまさにこれを crypto.getRandomValues() を通じて提供します。これがRandomSelectの抽選が使う源です。
公平さは2つめの問い
良い源があっても一様性は間違えやすいものです。d6は単純です。6つの等しく起こりうる値です。d7はそうではありませんし、「40個の名前から1つ選ぶ」も同じです。
素朴な方法——0から1の乱数小数を範囲に引き伸ばす——は下端に偏りを生みます。名前が40個あると、最初の名前が最後よりわずかに多く出ます。一部の乱数値が最後のバケットの終端を越えて落ち、それが不均等に捨てられるからです。
正しい方法は棄却サンプリングです。乱数を引き、結果が不完全な最後のバケットに入ったら捨てて引き直します。分布は完全に一様になります。
偏りが小さいため、これは見落とされがちです。実際には、実装は範囲外の値を棄却して引き直すので、すべての項目の確率がちょうど1/Nになります。名前40個の抽選で、小数を引き伸ばす実装が最初の名前にわずかに高い確率を与える場合でもです。
同じ手法は短縮ID生成器にも現れ、コードのコメントに採用率と、約1000万分の2という生じる偏りが記されています。無視できるほど小さく、不注意な実装なら見過ごされたほど小さな値です。それを測ることこそが要点です。
実務での意味
昼食を選ぶだけなら、これらはどれも関係ありません。どの生成器でも受け入れられる昼食になります。
賞品抽選、従業員の割り当て、評判が関わるものについては、問いは「出力を先読みできたか」です。Math.random() なら、原理的にはできました。crypto.getRandomValues() なら、できません。これは「ランダムだと言っている」と「仕組みがそうさせている」の違いです。
関連してよく混同されるのが、アニメーションについての点です。回転するルーホイールでは、結果は回り始める前に決まっており、アニメーションはそこへ向かって進みます。これを操作の証拠と受け取る読者もいます。逆です。結果がすでに確定していてタイミングで左右されないからこそ、誰も悪用できる入力がありません。映像は、すでに確定した値の上にかぶせた演出です。
自分で試す
コードを必要としない手軽な練習です。サイコロを20回振って結果を書き留めます。そして連続を探してください。
見つかります。同じ目が3回続くのは、およそ50回に1回起こります。これはサイコロが細工されている証拠ではなく、公平な過程を短い標本で見たときの姿です。
次に100回振って、各面を数えます。ばらつきは縮まります。誰も収束などしていません。埋めるべき不足など最初からなかったからです。これが独立性というものの、十分よく見たときの姿です。
さらに読む
このサイトの公平性ページでは、棄却サンプリングの段階を含め、実際の実装を順に説明しています。一度読む価値があります。とくに、疑問視される判断のためにツールを選ぶ場合は。
実用的なまとめは短いです。crypto.getRandomValues() を使い、範囲外の抽選を棄却するツールは正しいことをしています。そして、それを鵜呑みにする必要はありません。仕組みのほうを推論すればよいのです。