ランダムは実際には十分にランダムではない場合

コードベースのどこにでも現れる一般的なパターンが、多くの人が書いたことがあるものです。オブジェクトのセットが与えられたとき、ランダムに1つを選択します。すべてのオブジェクトは、選択される同じ確率を持つべきです。かなりシンプルで直接的な解決策は、大きな乱数を生成し、その数を剰余演算子で選択肢の数にクランプすることです。 Set<T> choices = ten_things(); u64 r = random_u64(); // [0..UINT64_MAX] の均一な確率 T chosen = choices[r % 10]; 私が若い頃、特にC言語を書いているときに、このオプションを何度も選択したことを覚えています。C言語の標準ライブラリはrand()以上のものは提供していません。また、私の他の言語であるHaskellでも同様でした。結局のところ、このような問題に直面したとき、それはかなり直接的で直感的な解決策であり、どんなに質素で弱いコードベースや言語であっても、乱数を取得する何らかのメカニズムは持っているはずです。 しかし、この解決策には隠された問題があります。それは、与えられたrandom_u64()関数の基盤となる均一分布を維持しないことです。つまり、選択されるオブジェクトの変動性は、私たちが直感的に考えることを尊重しません。各アイテムが1/10の確率で選択されると考えるかもしれませんが、そうではありません。 （非）均一選択の維持 まず、より簡単な問題から始めましょう。区間[0, 9]から整数を1つ選択します。可能な選択肢は10個あります。乱数生成関数が均一分布を持っていると仮定すると、各整数は1/10 = 10%の確率で選択されることになります。次に、上記の剰余演算子を使用して、この整数を使用して3つのオブジェクトのセットからランダムに値を選択しましょう。直感的（暗黙的）な希望は、この操作が3つのオブジェクトのいずれかを、それぞれ1/3 = 33.3%の確率で選択することです。言い換えれば、結果の確率分布が入力変数の均一分布を「尊重」することを望んでいます。 残念ながら、そうではありません。結果を単純に表にまとめると明らかになります。 入力値 -> 選択 ----------------------------- {0, 3, 6, 9} -> オブジェクト #1 を選択 {1, 4, 7} -> オブジェクト #2 を選択 {2, 5, 8} -> オブジェクト #3 を選択 言い換えれば、与えられた10個の入力のうち、4つが選択肢1を生成するのに対し、選択肢2と3はそれぞれ3つの入力しか生成しません。これは、選択肢1が意図した33%ではなく40%の時間で選択され、同様に2と3は30%の時間しか選択されないことを意味します。これは古典的な間違いの1つであり、特にrandom_u64()しか利用できない場合には顕著です。 さて、正しい動作は、random_between(l, h)関数です。これは、lからhまでの各包括的な数に1/((h-l)+1)の確率で選択される機会を与えます。そのような関数は、私たちが今期待するように、少し複雑です！ 私の考えでは、問題は2つあります。1つは、均一な乱数関数しか提供しないのはAPI設計として最適ではないということです。特に、最も有用なバリアントの1つが誤って実装されやすいことを考えると。しかし、それはまた、そもそも間違ったドメインで精神的に作業している良い例でもあります。 明示的な分布を与えることは（うまくいけば）簡単です 私が思うに、最初のことは、random_u64()のようなAPIが少し低レベルで特殊すぎるということです。私たちは実際に均一な数をサンプリングしたいのではなく、「何かがどれくらいの頻度で発生するか」を表現するためのより一般的な演算子を求めています。一方では、ランダムな数をピックアップする必要があることはめったになく、通常は可能な選択肢のセットから何かを選択したいのです。第二に、特定のオブジェクトを他のオブジェクトよりも可能性が高い、または低いと重み付けすることがしばしば有用です。均一分布は唯一価値のあるものではありません！random_u64()はこれらのどちらにも役立ちません。random_between(0, 9)は、一見すると最初のものにしか役立ちません（後述）。ほとんどの場合、より一般的な演算子に頼る方が有用だと考えます。それは、これらの問題を直接的に直面させるからです。つまり、選択確率とそれらの確率を受け取るrandom_choice()関数です。言い換えれば、確率分布自体を明示的に記述する必要があります。これにより、前の2つの動作と、より興味深い多くの動作を表現できます。 通常、確率について話すとき、それらが1.0に合計されると考えます。例えば、元の例の再定式化のように。このような設計では、誤った「偏った」選択は、親指の痛みのように際立つでしょう。 T chosen = random_choice([ (First, 0.4), // 40% の確率?!?!? (Second, 0.3), // 30% の確率 (Third, 0.3), // 30% の確率 ]) これは（多くの例のうちの）1つだと思いますが、汎用的なAPI、より抽象的なAPIは、実際にはコードの多くをより理解しやすく、正しく書くことを容易にします。もちろん、random_u64()とrandom_between()も引き続き利用できるはずですが、random_choice()がはるかに優れたデフォルトツールだと思います。なぜなら、それは成功のピットに陥るのを助けてくれるからです。 APIの改善：相対整数重み 前のインターフェースは教育的には良いですが、浮動小数点数の不安定性は、正確に1.0に合計する必要がある正確な重みを選択する能力を曖昧にする可能性があります。また、合計が1.0になるという要件は煩わしいです。なぜなら、各確率選択の適切なスケールを計算する必要があるかもしれないからです。そして、浮動小数点数を含む問題に直面すると、私たちはそれを処理するための試行錯誤された方法を使用します。つまり、それを排除して別のことをします。Pythonのようなほとんどの標準ライブラリがまさにこれを行っていることがわかります。相対整数重みです。「相対」という言葉は、数値が100に合計されないことを意味します。代わりに、それらを単純に合計し、任意の選択の重みはその選択の確率と合計の比率になります。前の重みは（4, 3, 3）と表されます。4 + 3 + 3 = 10であり、したがって3 / 10 = 0.3となります。 相対整数重みの良い点の1つは、それらがより直感的に動作するため、正しく使用する可能性が高くなることです。箱の中のアイテムの数を数えて、10個の青いアイテムと5個の赤いアイテムが見つかった場合、choicesを[(Blue, 10), (Red, 5)]と単純に記述でき、結果の選択は期待どおりに分布されます。 別の小さな注意点として、このAPIの実装は、random_u64()だけでなくrandom_between(l, h)があれば、直感的に行う方がはるかに簡単です。これは、random_u64()があまりにも低レベルすぎるというもう1つの兆候だと思います。整数重みが15 + 12 + 3 = 30であるとしましょう。次に、ランダムな数choice = random_between(0, 29)を単純に描画します。選択された値が[0, 14]の間にある場合、それは最初のオプションです。15から26の間にある場合は2番目のオプション、[27, 29]の場合は3番目のオプションです。言い換えれば、整数重みを区間[l, h]の部分集合に単純にマッピングし、その区間から一様に選択できます。これは非常に有用でシンプルであり、私の意見では、他の関数にも含めるべきです。 間違ったメンタルドメインでの作業 私にとってより微妙なもう1つの問題は、自分がどのドメインで操作しているかを認識することです。前の例では、私たちが話したいことは数値ではなく、確率変数です。私たちは通常、これらの確率変数を大文字のX、Y、Zなどで呼びます。通常の数値と同様に、確率変数にも代数があり、それらを加算したり減算したりでき、指数も備えています。しかし、これらの演算子も基盤となる分布とそれらの期待される結果に影響を与えます。しかし、最も重要なことは、非線形演算子は確率変数の期待値を尊重しないということです。特に、期待値E[f(X)]に対する関数fは、常にf(E[X])と同じではありません。ここで起こったことです。注意しないと、値x = random_u64()の何らかのプロパティを維持しようとしていると考えてしまいがちですが、実際には基盤となるrandom_u64()関数のプロパティを維持しようとしています。 私たちのケース 私たちはAntithesisの顧客です。彼らのプラットフォームでは、重要なコードパスをランダムに実行することでバグを見つけます。これは、オペレーティングシステム全体に対する大規模な決定論的ファザーです。そして、ファザーと同様に、コードカバレッジを導きとして考えることは有用です。「このコードはテストされたか」は、「ファザーはこのパスを見つけたか」と尋ねることと同等であり、ファザーが見つけた場合