ランダム性が実際には十分にランダムでないとき

2026-10-06 技術

作者 Austin Seipp

どのコードベースにも見られる、そして多くの人が一度は書いたことがあるだろう定番の書き方がある。オブジェクトの集合から一つをランダムに選ぶ、というものだ。どのオブジェクトも等しい確率で選ばれるべきである。ごく単純なやり方は、大きな乱数を一つ取ってきて、選択肢の数で割った余りを求め、範囲内に収めるというものだ：

Set<T> choices = ten_things();
u64 r = random_u64(); // uniform chance over [0..UINT64_MAX]
T chosen = choices[r % 10];

若い頃に何度もこの手を選んだことをはっきり覚えている。特に C を書いていたときはそうだった——標準ライブラリには rand() しかない——当時よく使っていた Haskell でも同じだった。何しろ、この問題に対してこの解法はほとんど最も直接的で直感的であり、どんなに貧弱なコードベースや言語でも、乱数を得る仕組みは何かしらあるものだ。

だがこの解法には問題が潜んでいる。与えられた random_u64() 関数が持つ一様分布を保たないのだ。つまり、選ばれた chosen 個のオブジェクトの分布は直感に反する。各要素が 1/10 の確率で選ばれると思い込んでいても、そうはならない。

一様選択の（非）保持

まずはもっと単純な問題から始めよう。区間 [0, 9] から整数を一つ取る。取りうる値は 10 通りある。乱数選択関数が一様分布に従うと仮定すれば、各整数が選ばれる確率は 1/10 = 10% だ。

次に、この整数を使って、上と同じように剰余演算で 3 個のオブジェクトから一つをランダムに選ぶ。直感的には（そして暗黙のうちに）、この操作が 3 個のうちの一つを 1/3 = 33.3% の確率で選ぶことを期待している。言い換えれば、結果の確率分布が入力変数の一様分布を「尊重」してほしいのだ。

残念ながらそうはならない。結果を表にすれば一目瞭然だ：

Input value  -> Choice
-----------------------------
{0, 3, 6, 9} -> choose object #1
{1, 4, 7}    -> choose object #2
{2, 5, 8}    -> choose object #3

つまり、与えられた 10 個の入力のうち 4 個が選択肢 1 に至り、選択肢 2 と 3 にはそれぞれ 3 個の入力しか至らない。選択肢 1 が選ばれるのは 40% であり、期待した 33% ではない。同様に 2 と 3 が選ばれるのは 30% にとどまる。

これは古典的な失敗の一つで、特に手元に random_u64() しかないときに起きやすい。正しいやり方は random_between(l, h) 関数を使い、l から h までの各閉区間の数値が 1/((h-l)+1) の確率で選ばれるようにすることだ。今なら予想できるように、そんな関数はもっと複雑になる！

問題は二つあると思う。一つは、一様乱数関数だけを提供するのは API 設計として浅慮だということ。特に、最も有用な変種の一つを間違えやすい。もう一つは、最初から間違った思考の枠組みで問題を捉えている好例だということだ。

分布を明示するほうが（おそらく）簡単

まず気づくべきは、random_u64() のような API はあまりに低レベルで、あまりに特殊すぎるということだ。本当に欲しいのは一様分布の数値をサンプリングすることではなく、「あることがどのくらいの頻度で起きるか」を表現する、より汎用的な演算子である。

一方で、乱数を一つ選ぶだけでは済まないことがほとんどで、たいていは複数の候補からオブジェクトを選びたい。もう一方で、あるオブジェクトを他より選ばれやすくしたり選ばれにくくしたりできると便利なことが多い——一様分布だけが価値ある分布ではない！random_u64() はどちらにも役立たない。random_between(0, 9) は一見すると最初の問題しか解けない（詳しくは後述）。

ほとんどの場合、より汎用的な演算子に切り替えて、これらの問題に正面から向き合わせるほうが有用だと思う。つまり、離散的な選択肢の集合とその選択確率を受け取る random_choice() 関数だ。言い換えれば、確率分布を自分で明示的に書くべきなのである。そうすれば前述の二つの振る舞いをどちらも表現でき、さらに面白い振る舞いも表現できる。

通常、確率といえば合計が 1.0 になると考える。たとえば元の例を書き直すとこうなる。この設計では、あの誤った「偏った」選択がひときわ目立つ：

T chosen = random_choice([
  (First,  0.4), // 40% chance?!?!?!
  (Second, 0.3), // 30% chance
  (Third,  0.3), // 30% chance
])

これは、汎用化されたより抽象的な 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 となり、予想どおりだ。

相対整数重みの利点は、振る舞いがより直感的で、正しく使える可能性が高いことだ。箱の中のものを数えて、青が 10 個、赤が 5 個あれば、[(Blue, 10), (Red, 5)] にそのまま選択を書けばよく、最終的な選択分布は思いどおりになる。

もう一点補足すると、random_between(l, h) だけでなく random_u64() があれば、この API の実装は直感的にずっと簡単になる。これは random_u64() の抽象レベルが低すぎることの表れだと思う。整数重み 15 + 12 + 3 = 30 があるとしよう。ならば乱数 choice = random_between(0, 29) を一つ引くだけでよい。引いた値が [0, 14] の間なら最初の選択肢、15, 26 の間なら二番目、[27, 29] なら三番目だ。言い換えれば、整数重みを区間 [l, h] の各部分集合に写像し、その区間上で一様に値を取るだけでよい。これは使いやすく単純で、他の関数と一緒に提供されるべきだと私は思う。

間違った確率領域で作業する

私にとって、もうひとつ微妙な問題は、自分がどの領域で操作しているのかを正しく見極めることだ。前の例で扱いたかったものは数字ではなく、確率変数だった。確率変数はふつう大文字で書き、X、Y、Z などと表す。

普通の数字と同じように、確率変数にも代数がある。足し算も引き算もでき、指数も持つ。だがこれらの演算は、ここで起きたのと同じように、背後にある分布とその期待値にも影響する。何より重要なのは、非線形演算は確率変数の期待値に従わないことだ。具体的には、期待値 E[f(X)] に関数 f を適用した結果は、f(E[X]) と常に等しいわけではない。

ここで起きていたのはまさにこれだ。うっかりすると、自分が保ちたいのは値 x = random_u64() の性質だと思い込んでしまうが、実際に保ちたいのは背後の random_u64() 関数の性質なのだ。

私たちのシナリオ

私たちは Antithesis の顧客だ。このプラットフォームでは、重要なコードパスをランダムに走らせてバグを見つける。OS 全体を対象にした大規模な決定論的 fuzzer だと思えばいい。fuzzer と同じで、コードカバレッジを道しるべにするのは有効だ。「このコードはテストされたか」は「fuzzer はこのパスを見つけたか」と同じ問いであり、fuzzer がそのパスを見つけられなければ、そのコードはテストされていない。

カバレッジを上げるとは、正のコードパスと負のコードパスを表現し、それをテストで見つけることにほかならない。負のパスとは、見つかればバグになる悪い状況だ。たとえば assert!() が発火する場合——キャッシュからデータを読み、そのデータ自身のハッシュをキーにしていて、assert!() というキーが再計算したデータハッシュと一致してしまう、といった具合だ。

正のパスなら、「小さい」アップロードと「大きい」アップロードで挙動が変わるアップロード関数が、確かに両方をテストしていることを確かめる、といったところだ。こういうときは分布を直接表現できると便利だ：

enum BlobSize {
  Small,  // 1KiB: fast path
  Medium, // 1MiB: streaming write path
  Large,  // 2MiB: more
  XLarge, // 8MiB: more more more
}

let choices = vec![
  (Small,  88),
  (Medium, 04),
  (Large,  04),
  (XLarge, 04),
];

if let Some(size) = weighted_choice(choices) {
   // ... upload blob of chosen size ...
};

このテストでは、アップロードの約 7/8 が小さなデータで、約 1/8 が大きなデータ（3 種類のサイズ）になる。これらの数字をいじれることは、状態空間を探索するうえで極めて価値がある。この例を少し広げて、たとえば Poisson 分布を表現するのも簡単だ。

もうひとつ実用的だと思うのは、ある条件下で choices の集合を広げる場面だ。たとえば choice.push() を使って上のベクトルに要素を足し、「良い」ことや「悪い」ことが起きたときに探索を誘導する——そのためには上の例の確率を再調整する必要があるが、例の組み立て方を変えればそれを避けられる。

これがこの記事の話につながる。先週あった出来事だ。Antithesis 関連のコードを見直した結果、（重み付き）random_choice() に紛れて入り込んでいた random_u64() の使用をすべて削除するに至った。実際に欲しかったのは常に離散的な重み付き選択だけだったからだ。新たな通達があるまで、これに対する新しい呼び出しを追加することは止めている。この教訓は commit message の片隅に埋もれさせるには惜しいと思う。私はいつも忘れてしまうから。

次に最初の例のようなコードを見かけたら、自問してほしい。欲しい分布を直接表現できないか？　できるなら、ずっと豊かな道具が見つかるはずだ。

← すべての記事

©2026 East River Source Control.
All rights reserved.

Built for humans and machines.

プライバシーポリシー 利用規約 リリースノート JJ ドキュメント ↗