選択の公平さは乱数の源で決まる

「ランダムです」というのは事実ではなく主張です。選択が公平であるためには、2つの条件が満たされる必要があります。数の源が予測できてはならず、すべての選択肢が等しい確率でなければなりません。

どちらも実装可能で、どちらもよく間違えられ、そしてそれぞれ独立に失敗します。優れた乱数源を持ちながら偏った割り当てをするツールもあれば、完全に一様な割り当てに予測可能な数を供給するツールもあります。

ランダム性はどこから来るのか

本物のランダム性は、以前の状態によって決まらない物理過程から生まれます。

• 放射性崩壊 — 原子が崩壊する瞬間は予測できません
• 熱雑音 — 抵抗器の中のランダムな電圧変動
• 大気雑音 — 雷活動による背景の静電気
• 量子測定 — 本質的に不確定な結果

コンピュータはこれらを直接観測できません。代わりに、ハードウェア生成器——/dev/urandom やその同等物——からサンプルを取ります。この生成器自体も物理過程を種にしています。これが真の乱数生成器です。

はるかに一般的なのは擬似乱数生成器です。乱数に見えるだけの数列を生み出す決定論的アルゴリズムです。

next = (previous × multiplier + increment) mod modulus

重要な性質は微妙なものではありません。アルゴリズムとシードを知っていれば、その数列がこれから生むすべての値を計算できます。おおよそではなく、正確にです。だからこそ、多くのウェブサイトが使う Math.random() は、重要な用途には適しません。その出力は内部状態で決まり、観測した出力からその状態を復元すれば、将来のすべての結果が予測可能になります。

答えを決める中間の選択肢

現代のプラットフォームは、呼び出しごとに生のハードウェアエントロピーを使うわけではありません。使うのは暗号学的に安全なPRNGです。決定論的ですが、ハードウェアエントロピーを種にしており、出力を観測しても状態が明らかにならないように設計されています。

CSPRNGは、あなたが使うあらゆるソフトウェアが決定論的であるのと同じ意味で決定論的です。それを許容できるのは、すでに出力したものから状態を復元できない点にあります。

ブラウザはこれを crypto.getRandomValues() を通じて提供します。ここでの抽選が使う源もこれです。

一様性は別の問題

良い源があれば十分とは限りません。乱数から選択肢への割り当ては依然として偏り得ます。多くのツールがこの間違いを犯します。

素朴な方法——0から1の乱数小数を範囲に引き伸ばす——は下端に偏りを生みます。名前が40個あると、一部の乱数値は最後のバケットの終端を越えて落ちます。それを捨てずに丸めると、最初の名前が最後の名前よりわずかに多く出ます。

偏りは誰も気づかないほど小さいため、ほとんどの実装に残り続けます。

正しい方法は棄却サンプリングです。乱数を引き、結果が不完全な最後のバケットに入ったら捨てて引き直します。分布は完全に一様になり、すべての項目の確率が1/Nになります。名前40個の抽選で、小数を引き伸ばす実装が最初の名前にわずかに高い確率を与える場合でもです。

同じ手法はここの短縮ID生成器にも使われており、採用率は252/256、生じる偏りは約1000万分の2です。無視できるほど小さく、不注意な実装なら見過ごされたほど小さな値です。だからこそ測る価値があります。

ツールのせいではない3つの人の失敗

ギャンブラーの誤謬。 表が5回続くと、次は裏が来る気がします。各試行は独立です。コインは不公平だったことを覚えていませんし、表が5回続いた後の正しい確率は依然として各面1/6です。

クラスタリングの錯覚。 ランダムなデータの中の連続は、探しているから模様に見えます。同じ結果が3回続くのは、直感が思うよりずっと頻繁に起こります。そして本当にランダムなデータは短い区間ではむらに見えます。完全に均等に見える数列のほうが、本物より捏造である可能性が高いのです。

誕生日のパラドックス。 23人の集団では、2人が同じ誕生日である可能性が高いです。これは心理学ではなく算数ですが、人がなぜランダム性の見積もりをこんなに苦手とするかを示しています。個々の確率はごく小さく、それが掛け合わさるからです。

共通するのは、1回の観測ではどちらの方向にも何も証明できないということです。奇妙に見えた抽選も、整って見えた抽選と同じくらい情報になりません。

実務で最も問題になる2つの失敗

仕組みをたどったところで、選択が争われたときに実際に何が起きるかに名前を付けておく価値があります。どちらも源の問題ではありません。

運営者が結果を上書きした。 引き直し、手作業での修正、抽選中の不在者の飛ばし。完璧な生成器でも、結果が改変されていればそれは改変された結果であり、見ていた人には分かります。

母集団が公表されたものと違った。 名前を加えたり、黙って1人除外したりすれば、アルゴリズムに関係なく選択は変わります。

どちらも手順上の失敗であり、どちらも記録された抽選が防ぎます。だからこそ、参加者リストを画面に入れて記録することは、どんな技術的性質よりも価値があります。両方を封じるからです。

この水準の厳密さが求められる場面

昼食を選ぶだけなら、これらはどれも関係ありません。どの生成器でも受け入れられる昼食になります。

賭けや評判、法的な側面が関わると、これが重要になります。

• 賞品抽選やコンテスト。 検証可能な結果こそが目的です
• 従業員や業務の割り当て。 人は手順を調べます
• 科学・臨床の無作為化。 この分野の標準は、記録され、シードされ、再現可能なランダム性です
• 規制や監査の場面。 記録されたランダム性はしばしば希望ではなく要件です

これらの要件はいずれも同じ4つで、短いものです。母集団は固定され公表されていること、重みがあるなら公表されていること、源が予測できないこと、結果が母集団の見える状態で記録されていることです。

自分で確認する方法

ブラウザのタブでCSPRNGを監査することはできませんが、仕組みについて推論することはできます。それで十分です。

源は何か尋ねる。 答えが「乱数関数」なら、それが予測可能なほうか尋ねてください。crypto.getRandomValues() は具体的で確認できる答えです。

一様性をどう実現しているか尋ねる。 棄却サンプリングに触れずに小数を範囲に引き伸ばす答えなら、その割り当てはおそらく偏っています。わずかに、しかし測定できる程度に。

運営者が何を変えられたか尋ねる。 何も変えられないなら、その結果は擁護できます。名前を飛ばしたり抽選をやり直したりできるなら、源に関係なく擁護できません。

公平性ページでは、このサイトでの実装をより詳しく扱っています。疑問視される判断のためにツールを選ぶなら、一度読む価値があります。