本篇是原文 Darts, Dice, and Coins: Sampling from a Discrete Distribution 的全文中文翻译版本

在被我的导师拉着参与 cloudwego/kitex 的一个负载均衡算法的改进时 #1184 ，他指出可能可以使用 Alias Method（别名方法）来实现更为高效的负载均衡。于是我仔细地研究了本文的英文原文（链接如上）， 起初我想寻求一个中文译版，但貌似没有找到

于是鄙人借助 GPT 翻译与个人的理解进行部分词汇修正，手打大部分 LaTeX 公式与表格后完成本文，如有谬误，欢迎指出

PS：暗黑主题可能不适合本文阅读，可在右下角切换

原文最近更新日期：December 29, 2011

今年早些时候，我在 Stack Overflow 上提出了一个关于不公平的骰子的数据结构的问题。具体来说，我感兴趣的问题是：

“你有一个 $n$n 面的骰子，第 $i$i 面被掷出的概率为 $p_{i}$pi​。模拟掷骰子的最有效数据结构是什么？”

这种数据结构可以用于多种目的。首先，你可以用它来模拟一个公平的六面骰子，通过给骰子的每个面分配 $\frac{1}{6}$61​ 的概率，或者模拟一个公平的硬币，通过模拟一个两面的骰子，每面有 $\frac{1}{2}$21​ 的概率出现。你还可以使用这个数据结构直接模拟两个公平六面骰子掷出的总和，通过使用一个 11 面的骰子（面数为 2、3、4、…、12），每个面都适当地加权，以表示如果使用两个公平骰子，这个总数出现的概率。然而，你也可以使用这个数据结构来模拟不公平的骰子。例如，如果你在玩花旗骰，而你知道这些骰子不是完全公平的，你可能会使用这个数据结构来模拟掷骰子的许多次，看看最佳策略会是什么。你也可以考虑以同样的方式模拟一个不完美的轮盘赌。

在游戏领域之外，您还可以在机器人模拟中使用这个数据结构，其中传感器有已知的故障率。例如，如果一个测距传感器有 95% 的几率返回正确的值，4% 的几率返回一个太小的值，和 1% 的几率返回一个太大的值，您可以使用这个数据结构来模拟传感器的读数，通过生成一个随机结果，并在那种情况下模拟传感器的读数。

我在 Stack Overflow 上收到的答案给我留下了深刻的印象，原因有两个。首先，解决方案指出了一种强大的技术，称为别名方法，它在对机器模型进行一些合理的假设后，能够在 $O(1)$O(1) 时间内完成骰子的模拟掷出，仅需一个简单的预处理步骤。其次，也许更令人惊讶的是，这种算法已经被知道了几十年，但我之前从未遇到过它！考虑到有多少处理时间用于模拟，我本以为这种技术会更为人所知。几次快速的谷歌搜索找到了关于这种技术的大量信息，但我找不到一个单独的网站，能够汇编这种技术背后的直觉和解释。

这篇文章是我尝试快速概述模拟不公平的骰子的各种方法，从高度不切实际的简单技术到非常优化和高效的别名方法。我在这里的希望是捕捉到问题的不同直觉，以及每种方法如何突出模拟不公平的骰子的某些新方面。对于每种方法，我的目标是探索激发思想、核心算法、正确性证明以及运行时分析（就时间、内存和所需的随机性而言）。

引言

在我详细介绍不同技术的具体细节之前，让我们首先统一我们的符号和术语。

在这篇文章的引言中，我使用了“骰子”这个术语来描述一个通常情况，其中有一组有限的结果，每个结果都有一些相关的概率。正式来说，这被称为离散概率分布，模拟不公平的骰子的问题被称为从离散分布中抽样。为了描述我们的离散概率分布（不公平的骰子），我们将假设我们给定了一组 $n$n 个概率 $p_0, p_1, ..., p_{n-1}$p0​,p1​,...,pn−1​ 与结果 $0, 1, ..., n-1$0,1,...,n−1 相关联。尽管结果可以是任何东西（正面/反面、骰子上的数字、颜色等），为了简单起见，我将假设结果是与给定索引相对应的某个正自然数。

在计算机上处理实数是一种复杂的计算领域。有许多快速算法的速度完全来自于在常数时间内计算任意实数的向下取整能力，而浮点表示中的数值不准确性可以完全破坏某些算法。因此，在我们进入关于概率算法的暗黑世界之前，我们应该界定清楚计算机能做什么和不能做什么。

在接下来的内容中，我将假设所有以下操作都可以在恒定时间内完成：

1. 加法、减法、乘法、除法和任意实数的比较：我们需要能够进行这些操作来处理概率。这看起来可能是一个非常强的假设，但计算机处理实数时的精度（即能够表示的实数的精确程度）受到其基本处理单元的限制（例如，32位机器上的64位双精度数），那么这其实是很合理的。

2. 生成范围在 [0, 1) 内的均匀实数：为了模拟随机性，我们需要某种随机源。我假设我们可以在恒定时间内生成任意精度的实数。这远远超出了计算机实际能力，但出于本讨论的目的，我认为这样做是可以的。如果我们允许使用 $[0, 1]$[0,1] 内的任意 IEEE-754 双精度数，我们确实会失去一些精度，但对于大多数应用来说可能已经足够准确了。

3. 计算实数的整数下限：我们使用 IEEE-754 双精度数完成这类操作是合理的，但在更广泛的计算环境中，这样的要求对计算机是不合理的。

值得考虑的是，假设我们能够高效地执行所有这些操作是否合理。在实践中，我们很少有概率遇到 IEEE-754 双精度浮点数固有因舍入误差而引起的重大精度问题，因此， IEEE 双精度数满足以上所有约束。当然，如果我们要求概率精确地*被指定为高精度有理数，那么这些约束可能是不合理的。

模拟公平骰子

在我们概括到模拟任意加载的骰子这一特殊情况之前，让我们从一个更简单的算法开始，这个算法将作为后续算法的基础：模拟一个公平的、$n$n 面的骰子。例如，我们可能对掷出一个公平的六面骰子来玩大富翁或风险游戏感兴趣，或者抛掷一个公平的硬币（一个两面的骰子）等。

在这个特殊情况下，有一个简单、优雅且高效的算法可以模拟结果。假设我们可以生成真正随机的、均匀分布的实数，范围在 $[0,1)$[0,1) 内。我们可以将这个范围可视化如下：

要模拟投掷 $n$n 面的骰子，一种方法是将范围 $[0,1)$[0,1) 分成 $n$n 个均匀大小的小区间，每个区间的长度为 $\frac{1}{n}$n1​。如下所示：

如果我们生成一个在范围 $[0,1)$[0,1) 内随机选择的实数，它将会落入这些小区间中的一个。我们可以通过确定它落在哪个区间来得知骰子投掷的结果。例如，如果我们随机选择的值落在了这个位置：

我们会说骰子的结果是 $2$2（假设骰子的编号从 $0$0 开始）。

从图形上看，很容易看出随机值落在哪个区间，但我们如何使用算法实现呢？这体现骰子的公平性。由于所有的区间都具有相同的大小，即 $\frac{1}{n}$n1​，我们可以找出最大的 $i$i 使得 $\frac{i}{n}$ni​ 不大于随机生成的值（称为 $x$x）。如果我们试图找到最大的 $i$i 值，使得 $\dfrac{i}{n}\leq x$ni​≤x，这等价于找到最大的 $n$n 值，使得 $i\leq xn$i≤xn。但是，根据定义，这意味着 $i=⌊xn⌋$i=⌊xn⌋，即不大于 $xn$xn 的最大自然数。因此，这给我们提供了以下（非常简单的）模拟公平的 $n$n 面骰子的算法：

算法：模拟公平的骰子

1. 生成在范围 $[0,1)$[0,1) 内均匀随机的值 $x$x。
2. 返回 $⌊xn⌋$⌊xn⌋。

根据我们上面的计算假设，这个算法的运行时间是 $O(1)$O(1)。

这一部分有两个要点。首先，我们可以将范围 $[0,1)$[0,1) 分割成若干块，以便范围内的均匀随机实数自然地映射回我们可用的众多离散选择之一。我们将在本文的其余部分广泛利用这一技巧。其次，确定特定随机值落入哪个范围可能会很复杂，但如果我们了解有关分区的一些信息（在这种情况下，它们都具有相同的大小），则可以在数学上轻松确定特定点位于哪个分区。

用公平骰子模拟不公平骰子

在给定模拟公平骰子的算法的基础上，我们是否可以调整该算法以模拟一个不公平的骰子？有趣的是，答案是肯定的，但这将占用更多的空间。

根据前面的经验，为了模拟一个不公平的骰子，我们只需要将范围 $[0,1)$[0,1) 分成若干块，然后确定我们落入了哪一块。然而，一般情况下，这可能比看起来更加困难。例如，假设我们有一个四面的骰子，其各面的概率分别为$\frac{1}{2}$21​、 $\frac{1}{3}$31​、 $\frac{1}{12}$121​ 和 $\frac{1}{12}$121​（我们可以确认这是一个合法的概率分布，因为 $\frac{1}{2} + \frac{1}{3} + \frac{1}{12} + \frac{1}{12} = \frac{6}{12} + \frac{4}{12} + \frac{1}{12} + \frac{1}{12} = \frac{12}{12}$21​+31​+121​+121​=126​+124​+121​+121​=1212​）。如果我们将范围 [0,1) 分成四个具有这些给定大小的区间，我们得到以下结果：

不幸的是，我们在这里陷入了困境。即使我们知道范围 $[0,1)$[0,1) 内的一个随机数，也没有简单的数学技巧可以自动确定该数落入哪个分区。这并不是说这是极其困难的 - 正如您将看到的，有许多很棒的技巧可以使用 - 但没有一个一定具有像模拟公平骰子的算法那样的数学简单性。

然而，我们可以调整公平骰子的技巧以适应这种情况。让我们以这个特定情况为例。骰子各面出现的概率分别为 $\frac{1}{2}$21​、 $\frac{1}{3}$31​、 $\frac{1}{12}$121​ 和 $\frac{1}{12}$121​。如果我们将这些重新写成具有共同分母的形式，我们得到值 $\frac{6}{12}$126​、 $\frac{4}{14}$144​、 $\frac{1}{12}$121​ 和 $\frac{1}{12}$121​。因此，我们可以这样考虑这个问题：与其掷一个具有加权概率的四面骰子，为什么不掷一个具有重复标签的12面公平骰子？由于我们知道如何模拟公平骰子，这相当于将范围 $[0,1)$[0,1) 分成以下十二个区间：

然后将它们分配给不同的结果，如下所示：

现在，模拟一个骰子的投掷非常简单 - 我们只需投掷这个新的公平骰子，然后读取它的值。这个第一步可以使用上面的算法来完成，它将给我们返回一个在范围 $0,1,...,11$0,1,...,11内的整数。要将该整数映射回原始的不公平骰子的一面，我们将存储一个大小为 12 的辅助数组，将这些数字中的每一个映射回原始的结果。从图形上看，我们可以如下所示：

为了将这个过程正式化为一个算法，我们将描述初始化步骤（创建映射表）和生成步骤（模拟随机骰子的投掷）。在这个算法和随后的算法中，这两个步骤都是重要的，因为设置时间可能会很长。

在初始化步骤中，我们首先找到我们所给定的骰子各面的概率的最小公倍数（在我们的示例中，这是12）。最小公倍数在这里很有用，因为它对应着我们可以用于所有分数的最小公共分母，因此也是新的公平骰子的面数。一旦我们有了这个最小公倍数（我们称之为 L），我们需要确定新骰子的每个面将分配给原始不公平骰子的哪个面。在我们的示例中，概率为 $\frac{1}{2}$21​ 的面在新骰子上有 6 个面，因为 $\frac{1}{2} \times 12=6$21​×12=6。同样地，概率为 $\frac{1}{3}$31​ 的面在新骰子上有 $4$4 个面，因为 $\frac{1}{3} \times 12=4$31​×12=4。更一般地，如果 $L$L 是概率的最小公倍数，$p_{i}$pi​ 是骰子的第 $i$i 面出现的概率，那么我们将把 $L⋅p_{i}$L⋅pi​ 个新骰子的面分配给原始不公平骰子的第 $i$i 面。

以下是上述算法的伪代码：

算法：使用公平骰子模拟不公平骰子

• 初始化：
  1. 找到概率 $p_{0}, p_{1}, ..., p_{n-1}$p0​,p1​,...,pn−1​ 的分母的最小公倍数；将其命名为 $L$L。
  2. 分配一个大小为 $L$L 的数组 $A$A，用于映射公平骰子的结果到原始骰子的结果。
  3. 对于原始骰子的每一面 $i$i，以任意顺序执行以下步骤：
     1. 将接下来 $L⋅p_{i}$L⋅pi​ 个 $A$A 中元素设置为 $i$i。
• 生成：
  1. 从一个 $L$L 面的公平骰子生成一个公平骰子的结果；将其命名为 $S$S。
  2. 返回 $A[S]$A[S]。

这个算法可能很简单，但它的效率如何？实际的骰子投掷生成非常快速 - 使用之前的算法生成随机骰子投掷只需要 $O(1)$O(1) 的工作量，再加上表格查找额外的 $O(1)$O(1) 工作量。这总共需要的工作量是 $O(1)$O(1)。因此，这个算法在时间复杂度上是非常高效的。

然而，初始化步骤可能会非常耗时。为了使这个算法工作，我们需要分配一个与所有输入分数的分母的最小公倍数一样大的数组空间。对于我们的示例（$\frac{1}{2}$21​、 $\frac{1}{3}$31​、 $\frac{1}{12}$121​ 、$\frac{1}{12}$121​），这个最小公倍数是 $12$12，但对于其他输入来说，它可能会变得非常差劲。举个例子，考虑分数 $\frac{999999}{1000000}$1000000999999​ 和 $\frac{1}{1000000}$10000001​。分母的最小公倍数是一百万，所以我们的表格将需要一百万个条目！

这意味着在某些情况下，初始化步骤可能会占用大量的空间。在考虑使用这个算法时，需要注意可能的空间复杂度问题。

不幸的是，情况可能比这更糟。在前面的例子中，我们至少可以说我们“预期”算法会使用大量内存，因为每个分数的分母都是一百万。然而，我们可能会遇到一组概率，其中最小公倍数远远大于任何单个分母。例如，考虑概率 $\frac{1}{15}$151​、$\frac{1}{10}$101​、$\frac{1}{6}$61​。在这里，分母的最小公倍数是$30$30，大于任何一个分母本身。这个构造之所以有效，是因为$15=3×5$15=3×5，$10=2×5$10=2×5，$6=2×3$6=2×3；换句话说，每个分母都是从三个素数中选择的两个素数的乘积。它们的最小公倍数因此是所有这些素数的乘积，因为每个分母都必须整除最小公倍数。如果我们将这个构造推广，并考虑任意一组 $k$k 个素数，那么如果我们为这些素数的每个两两乘积选择一个分数，那么最小公倍数可能远远大于任何单个分母。事实上，我们可以得出最小公倍数的一个最好的上界是 $O(\prod ^{n}_{i=1}d_{i})$O(∏i=1n​di​)，其中 $d_{i}$di​ 是第 $i$i 个概率的分母。这意味着，如果概率不是事先已知的，那么这个算法在任何实际场景中的使用都可能因为需要的内存太多而无法实现。

尽管如此，在许多情况下，这个算法的表现是良好的。如果所有的概率都相同，那么我们作为输入给定的所有概率都是 $\frac{1}{n}$n1​，其中 $n$n 是某个整数。然后，分母的最小公倍数是 $n$n，因此我们最终掷出的公平骰子将有 $n$n 个面，原始骰子的每个面将对应于公平骰子的一个面。初始化时间因此是 $O(n)$O(n)。从图形上看，这将如下所示：

下表总结了该算法的信息

这个算法的另一个重要细节是，它假设我们以分数的形式表示概率，这些分数具有适当的分母。如果概率以 IEEE-754 双精度浮点数的形式给出，那么这种方法可能会由于舍入而遭受严重误差；想象一下如果我们有 0.25 和 0.250000000001 作为概率！因此，除非在特殊情况下概率已知为良好且以有利于有理数运算的格式指定，否则最好不要尝试这种方法。

模拟有偏向硬币

我们从简单的随机基元（公平骰子）引申了一个简单但潜在效率低下的用于模拟不公平骰子算法。也许探索其他简单的随机基元可能会为解决这个问题提供不同的方法。

一个简单但有用的案例是使用随机生成器来模拟一个有偏向的硬币。假设有一枚硬币，正面朝上的概率为 $p_{heads}$pheads​，那么我们如何模拟投掷这枚有偏向的硬币呢？

我们之前形成的一个直觉是，我们可以将范围 $[0,1)$[0,1) 分成一系列小区间，以便当我们在该范围内选择一个随机值时，它最终会以与该区间的大小相等的概率进入某个区间。要使用在范围 $[0,1)$[0,1) 内均匀随机值来模拟有偏向的硬币，我们可以考虑将范围 $[0,1)$[0,1) 分割如下：

然后生成一个在范围 $[0,1)$[0,1) 内均匀随机的值，以确定它包含在哪个区间。幸运的是，由于只有一个分割点，确定点包含在哪个区间相当容易；如果值小于 $p_{heads}$pheads​，则硬币正面朝上，否则硬币反面朝上。以下是伪代码：

算法：模拟有偏向的硬币
生成一个在范围 $[0,1)$[0,1) 内均匀随机的值 $x$x。
如果 $x<p_{heads}$x<pheads​，则返回 “正面”。
如果 $x≥p_{heads}$x≥pheads​，则返回 “反面”。
由于我们可以在 $O(1)$O(1) 时间内生成范围 $[0,1)$[0,1) 内的均匀随机值，并且也可以在 $O(1)$O(1) 时间内进行实数比较，因此这个算法的运行时间为 $O(1)$O(1)。

用有偏向硬币模拟公平骰子

根据我们之前的讨论，我们知道可以使用一个公平骰子来模拟一个不公平的骰子，前提是我们愿意承受可能的空间使用增加。由于我们可以将有偏向的硬币看作一个有偏向的两面骰子，这意味着可以使用一个公平骰子来模拟一个有偏向的硬币。有趣的是，反过来也是可能的，我们可以使用有偏向的硬币来模拟公平骰子。这种构造方法简单而优雅，并且可以轻松推广到使用一组有偏向的硬币来模拟不公平的骰子。

有偏向的硬币的构造方法是基于硬币出现正面的概率将范围 $[0,1)$[0,1) 分为 “正面” 与 “反面” 区域 。我们已经在上面看到了类似的技巧，用于模拟一个公平的 $n$n 面骰子，通过将范围 $[0,1)$[0,1) 分成 $n$n 个大小相等的区域。例如，当掷一个四面骰子时，我们得到了这样的分区：

现在，假设我们有一组有偏向的硬币可供使用，我们有兴趣模拟掷一个公平骰子。我们可以考虑一种方法，从左到右穿越这些区间，每次都询问我们是否要停在当前所在的区间或继续前进。例如，假设我们想随机选择这四个区间中的一个。从最左边的区间开始，我们可以投掷一个有偏向的硬币，以确定我们是否应该停在这个区间或继续前进。由于我们想以概率 $\frac{1}{4}$41​ 均匀地选择所有这些区间，我们可以通过投掷一个出现正面概率为 $\frac{1}{4}$41​ 的有偏向硬币来实现这一点。如果它出现正面，我们就停在这个区间。否则，我们继续前进到下一个区间。

如果硬币出现反面，我们就会进入第二个区间，并且再次询问是否应选择这个区间或继续前进。最初，你可能认为我们应该再次投掷一个出现正面概率为 $\frac{1}{4}$41​ 的硬币来决定这一点，但实际上这是不正确的！看到这种推理的错误之处的一种方法是将其推向极端 - 如果在每个区间中我们都投掷一个出现正面概率为 $\frac{1}{4}$41​ 的硬币，有很小的概率每个区间都是反面，我们将拒绝每个区间。在某种程度上，当我们穿越这些区间时，我们需要增加硬币出现正面的概率。在极端情况下，如果我们最终进入最后一个区间，我们需要硬币以概率 $1$1 出现正面，因为如果我们拒绝了每一个之前的区间，正确的决定是停在最后一个区间。

为了确定我们的有偏向硬币在跳过第一个区间后出现正面的概率，注意如果我们确实跳过了第一个区间，那么只剩下三个区间。由于我们在掷一个公平骰子，我们希望这三个区间中的每一个都以概率 $\frac{1}{3}$31​ 被选择。因此，直观地看，我们应该让第二个硬币以概率 $\frac{1}{3}$31​ 出现正面。使用类似的论点，如果我们在第二个区间投掷反面，那么我们为第三个区间投掷的硬币应该以概率 $\frac{1}{2}$21​ 出现正面，而我们为最后一个区间投掷的硬币应该以概率 $1$1 出现正面。

这种直观的想法引导我们到以下算法。请注意，我们尚未论证这个算法是否正确；我们将在稍后进行讨论。

算法：使用有偏向硬币模拟公平骰子

1. 对于 $i$i 从 $0$0 到 $n-1$n−1：
   1. 投掷一个有偏向硬币，出现正面的概率为 $\frac{1}{n-i}$n−i1​ 。
   2. 如果硬币出现正面，返回 $i$i。

这个算法简单，并且在最坏情况下的运行时间为 $O(n)$O(n)。但是我们如何知道它实际上是正确的呢？为了证明这一点，我们需要以下定理：

定理：上述算法对于任何 $i$i 的选择都以概率 $\frac{1}{n}$n1​ 输出面 $i$i。

证明：假设任意常数 $n ≥ 0$n≥0。我们通过强归纳来证明每个面都有概率 $\frac{1}{n}$n1​ 被选择。

作为基本情况，我们证明骰子的第 $0$0 面以概率 $\frac{1}{n}$n1​ 被选择。但是这是直接从算法得出的 - 如果一个有偏向硬币以概率 $\frac{1}{n}$n1​ 出现正面，那么我们就选择第 $0$0 面，这意味着我们以概率 $\frac{1}{n}$n1​ 选择它。

对于归纳步骤，假设对于第 $0, 1, 2, ..., k-1$0,1,2,...,k−1 面，这些面都以概率 $\frac{1}{n}$n1​ 被选择，然后考虑第 $k$k 面被选择的概率。第 $k$k 面将被选择当且仅当前 $k$k 面都没有被选择，然后一个概率 $\frac{1}{n-k}$n−k1​ 出现正面的硬币出现正面。因为前 $k$k 面每个都以概率 $\frac{1}{n}$n1​ 被选择，而且只会选择其中一个面，所以前 $k$k 面中有一个被选择的概率为 $\frac{k}{n}$nk​。这意味着算法不选择前 $k$k 面的概率为 $1 - \frac{k}{n} = \frac{n-k}{n}$1−nk​=nn−k​。这意味着选择第 $k$k 面的概率为 $\frac{n-k}{n} \frac{1}{n-k} = \frac{1}{n}$nn−k​n−k1​=n1​，符合要求，完成了归纳。因此，每一面都以均匀随机的概率被选择。

当然，这个算法相当低效 - 我们可以使用之前的技术在 $O(1)$O(1) 时间内模拟一个公平骰子的投掷！ - 但这个算法可以作为一种步骤，用于构建一个使用有偏向硬币模拟不公平骰子的相对高效的算法。

用有偏向硬币模拟不公平骰子

上述算法很有趣，因为它提供了一种使用一组硬币模拟骰子的简单框架。我们首先翻转一枚硬币来确定是选择骰子的第一面还是继续选择剩余的面。在这个过程中，我们必须小心地扩大剩余的概率。

让我们看看如何使用这种技术来模拟一个不公平的骰子。让我们使用之前的例子，概率分别为 $\frac{1}{2}$21​、 $\frac{1}{3}$31​、 $\frac{1}{12}$121​ 和 $\frac{1}{12}$121​。回顾一下，这将范围 $[0,1)$[0,1) 分为以下部分：

现在，让我们考虑如何使用有偏向硬币来模拟这个不公平的骰子。我们可以开始翻转一枚硬币，它有 $\frac{1}{2}$21​ 的概率出现正面，以确定是否应该输出第 $0$0 面。如果这枚硬币出现正面，那太好了！我们完成了。否则，我们需要再翻一枚硬币来确定是否选择下一面。与之前一样，尽管下一面出现的概率为 $\frac{1}{3}$31​，但我们不想翻一枚出现正面概率为 $\frac{1}{3}$31​ 的硬币，因为当我们没有选择第 $\frac{1}{2}$21​ 面时，就已经丢掉了一半的概率。实际上，由于一半的概率已经消失了，如果我们此时重新调整剩余的概率，我们会得到更新后的概率为 $\frac{2}{3}$32​、$\frac{1}{6}$61​、$\frac{1}{6}$61​。因此，第二枚硬币应该以概率 $\frac{2}{3}$32​ 出现正面。如果这枚硬币也出现反面，那么我们必须在两个 $\frac{1}{12}$121​ 面之间进行选择。由于在这一点上已经消失了 $\frac{5}{6}$65​ 的概率质量，我们将重新调整 $\frac{1}{12}$121​ 面的概率，以使每个面都有 $\frac{1}{2}$21​ 的概率出现正面，因此第三枚硬币将以概率 $\frac{1}{2}$21​ 出现正面。如果最后一枚硬币被翻转，那么它必须以概率 $1$1 出现正面，因为它是最后一个区间。

总结一下，硬币的概率如下：

第一次翻转：$\frac{1}{2}$21​
第二次翻转：$\frac{2}{3}$32​
第三次翻转：$\frac{1}{2}$21​
第四次翻转：$1$1

尽管这些数字从直觉上看可能有意义，但要将其转化为算法，我们需要为选择概率提供正式的构建。思路如下 - 在每个步骤中，我们都记住了还有多少概率质量待使用。在开始之前，在翻转任何硬币之前，这个值为 $1$1。翻转第一枚硬币后，它变为 $1 - p_{0}$1−p0​。翻转第二枚硬币后，它变为 $1 - p_{0} - p_{1}$1−p0​−p1​。更一般地说，翻转了 $k$k 枚硬币后，剩余的概率质量为 $1-\sum ^{k-1}_{i=0}p_{i}$1−∑i=0k−1​pi​ 。每当我们翻转一枚硬币来确定是否选择第 $k$k 个区间时，我们实际上是在翻转一枚硬币，其正面出现的概率等于剩余概率中由概率 $p_{k}$pk​ 占据的部分，这个概率由 $\frac{p_{k}}{1-\sum ^{k-1}_{i=0}p_{i}}$1−∑i=0k−1​pi​pk​​ 给出。这为我们提供了使用一组有偏向硬币模拟有偏向骰子的以下算法（同样，我们稍后将证明其正确性和运行时间）：

算法：使用有偏向硬币模拟有偏向骰子

• 初始化：
  存储后续需要使用的概率 $p_{i}$pi​。
• 生成：
  1. 设置 $mass=1$mass=1
  2. 对于 $i$i 从 $0$0 到 $n-1$n−1：
     1. 翻转一枚有偏向硬币，正面出现的概率为 $\frac{p_{i}}{mass}$masspi​​。
     2. 如果正面出现，返回 $i$i。
     3. 否则，设置 $mass=mass−p_{i}$mass=mass−pi​。

虽然这可能在直觉上有一定的道理，但从数学上来说，它是否正确呢？幸运的是，答案是肯定的，这要归功于对上面证明的一个推广，以下是具体的推广内容：

定理：上述算法对于任何选择的 $i$i，以概率 $p_{i}$pi​ 输出边 $i$i。

证明：考虑任意固定的 $n≥0$n≥0。我们通过强归纳来证明 $n$n 个边中的每个边都具有概率 $p_{i}$pi​ 被选择的特性。

作为基本情况，我们展示骰子的边 $0$0 具有概率 $p_{0}$p0​ 被选择。如果第一次硬币翻转出现正面，我们选择边 $0$0，这以概率 $\frac{p_{0}}{mass}$massp0​​ 发生。由于 $mass$mass 最初为 $1$1，这个概率为 $\frac{p_{0}}{1}=p_{0}$1p0​​=p0​，因此边 $0$0 以概率 $p_{0}$p0​ 被选择，符合要求。

对于归纳步骤，假设边 $0、1、...、k-1$0、1、...、k−1 被选择的概率分别为 $p_{0}、p_{1}、...、p_{k-1}$p0​、p1​、...、pk−1​，然后考虑边 $k$k 被选择的概率。边 $k$k 将被选择当且仅当前 $k$k 个边都未被选择，然后一枚正面概率为 $\frac{p_{k}}{mass}$masspk​​ 的硬币翻转正面。因为前 $k$k 个边都以正确的概率被选择，而且只有一个边被选择，所以前 $k$k 个边中至少选择一个的概率由 $\sum ^{k-1}_{i=0}p_{i}$∑i=0k−1​pi​ 给出。这意味着算法不选择前 $k$k 个边的总概率为 $1-\sum ^{k-1}_{i=0}p_{i}$1−∑i=0k−1​pi​。现在，边 k 的硬币翻转正面的概率为 $\frac{p_{k}}{mass}$masspk​​，经过 $k$k 次迭代后，我们可以快速归纳出 $mass=1-\sum ^{k-1}_{i=0}p_{i}$mass=1−∑i=0k−1​pi​。这意味着选择边 $k$k 的总概率为 $(1-\sum ^{k-1}_{i=0}p_{i})\frac{p_{k}}{1-\sum ^{k-1}_{i=0}p_{i}}=p_{k}$(1−∑i=0k−1​pi​)1−∑i=0k−1​pi​pk​​=pk​，符合要求，完成了归纳证明。

现在，让我们考虑这个算法的运行时复杂度。我们知道初始化时间将是 $Θ(1)$Θ(1)（如果我们保留输入概率数组的浅拷贝），但如果我们要存储自己的版本数组（以防调用者以后想要更改它），则可能是 $Θ(n)$Θ(n)。实际生成骰子投掷结果可能在最坏情况下需要翻转 $Θ(n)$Θ(n) 枚硬币，但在最佳情况下只需要翻转一次硬币。

然而，经过一些思考，可以清楚地看出输入分布会严重影响我们需要翻转多少次硬币。在绝对最佳情况下，我们有一个概率分布，其中所有的概率质量都集中在骰子的第一个面上，而其余的概率都为零。在这种情况下，我们只需要翻转一次硬币。在绝对最坏情况下，所有的概率质量都集中在骰子的最后一个面上，其他地方都是零，这种情况下，我们将需要翻转 n 枚硬币才能找到结果。

我们可以精确而数学地描述这个算法的预期硬币翻转次数。让我们考虑一个随机变量 $X$X，表示在某个特定分布上执行此算法时翻转的硬币数量。也就是说，$ℙ[X=1]$P[X=1] 表示算法在终止之前翻转一枚硬币的概率，$ℙ[X=2]$P[X=2] 表示算法在终止之前翻转两枚硬币的概率，依此类推。在这种情况下，我们的算法的预期硬币翻转次数由随机变量 X 的期望值给出，表示为 $𝔼[X]$E[X]。根据定义，我们有以下公式：

$$𝔼[X]=\sum ^{n}_{i=1}i⋅ℙ[X=i]$$E[X]=i=1∑n​i⋅P[X=i]

那么 $ℙ[X=i]$P[X=i] 的值是多少呢？嗯，算法将在选择了骰子的某一面后终止。如果选择了第 $0$0 面，它将翻一枚硬币来决定是否停在那里。如果选择了第 $1$1 面，它将翻两枚硬币 - 一枚来表示不想选择第 $0$0 面，另一枚来表示想要选择第 $1$1 面。更一般地说，如果算法选择了第 $i$i 面，它将翻 $i+1$i+1 枚硬币，其中 $i$i 枚用于决定不选择前面的 $i-1$i−1 面，一枚用于决定选择第 $i$i 面。结合我们知道的第 $i$i 面被选择的概率 $p_{i}$pi​，这意味着：

$$𝔼[X] = \sum_{i=1}^{n} i \cdot ℙ[X = i] = \sum_{i=1}^{n} i \cdot p_{i-1} = \sum_{i=1}^{n} ((i-1)p_{i-1} + p_{i-1}) = \sum_{i=1}^{n} (i-1)p_{i-1} + \sum_{i=1}^{n} p_{i-1}$$E[X]=i=1∑n​i⋅P[X=i]=i=1∑n​i⋅pi−1​=i=1∑n​((i−1)pi−1​+pi−1​)=i=1∑n​(i−1)pi−1​+i=1∑n​pi−1​

在最后的简化中，注意到第一项等于 $\sum ^{n-1}_{i=0}i⋅p_{i}$∑i=0n−1​i⋅pi​，这等于 $𝔼[p]$E[p]；即骰子投掷的期望结果！而第二项是 $1$1，因为它是总概率的和。这意味着 $𝔼[X]=𝔼[p]+1$E[X]=E[p]+1。也就是说，硬币翻转的预期次数等于骰子投掷的预期值再加上1！