当随机性实际上不够随机时

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 个对象中随机挑一个值。直觉上（也是隐含地）我们希望这个操作以 1/3 = 33.3% 的概率选中 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 的客户。在他们的平台上，我们实际上是通过随机走重要的代码路径来发现 bug——它就是一个针对整个操作系统的大型确定性 fuzzer。和 fuzzer 一样，把代码覆盖率当作指路明灯很有用：“这段代码被测到了吗”等价于问“fuzzer 找到这条路径了吗”，如果 fuzzer 没找到那条路径，那段代码就没被测到。

提高覆盖率，无非是把正向和负向代码路径表达出来，然后在测试中找到它们。负向路径是一种坏情况，一旦被找到就是 bug，比如某个 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 的上传是大块数据（三种不同大小）。能摆弄这些数字，对探索状态空间极有价值！把这个例子扩展一下，比如表达一个 Poisson 分布，也很容易。

另一个我觉得很实用的场景，是在某些条件下扩展 choices 的集合。比如用 choice.push() 往上面的向量里加东西，在发生某种「好」或「坏」的事情时用来引导搜索——这样做需要重新平衡上面例子里的概率，但你可以换个方式组织这个例子来避开这一点。

这就引出了这篇文章，以及上周发生的一件事：最近审查我们与 Antithesis 相关的代码时，我们最终把随着（加权）random_choice() 混进来的 random_u64() 用法全部删掉了，毕竟实践中我们想要的始终只是离散的加权选择；在另行通知之前，我们已暂停引入对它的新调用。我觉得这个教训足够重要，不该让它埋没在某条 commit message 里，因为我总是忘记它。

下次你看到类似最初那段示例的代码时，问问自己：我能不能直接表示想要的分布？如果可以，你大概会发现一个丰富得多的工具可以玩。

← 所有文章

为人类和机器而构建。

隐私政策条款版本说明 JJ 文档 ↗