飞镖，骰子和硬币：离散分布算法

我曾经问过Stack Overflow一个关于作弊骰子的数据结构的问题。 我对这个问题的答案特别感兴趣：“如果我们有一个n面骨骼，那么我的脸有可能掉出p _i 。 模拟这种骨头的滚动最有效的数据结构是什么？”

此数据结构可用于许多任务。 例如，您可以使用它来模拟诚实的十六进制滚动，分配概率 $$$\ frac {1} {6}$ 骨头的每一侧，或通过模仿双侧骨头来模拟公平的硬币，从两侧掉出的概率等于 $$$\ frac {1} {2}$ 。 您还可以使用此数据结构通过创建11面的骨骼（面为2、3、4，...，12）直接模拟两个诚实的六边形骨骼的总和，该骨骼的每个面具有与两个诚实的骨骼卷相对应的概率权重。 但是，您也可以使用此数据结构来模拟欺诈骨骼。 例如，如果您玩的是不完全诚实的骨头掷骰子 ，则可以使用此数据结构来模拟很多骨头掷骰并分析最佳策略。 您也可以尝试模拟同样不完美的轮盘 。

如果您不参加游戏，则可以在传感器故障级别已知的机器人的仿真中应用此数据结构。 例如，如果范围传感器有95％的概率返回正确的值，4％的概率太小值和1％的概率太高的值，则可以使用此数据结构通过生成随机结果来模拟读取传感器的读数并模拟传感器的读数结果。

我在Stack Overflow上收到的答案使我印象深刻，原因有两个。 首先，在解决方案中，建议我使用一种称为别名方法的强大技术，该方法在对机器模型进行某些合理假设的前提下，能够在简单的初步准备阶段之后随时间推移模拟骨骼滚动 $$$O（1）$ 。 其次，令我惊讶的是，该算法已经存在了数十年，但我从未见过！ 考虑到在模拟上花费了多少计算时间，人们可以期望这项技术广为人知。 在Google上进行的一些查询为我提供了有关此技术的大量信息，但是我找不到一个站点可以将对这种技术的直观理解与解释结合在一起。

本文是我的尝试，简要概述从简单且非常不切实际的技术到非常优化且有效的别名方法，来模拟欺骗骨骼的不同方法。 我希望我能够传达出各种直观地理解任务的方式，以及每种方式如何强调模拟作弊骨骼的一些新方面。 对于每种方法，我的目标是研究一种激励思想，一种基本算法，保真度证明以及运行时分析（根据所需的时间，内存和随机性）。

参赛作品

在继续介绍各种技术的具体细节之前，让我们首先对术语和符号进行标准化。

在本文的引言中，我使用“作弊骨骼”一词来描述一个广义场景，其中存在有限的结果集，每个结果都有一个概率，正式地，这称为离散概率分布 ，而模拟作弊骨骼的任务称为从离散分布中采样 。

为了描述我们的离散概率分布（骗子骨头），我们假设我们有一组n个概率 $$$p_0，p_1，...，p_ {n-1}$ 与结果有关 $$$0，1，...，n-1$ 。 虽然结果可以是任意值（鹰/尾巴，骨头上的数字，颜色等），但为简单起见，我将结果视为对应于给定索引的某种正实数。

在计算机上使用实数是计算的“灰色领域”。 有许多快速算法，其速度仅由能够在恒定时间内计算任意实数的下限函数提供 ，并且浮点数表示中的数值不正确会完全破坏某些算法。 因此，在开始讨论适用于概率的算法之前，即进入实数的黑暗世界之前，我必须阐明计算机可以做什么和不能做什么。

在下文中，我将假定可以在恒定时间内执行以下所有操作：

• 加法。 任意实数的减法，乘法，除法和比较 。 我们将需要执行此操作来操纵概率。 这似乎是一个大胆的假设，但是如果我们假设任何实数的精度受到机器字长的多项式的限制（例如，在32位机器上为64位double的整数），但我认为这不太合理。
• 在区间[0，1）中生成统一的实数。 为了模拟随机性，我们需要一些随机值源。 我想我们可以在恒定时间内生成任意精度的实数。 这远远超出了实际计算机的功能，但在我看来，出于讨论目的，这是可以接受的。 如果我们同意通过说任意IEEE-754倍数在[0，1]区间内牺牲了一部分精度，那么我们实际上将失去精度，但是结果对于大多数应用来说可能足够精确。
• 计算实数的整数下限（四舍五入）。 如果我们假设我们使用的是IEEE-754 double，那么这是可以接受的，但是通常，对计算机的这种要求是不可行的。

值得提出一个问题-假设我们可以有效地执行所有这些操作是否合理？ 实际上，我们很少使用所指示的概率达到IEEE-754 double内在的舍入误差会导致严重问题的准确度，因此我们仅通过与IEEE double一起工作就可以满足上述所有要求。 但是，如果我们所处的环境中准确地将概率表示为高精度的有理数，则此类限制可能是不合理的。

诚实的骨骼模拟

在继续讨论抛出任意作弊骨骼的更一般情况之前，让我们从一个更简单的算法开始，该算法将用作以下算法的构建块：模拟一个诚实的n面骨骼。 例如，在玩“大富翁”或“风险”游戏时，诚实的六角形骰子掷骰，或者扔出诚实的硬币（双面骰子）等对我们有用。

对于这种特殊情况，有一种简单，优雅且有效的算法来模拟结果。 该算法基于以下思想：假设我们可以在区间中生成真正随机的，均匀分布的实数 $$$[0，1）$ 。 此间隔可以说明如下：


现在，如果我们想退出 $$$n$ 切面的骨头，那么一种方法是分割间隔 $$$[0，1）$ 在 $$$n$ 大小相等的区域，每个区域都有一个长度 $$$\ frac {1} {n}$ 。 看起来像这样：


接下来，我们在区间中生成一个随机选择的实数 $$$[0，1）$ 那肯定属于这些小区域之一。 据此，我们可以通过查看数字掉入的区域来计算出骨头滚动的结果。 例如，如果我们随机选择的值落入该位置：


那么我们可以说2落在了骨骼上（如果我们假设骨骼的边缘是从头开始索引的）。

从图形上很容易看出哪个区域具有随机值，但是如何在算法中对其进行编码？ 在这里，我们利用了一个事实，那就是诚实。 由于所有间隔的大小相等，即 $$$\ frac {1} {n}$ ，那么我们可以看到最大的价值是什么 $$$我$ 就是这样 $$$\ frac {i} {n}$ 只不过是随机生成的值（我们将此值称为x）。 您可能会注意到，如果我们想找到最大值， $$$\ frac {i} {n} \ le x$ ，这类似于找到最大值 $$$n$ 这样 $$$i \ le xn$ 。 但是根据定义，这意味着 $$$i = \ lfloor xn \ rfloor$ ，最大正整数不大于xn。 因此，这使我们想到了这种（非常简单的）诚实的多面骨骼模拟算法：

算法：诚实的骨骼模拟

1. 生成均匀分布的随机值 $$$x$ 在范围内 $$$[0，1）$ 。
2. 回程 $$$\ lfloor xn \ rfloor$ 。

鉴于以上关于计算的假设，该算法可以及时运行 $$$O（1）$ 。

从本节可以得出两个结论。 首先，我们可以分割时间间隔 $$$[0，1）$ 部分是为了使在此间隔内均匀分布的随机实数自然地减少为我们可用的许多离散选项之一。 在本文的其余部分，我们将积极利用此技术。 其次，确定随机值属于哪个特定间隔可能很困难，但是如果我们对部分有所了解（在这种情况下，它们的大小都相同），那么我们可以在数学上简单地确定哪个部分引用了某个特定值点。

用诚实的骨头欺骗骨头

有了诚实的骨骼模拟算法，我们能否使其适应模拟作弊的骨骼？ 有趣的是，答案是肯定的，但是解决方案将需要更多的空间。

从上一节中可以很直观地看出，为了模拟作弊的骨骼投掷，足以划分间隔 $$$[0，1）$ 碎片，然后确定我们击中了哪一部分。 但是，在一般情况下，这可能比看起来要复杂得多。 假设我们有一个具有面子概率的四面体 $$$\ frac {1} {2}$ ， $$$\ frac {1} {3}$ ， $$$\ frac {1} {12}$ 和 $$$\ frac {1} {12}$ （我们可以确保这是正确的概率分布，因为 $$$\ 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}$ ） 如果我们划分间隔 $$$[0，1）$ 分成这些大小的四个部分，然后得到以下结果：


不幸的是，在这一步我们被困住了。 即使我们知道间隔中的一个随机数 $$$[0，1）$ ，那么就没有简单的数学技巧可以自动确定该数字属于哪个部分。 我不想说这是不可能的-正如您将看到的，我们可以使用许多出色的技巧-但它们都没有诚实的掷骨算法的数学简单性。

但是，在这种情况下，我们也可以调整用于诚实骨骼的技术。 让我们以上面讨论的骨头为例。 下降边缘的概率为 $$$\ frac {1} {2}$ ， $$$\ frac {1} {3}$ ， $$$\ frac {1} {12}$ 和 $$$\ frac {1} {12}$ 。 如果我们重写此代码，以便所有成员都有一个共同的除数，我们将获得值 $$$\ frac {6} {12}$ ， $$$\ frac {4} {12}$ ， $$$\ frac {1} {12}$ 和 $$$\ frac {1} {12}$ 。 因此，我们可以将任务理解为：与其抛掷具有加权概率的四面体骨骼，不为什么抛掷12面诚实的骨骼，其边缘上有重复的值？ 因为我们知道如何模拟诚实的骨头，所以这类似于间隔分离 $$$[0，1）$ 以这种方式分解：


然后，我们将它们分配给各种结果，如下所示：


现在，模拟骨骼抛出将非常简单-我们只需扔掉这个新的诚实骨骼，然后查看哪一张面孔掉下来并读取其值即可。 第一步可以通过上面介绍的算法执行，这将为我们提供区间中的整数 $$$0，1，...，11$ 。 为了将此整数绑定到原始作弊者骨骼的一个面，我们将存储一个包含十二个元素的辅助数组，这些数组将这些数字中的每一个与原始结果连接起来。 可以用图形表示如下：


为了以算法的形式对此进行形式化，我们描述了初始化阶段（获取表）和生成阶段（模拟随机的骨骼抛出）。 这两个步骤在此算法和后续算法中都必须考虑，因为准备时间应该很长。

在初始化阶段，我们首先寻找为骨骼边缘指定的所有概率中的最小公倍数 （在我们的示例中，LCL为12）。 NOC在这里很有用，因为它对应于我们可用于所有分数的最小公因数，因此对应于我们将滚动的新诚实骨骼的面数。 收到此NOC（用L表示）后​​，我们必须确定将在原始作弊者骨骼的每个面孔上分布多少个新骨骼面孔。 在我们的示例中，具有概率的面孔 $$$\ frac {1} {2}$ 自从获得新骨骼的六个侧面以来， $$$\ frac {1} {2} \乘以12 = 6$ 。 同样，有概率的一方 $$$\ frac {1} {3}$ 自从获得4张面孔 $$$\ frac {1} {3} \乘以12 = 4$ 。 以更一般的形式，如果L是概率的LCL，并且 $$$p_i$ 是一张脸的概率 $$$我$ 骨头，然后突出脸部 $$$我$ 原始的沙皮狗骨头 $$$L \ cdot p_i$ 诚实的骨头方面。

这是上述算法的伪代码：

算法：用诚实的骨头模拟作弊的骨头

• 初始化 ：
  
  1. 查找概率分母的NOC $$$p_0，p_1，...，p_ {n-1}$ ; 表示它 $$$L$
  2. 选择一个阵列 $$大小 $$$L$ 比较诚实的骨头滚和原始骨头的滚的结果。
  3. 对于每一张脸 $$$我$ 对于初始骨骼，我们可以按任何顺序执行以下操作：
     
     1. 我们分配如下 $$$L \ cdot p_i$ 元素 $$价值 $$$我$ 。
• 代 ：
  
  1. 我们为 $$$L$ 脸骨 叫脸 $$$S$ 。
  2. 回程 $$$A [S]$ 。

该算法可能很简单，但是效率如何？ 骨卷的生成非常快-每个骨卷都需要 $$$O（1）$ 运行时使用先前的算法生成随机骰子掷骰，以及更多 $$$O（1）$ 工作时间搜索表。 这给了我们总的工作时间。 $$$O（1）$ 。

但是，初始化步骤可能会非常昂贵。 为了使该算法起作用，我们需要为所有输入分数的分母的NLC大小的数组分配空间。 在我们的示例中（ $$$\ frac {1} {2}$ ， $$$\ frac {1} {3}$ ， $$$\ frac {1} {12}$ ， $$$\ frac {1} {12}$ ），它是12，对于其他输入值，该值在病理上可能是错误的。 例如，让我们看一下分数 $$$\ frac {999999} {1,000,000}$ 和 $$$\ frac {1} {1000000}$ 。 分母的NOC等于一百万，所以我们的表中应该有一百万个元素！

不幸的是，情况可能更糟。 在前面的示例中，我们至少可以“期望”该算法占用大量内存，因为分数的两个分母都等于一百万。 但是，我们可能有许多概率的NOC明显大于每个单独的分母。 例如，让我们看一下概率 $$$\ frac {1} {15}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {5} {6}$ 。 此处分母的NOC为30，大于任何分母。 设计在这里起作用是因为 $$$15 = 3 \乘5$ ， $$$10 = 2 \乘5$ 和 $$$6 = 2 \乘以3$ ; 换句话说，每个分母都是从三个值的集合中选择的两个素数的乘积。 因此，它们的NOC是所有这些质数的乘积，因为每个分母都必须是NOC的除数。 如果我们对这种结构进行概括并考虑任何一组 $$$k$ 质数，并为这些质数的每个成对乘积取一个分数，那么NOC将远远大于每个单独的分母。 实际上，我们可以为NOC获得的最佳上限之一是 $$$O（\ prod_ {i = 0} ^ n {d_i}）$ 在哪里 $$$d_i$ 是分母 $$$我$ 那个概率。 当概率未知时，这不允许在实际条件下使用这种算法，因为存储大小表需要内存 $$$O（\ prod_ {i = 0} ^ n {d_i}）$ ，它很容易超过内存中的容量。

换句话说，在许多情况下，该算法的性能都很好。 如果所有概率都相同，那么在输入处获得的所有概率都相等 $$$\ frac {1} {n}$ 对于一些 $$$n$ 。 那么NOC分母等于 $$$n$ ，也就是说，诚实的骨头将具有 $$$n$ 面，原始骨骼的每个面将对应于诚实骨骼的一个面。 因此，初始化时间为 $$$O（n）$ 。 可以用图形表示如下：


这为我们提供了有关该算法的以下信息：

演算法	初始化时间		产生时间		内存占用
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$

关于此算法的另一个重要细节：它假定我们将以具有良好分母的分数的形式接收方便的概率。 如果将概率指定为IEEE-754的两倍，则由于舍入误差小，这种方法可能会造成灾难性的后果； 假设我们有0.25和0.250000000001的概率！ 因此，最好不要使用这种方法，除非在特殊情况下，概率表现良好，并以与有理数运算对应的格式指定。

非对称硬币模拟

我们对一个简单的随机原始（诚实的骨头）的解释导致了一个简单但可能非常无效的作弊骨骼模拟算法。 也许对其他简单随机基元的研究将为解决该问题的其他方法提供一些启示。

一个简单但令人惊讶的有用任务是使用随机数生成器模拟非对称硬币。 如果我们有一个硬币的可能性是鹰 $$$p_ {heads}$ ，那么我们如何模拟这种不对称硬币的投掷？

之前，我们开发了一种直观的方法：间隔分区 $$$[0，1）$ 在这样的区域序列上，当在间隔中选择一个随机值时，它会以等于区域大小的概率出现在某些区域中。 使用间隔中均匀分布的随机值模拟不对称硬币 $$$[0，1）$ 我们必须打破间隔 $$$[0，1）$ 如下：


然后在区间内生成均匀分布的随机值 $$$[0，1）$ 看看它在哪个区域。 幸运的是，我们只有一个分割点，因此很容易确定该点在哪个区域。 如果值小于 $$$p_ {heads}$ ，然后老鹰落在硬币上，否则-尾巴。 伪代码：

算法：模拟非对称硬币

1. 在间隔中生成均匀分布的随机值 $$$[0，1）$ 。
2. 如果 $$$x <p_ {heads}$ ，返回“老鹰”。
3. 如果 $$$x \ ge p_ {heads}$ ，返回尾巴。

由于我们可以在区间内生成均匀分布的随机值 $$$[0，1）$ 及时地 $$$O（1）$ ，我们还可以比较的实数 $$$O（1）$ ，那么该算法会及时运行 $$$O（1）$ 。

使用不对称硬币模拟诚实的骨头

从前面的讨论中，我们知道，如果我们准备花费额外的内存空间，就可以使用诚实骨骼来模拟欺骗骨骼。 由于我们可以将不对称硬币视为欺骗的双侧骨骼，因此这意味着我们可以在诚实骨骼的帮助下模拟不对称硬币。 有趣的是，也可以做相反的事情-使用非对称硬币模拟诚实的骨头。该设计简单，优雅，并且可以使用各种不对称硬币很容易地推广到模拟作弊的骨骼。

模拟非对称硬币的设计将区间分割$$$[0, 1)$为两个区域-区域“鹰”和区域“尾部”基于骨鹰丢失的概率。我们已经看到了用于模拟诚实行为的类似技巧$$$n$面骨：间隔$$$[0, 1)$分为$$$n$相等的面积。例如，当扔四面体骨骼时，我们得到以下分离：


现在，假设我们有兴趣使用一组非对称硬币来模拟这个诚实的骨头。一种解决方法如下：假设我们每次从左到右绕过这些区域，每次询问是否要在当前区域停留，或者是否继续前进。例如，假设我们要随机选择这些区域之一。从最左边的区域开始，我们将翻转一个不对称的硬币，这告诉我们是应该在该区域中停止还是继续前进。由于我们需要从所有这些区域中统一选择概率$$$\frac{1}{4}$，那么我们可以通过扔一个不对称的硬币来做到这一点$$$\frac{1}{4}$ 。如果有鹰落下，那么我们将停在当前区域。否则，我们将移至下一个区域。

如果硬币掉下来了，那么我们发现自己处于第二个区域，并再次询问我们应该再次选择该区域还是继续移动。您可能会认为，为此，我们必须投掷另一枚可能带有鹰的硬币$$$\frac{1}{4}$，但实际上并非如此！要了解这种推理的缺陷，我们必须采取一种极端的情况-如果在每个区域中投掷一枚硬币，老鹰很有可能落在上面$$$\frac{1}{4}$也就是说，，在每个区域中硬币掉下来的可能性很小，也就是说，我们将不得不放弃所有区域。在区域之间移动时，我们需要以某种方式继续增加鹰落在硬币上的可能性。在极端情况下，如果我们发现自己处于最后一个区域，那么硬币必须有一只老鹰，其概率为$$$1$，因为如果我们拒绝所有先前的区域，那么正确的决定就是在最后一个区域停止。

为了确定我们的不对称硬币在跳过第一个区域后扔鹰的概率，我们需要注意，在跳过第一个区域后仅剩三个。当我们做一个诚实的骨头时，我们需要以概率选择这三个区域中的每一个$$$\frac{1}{3}$ 。 因此，从直觉上看，似乎我们应该有第二只骨头，老鹰很有可能掉在上面 $$$\frac{1}{3}$ 。 使用类似的推理，可以理解的是，当在第三区域的格子的第二区域出现尾巴时，老鹰应该很可能将硬币掉落 $$$\frac{1}{2}$，并且在最后一个区域中-很有可能$$$1$ 。

这种直观的理解将我们引向以下算法。注意，我们没有讨论此算法的正确性或谬误；很快我们会做到的。

算法：使用非对称硬币模拟诚实的骨头

1. 对于 $$$i = 0$至$$$n - 1$ ：
   
   1. 投掷不对称硬币并有鹰的可能性 $$$\frac{1}{n - i}$ 。
   2. 如果老鹰掉落，则返回 $$$我$ 。

该算法很简单，并且在最坏的情况下可以及时运行。 $$$O（n）$ 。但是，我们如何检查是否正确？为了找出答案，我们需要以下定理：

定理：以上算法返回边$$$我$可能$$$\frac{1}{n}$为任何选定的$$$我$ 。

证明：考虑任何常数$$$n \ge 0$ 。 使用强归纳法，我们证明了每个 $$$n$面孔有选择的可能性$$$\frac{1}{n}$ 。

对于我们的示例，我们表明 $$$0$骰子有选择的可能性$$$\frac{1}{n}$ 。 但这直接来自算法本身-如果在非对称硬币上使用鹰的概率，我们选择面0 $$$\frac{1}{n}$ , $$$\frac{1}{n}$ 。

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ 。 $$$k$当且仅当将被选择不选择第一$$$k$面孔，并在硬币上有老鹰的可能性$$$\frac{1}{n - k}$ . $$$k$面孔有选择的可能性$$$\frac{1}{n}$ , , $$$k$为$$$\frac{k}{n}$ 。 这意味着算法未选择第一个算法的概率 $$$k$面孔等于$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ 。 也就是说，选择面孔的可能性 $$$k$为$$$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$，将被显示。因此，均匀且随机地选择骨骼的每个面。

当然，该算法效率很低-使用第一种技术，我们可以及时模拟一轮诚实骰子 $$$O(1)$！但是，该算法可以用作有效算法的垫脚石，该算法可使用非对称硬币来模拟欺诈骨骼。

使用不对称硬币进行舒勒骨骼模拟

上面介绍的算法很有趣，因为它为我们提供了使用一组硬币来模拟骨骼的简单框架。我们从投掷硬币开始，以确定是选择骨骼的第一个面还是移动到其余的面。在此过程中，我们需要仔细处理剩余概率的规模。

让我们看看如何使用此技术来模拟作弊的骨骼投掷。我们将示例与概率一起使用$$$\frac{1}{2}$ ， $$$\frac{1}{3}$ ， $$$\frac{1}{12}$ ， $$$\frac{1}{12}$ 。 他，如果您不记得，将间隔 $$$[0, 1)$如下：


现在，让我们考虑如何使用非对称硬币来模拟这种作弊的骨骼。我们可以先投掷具有老鹰概率的硬币$$$\frac{1}{2}$以确定是否应该返回面0。如果有鹰落在该硬币上，那就好！我们完成了。否则，我们需要扔另一个硬币来决定是否选择下一个构面。和以前一样，尽管下一个方面有选择的可能性$$$\frac{1}{3}$，我们不想投掷一枚老鹰有可能掉落的硬币$$$\frac{1}{3}$，因为当我们没有选择行时，一半的“质量”概率被丢弃了$$$\frac{1}{2}$ 。 实际上，由于一半的概率已消失，因此，如果我们对剩余的概率重新进行归一化，我们将获得更新的概率： $$$\frac{2}{3}$ ， $$$\frac{1}{6}$ ， $$$\frac{1}{6}$ 。 因此，第二枚硬币必须以概率抛出 $$$\frac{2}{3}$ 。 如果这枚硬币也是尾巴，那么我们必须在两侧之间进行选择 $$$\frac{1}{12}$ 。 因为在这个阶段我们将摆脱 $$$\frac{5}{6}$质量的概率，那么我们可以再次归一化各方的概率$$$\frac{1}{12}$这样每个人都有机会$$$\frac{1}{2}$滴鹰，即第三枚硬币有几率$$$\frac{1}{2}$ 。 最后的硬币，如果碰到她的话，应该很有可能扔鹰 $$$1$因为这是最近的区域。

总而言之，硬币的概率如下：

1. 第一卷： $$$\frac{1}{2}$
2. 第二卷： $$$\frac{2}{3}$
3. 第三卷： $$$\frac{1}{2}$
4. 第四卷： $$$1$

这些数字的来源可能很直观，但是为了将选择转换为算法，我们必须创建概率选择的形式构造。这个想法将是以下内容-在每个阶段，我们都会记住其余的概率。开始时，在投掷第一个硬币之前，它等于$$$1$ 。 抛第一枚硬币后 $$$1 - p_0$ 。 抛第二枚硬币后 $$$1 - p_0 - p_1$ 。 投掷后更普遍 $$$k$概率的余数为$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ 。 每次我们掷硬币以确定是否选择区域 $$$k$，结果我们扔了一个硬币，鹰落在上面的概率等于剩余概率所占概率的分数$$$p_k$，定义为$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ 。 这为我们提供了以下算法，用于使用一组不对称硬币欺骗骨骼模拟（我们将在下面证明其正确性和运行时间）：

算法：不对称硬币的舒勒骨头

• 初始化：
  
  1. 我们保持概率 $$$p_i$供进一步使用。
• 代：
  问$$$mass = 1$
  对于$$$i = 0$ to $$$n - 1$ ：
  
  1. $$$\frac{p_i}{mass}$ 。
  2. , $$$我$ 。
  3. $$$mass = mass - p_i$

, ? , :

: $$$我$ $$$p_i$ $$$我$ 。

: $$$n \ge 0$ 。 , $$$n$ $$$p_i$ 。

, $$$0$ $$$p_0$ 。 $$$0$ , , $$$\frac{p_0}{mass}$ 。 $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ 。 $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ 。 , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ 。 , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ 。 , $$$k$ $$$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$ , .

. , $$$\Theta(1)$ , , $$$\Theta(n)$ , ( , ). $$$\Theta(n)$ , .

, . , , . . , . $$$n$ .

. $$$X$ , . $$$\mathbb{P}[X = 1]$ , , $$$\mathbb{P}[X = 2]$ — , , .. $$$X$ , $$$\mathbb{E}[X]$ 。 ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

$$$\mathbb{P}[X = i]$ ？ - . $$$0$ , . $$$1$ , — , $$$0$ , , $$$1$ 。 , $$$我$ , $$$i + 1$ : $$$我$ , , $$$i - 1$ , , , $$$我$ 。 , $$$我$ $$$p_i$ , ,

$$ $$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[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}}$$

请注意，在最后的简化中，第一项等效 $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ 等价的 $$$\ mathbb {E} [p]$ ，掷骰子的预期结果！ 而且，第二项等于 $$$1$ 因为这是所有概率的总和。 这意味着 $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ 。 也就是说，预期的掷硬币数量等于一加上掷骰的数学期望！

演算法	初始化时间		产生时间		忙碌的记忆
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$
不对称硬币的舒勒骨头	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$	$$$\ Theta（n）$

泛化不对称硬币：模拟欺诈骨骼

在上面显示的示例中，由于仅需考虑一个分割点，因此我们能够有效地模拟非对称硬币。 我们怎样才能有效地将这个想法推广到一个骗人的骨头上，其中面孔的数量可以是任意的？

如您所见，不对称硬币是欺骗性的骨骼，只有两个面。 因此，我们可以简单地将不对称硬币视为要解决的更一般问题的特例。 在解决非对称硬币问题时，我们将区间除以 $$$[0，1）$ 分为两个区域-一个区域用于鹰，第二个区域用于尾巴-然后使用只有一个分割点的事实来查找该区域。 如果我们的骨骼是n面的，那么就会有更多的区域，因此会有几个分割点。 例如，假设我们有一个具有概率的七面骨头 $$$\ frac {1} {4}$ ， $$$\ frac {1} {5}$ ， $$$\ frac {1} {8}$ ， $$$\ frac {1} {8}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {10}$ 。 如果我们要分割间隔 $$$[0，1）$ 分为七个部分，然后我们按如下操作：


注意这些区域的位置。 第一个区域开始于 $$$0$ 和结束 $$$\ frac {1} {4}$ 。 第二个区域以 $$$\ frac {1} {4}$ 并以 $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ 。 更一般地，如果概率相等 $$$p_0，p_1，...，p_ {n-1}$ ，那么面积将是间隔 $$$[0，p_0）$ ， $$$[p_0，p_0 + p_1）$ ， $$$[p_0 + p_1，p_0 + p_1 + p_2）$ 等 那是区域 $$$我$ 受间隔限制

$$ $$[\ sum_ {j = 0} ^ {i-1} {p_j}，\ sum_ {j = 0} ^ {i} {p_j}）$$

请注意，这两个值之间的差异是 $$$p_i$ ，即该区域的总面积为 $$$p_i$ 根据需要。

现在我们知道了这些区域在哪里。 如果我们要选择均匀分布的随机值 $$$x$ 在范围内 $$$[0，1）$ ，那么我们如何确定它落在哪个间隔？ 如果使用非对称硬币算法作为起点，则思路如下：从第一个区域的终点开始，不断向上移动所有区域，直到找到一个其值大于该值的终点。 $$$x$ 。 如果这样做，我们将找到包含该点的第一个区域 $$$x$ ，因此也是我们的价值。 例如，如果我们选择一个随机值 $$$x = \ frac {27} {40}$ ，然后执行以下搜索：


从中我们可以得出结论，构面3由于从头开始索引而下降了。

这样的线性扫描算法将为我们提供时间算法 $$$O（n）$ 查找骨骼的弹出边缘。 但是，通过使用以下观察结果，我们可以显着改善其执行时间：一系列区域的端点形成一个递增的序列（因为我们总是添加越来越多的概率，所有概率都不能小于零）。 因此，我们要回答以下问题：值的顺序增加并且带有一些检查点，我们需要找到严格大于检查点的时间间隔中的第一个值。 这是使用二进制搜索的最佳时机！ 例如，这是在上面的数组上的一个二进制搜索，以查找它所属的区域 $$$x = \ frac {39} {40}$ ：


随着时间的推移，这为我们提供了一种算法。 $$$\ Theta（\ log n）$ 在区间中绑定均匀分布的随机值 $$$[0，1）$ 到一块废弃骨头的边缘。 此外，预处理时间足以构建端点表 $$$\ Theta（n）$ ; 我们只是在上移时简单地计算部分概率之和。

该算法有时称为轮盘赌选择算法，因为它使用类似于轮盘赌的技术选择随机区域-将球丢入一个区间并观察其停止位置。 在伪代码中，算法如下所示：

算法：轮盘选择

• 初始化 ：
  
  1. 选择一个阵列 $$大小 $$$n$
  2. 我们设定 $$$A [0] = p_0$ 。
  3. 尽一切可能 $$$我$ 来自 $$$1$ 之前 $$$n-1$ ：
     
     1. 我们设定 $$$A [i] = A [i-1] + p_i$
  
  
• 代 ：
  
  1. 生成均匀分布的随机值 $$$x$ 在范围内 $$$[0，1）$
  2. 使用二进制搜索，我们找到索引 $$$我$ 最小元素 $$哪个少 $$$x$ 。
  3. 回程 $$$我$ 。

此算法与先前给出的算法之间的比较看起来非常令人印象深刻：

演算法	初始化时间		产生时间		忙碌的记忆
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$
不对称硬币的舒勒骨头	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$	$$$\ Theta（n）$
轮盘赌轮选择	$$$\ Theta（n）$		$$$\ Theta（\ log n）$		$$$\ Theta（n）$

显然，我们现在有一个比原始算法更好的算法。 乍一看，概率自由裁量权似乎很有希望，但是这种基于连续值和二元搜索的新方法看起来要好得多。 但是，仍然可以通过巧妙地使用一组混合技术来改善这些指标，我们将在下面进行讨论。

该算法一个有趣的细节是，尽管使用二进制搜索可以保证生成随机数的最坏情况 $$$O（\ log n）$ ，它也不允许更快的搜索； 也就是说，生成时间也将相等 $$$\欧米茄（\ log n）$ 。 可以改善吗？ 事实证明您可以。

假设我们从对累积概率列表的二分搜索转变为使用二分搜索树 。 例如，有了上面给出的概率集，我们可以为它们的累积分布构造以下二进制搜索树：


现在，如果我们要模拟一卷骨头，我们可以在区间中生成一个均匀分布的数 $$$[0，1）$ 然后查看该二进制搜索树（BST）中的间隔。 由于这是平衡的二叉搜索树，因此最佳搜索时间为 $$$O（1）$ 和最坏的 $$$O（\ log n）$ 。

但是，假设我们对概率分布了解更多，我们可以做得更好。 例如，假设我们的概率相等 $$$\ frac {99} {100}$ ， $$$\ frac {1} {600}$ ， $$$\ frac {1} {600}$ ， $$$\ frac {1} {600}$ ， $$$\ frac {1} {600}$ ， $$$\ frac {1} {600}$ ， $$$\ frac {1} {600}$ 。 也就是说，概率分布极度倾斜，几乎所有概率集中在一张面上。 我们可以为这些概率建立平衡的BST：


尽管此二叉搜索树是完美平衡的，但它并不非常适合我们的任务。 由于我们知道在100种情况中有99种情况下，随机值将在 $$$[0，\ frac {99} {100}）$ ，那么就没有必要为该间隔存储节点了。 实际上，这意味着几乎所有时候我们都会对蓝色和黄色区域进行两个不必要的比较。 由于我们极有可能率先检查最大间隔，因此不合理地平衡树以使平均情况由于剩余的情况而变得更好是合乎逻辑的。 如图所示：


现在，我们很可能会在第一次尝试后立即找到所需的区域来完成搜索。 在极不可能的情况下，所需的区域位于剩余区域中 $$$（\ frac {99} {100}，1]$ 我们平静地走到那棵树的尽头，那棵树实际上很平衡。

我们想以广义的形式解决以下问题：

给定给定的概率集，请为这些概率找到一个二叉搜索树，该树将期望的搜索时间最小化。

幸运的是，这个问题已经得到了很好的研究，被称为最优二叉搜索树问题 。 有很多算法可以解决这个问题。 已知可以及时找到确切的解决方案 $$$O（n ^ 2）$ 使用动态编程 ，并且有很好的线性时间算法可以找到近似解。 另外，要获得最佳解的恒定因子，可以使用展开树数据结构（扩展树） （自平衡二进制搜索树）。

有趣的是，这种优化的二叉搜索树的行为的最佳情况发生在概率分布极度偏斜时，因为我们可以简单地将包含绝大多数概率质量的节点移到树的根部，而最坏的情况是当分布平衡时，因为这时树应该宽和浅。 这与先前算法的行为相反，在先前算法中，诚实的算法被用来模拟作弊的骨骼！

在最好的情况下，我们有一个作弊的骨骼，其中一个面总是掉出（也就是说，它的概率为1，而其他所有面的概率为0）。 这是我们先前示例的极端夸张，但是在这种情况下，搜索将始终在第一次尝试后结束。 在最坏的情况下，所有概率都是相等的，我们得到了标准的BST搜索。 我们得出以下几点：

演算法	初始化时间		产生时间		忙碌的记忆
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$
不对称硬币的舒勒骨头	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$	$$$\ Theta（n）$
轮盘赌轮选择	$$$\ Theta（n）$		$$$\ Theta（\ log n）$		$$$\ Theta（n）$
最佳轮盘选择	$$$O（n ^ 2）$		$$$\ Theta（1）$	$$$O（\ log n）$	$$$\ Theta（n）$

飞镖投掷

到目前为止，我们一直在考虑两个可帮助我们构建用于模拟欺诈骨骼的算法的原语：诚实骨骼和非对称硬币。 仅使用诚实的骨头，我们得出了一种（欺骗，不切实际的）欺骗骨头的算法，并且从不对称硬币开始，我们能够发明出一种快速的欺骗骨头的算法。 可以将这两种方法结合起来以创建基于诚实骨头和不对称硬币的算法吗？ 事实证明，是的，并且实际上所产生的算法比这两种方法都更好。

在此之前，我们将间隔时间可视化 $$$[0，1）$ 和一维间隔的骨面概率。 这两种算法都选择间隔中的某个点 $$$[0，1）$ 并将其放在直线段上，其长度对应某种概率。 我们创建的细分越长，选择此细分的可能性就越大。 但是，如果您尝试不是一维而是二维地思考怎么办？ 如果我们冒概率怎么办 $$$p_i$ 不是直线段的长度，而是矩形的面积？

让我们从返回上一个带有概率的示例开始 $$$\ frac {1} {2}$ ， $$$\ frac {1} {3}$ ， $$$\ frac {1} {12}$ ， $$$\ frac {1} {12}$ 。 我们用宽度为矩形的形式表示这些概率 $$$w$ （有些随意 $$$w> 0$ ）和高度 $$$p_i$ （因此，矩形的面积将等于 $$$w \ cdot p_i$ ）：


请注意，这些矩形的总面积为 $$$w$ 自该地区

$$ $$\ sum_ {i = 0} ^ {n-1} {w p_i} = w \ sum_ {i = 0} ^ {n-1} {p_i} = w$$

现在假设我们围绕这些宽度为 $$$4w$ （因为有四个四边形），并且高度为 $$$\ frac {1} {2}$ （因为最高的矩形的高度 $$$\ frac {1} {2}$ ）：


我们可以想象这个矩形分为五个区域-四个区域对应不同的概率，一个区域指示未使用的空间。 休息一下，我们可以将随机掷骰子模拟算法视为飞镖游戏。 假设我们向这个目标投掷了（完全均匀分布的）飞镖。 如果落入未使用的空间，则我们将飞镖取出并再次扔出，重复此过程，直到进入一个矩形中。 由于概率越大，矩形越大，则抛出骨头的边缘的可能性越大，落入其矩形的可能性就越大。 实际上，如果我们设置已经落入某种矩形的条件，则会得到以下结果：

$$ $$\ mathbb {P} [\ mbox {在第i边击中矩形} | \ mbox {命中某个矩形}] = \ frac {\ mbox {i的矩形区域}} {\ mbox {总矩形区域}} = \ frac {w p_i} {w} = p_i$$

换句话说，当我们最终用均匀分布的飞镖落入某种矩形时，我们选择面矩形 $$$我$ 骗子骨头的可能性 $$$p_i$ ，也就是说，有我们需要的可能性！ 也就是说，如果我们找到某种有效的方法来模拟在该矩形上投掷随机飞镖，那么我们将有一种有效的方法来模拟投掷随机骰子。

模拟在此矩形上投掷飞镖的一种方法是在间隔中选择两个均匀分布的值 $$$[0，1）$ 将它们缩放到适当的宽度和高度，然后检查飞镖下面的区域。 但是，这会导致与尝试确定随机值所在的一维区域时遇到的问题相同的问题。 但是，确实有一系列精彩的观察，因此，确定影响的位置可能是一个简单的任务，即使不是不重要的任务。

初步观察：由于所有矩形的宽度相等，因此可以任意选择这些矩形的宽度。 当然，高度取决于骨头表面的概率。 但是，如果我们按某个正实数平均缩放所有高度 $$$h$ ，则所有矩形的相对面积将相同。 实际上，对于任何正实数 $$$h$ 按比例缩放高度后所有矩形的总面积 $$$h$ 计算为

$$ $$\ sum_ {i = 0} ^ {n-1} {w h p_i} = w h \ sum_ {i = 0} ^ {n-1} {p_i} = w h$$

现在，我们将考虑选择任何单个矩形的可能性，从而将自己限制在一定要碰到某种矩形的条件下。 使用相同的计算，我们得到以下结果：

$$ $$\ mathbb {P} [\ mbox {在第i边击中矩形} | \ mbox {命中某个矩形}] = \ frac {\ mbox {i的矩形区域}} {\ mbox {总矩形区域}} = \ frac {w h p_i} {w h} = p_i$$

也就是说，实际上，如果我们线性且均匀地缩放它们，则选择任何单个矩形的可能性不会改变。

由于我们可以选择任何合适的缩放比例，为什么不缩放这些矩形，以使边框的高度始终为1？ 由于边界框的高度由最大值确定 $$$p_i$ 输入概率，那么我们可以先将每个矩形缩放一个因子 $$$\ frac {1} {p_ {max}}$ 在哪里 $$$p_ {max}$ 是所有输入概率的最大概率。 因此，我们得到了矩形1的高度。类似地，由于我们可以为矩形选择任意宽度，因此我们取宽度1。这意味着对于 $$$n$ 边框总宽度的概率为 $$$n$ ，总高度为1。如图所示：


现在，我们准备考虑如何将随机飞镖扔到矩形中并确定它掉进了什么。 最重要的是，我们可以分割矩形，使其不由几个较小的矩形和形状奇怪的空白组成。 相反，该区域被切成一组 $$$2n$ 矩形，每个矩形两个 $$$n$ 输入概率。 如图所示：


注意此矩形的形成方式。 对于作弊者骨骼的每个面，我们有一个宽度为1且高度为1的列，分为两个空格-一个半空格``是''（对应于此大小的矩形）和一个半空格``否''（对应于该列的其余部分）。

现在让我们考虑如何扔飞镖。 投掷到此矩形中的完美均匀的飞镖将具有以下成分 $$$x$ 和 $$$y$ 。 这里组件 $$$x$ 应该在间隔内 $$$[0，1）$ ，对应于飞镖击中哪一列。 组成部分 $$$y$ 应该在间隔内 $$$[0，1）$ ，对应于我们在该栏中的高度。 元件选择 $$$x$ 影响我们正在考虑的作弊者骨骼的哪一面，以及成分的选择 $$$y$ 对应于我们是否选择了这个方面。 但是，等等-我们已经知道了这两个想法！ 座标选择 $$$x$ 对应于列，类似于抛出诚实的骨头来决定列的选择。 座标选择 $$$y$ 对应于非对称硬币的投掷，以确定是选择面孔还是再次抛掷！ 这种观察非常重要，以至于我们绝对可以理解：

在此间隔中选择随机点类似于扔出诚实的骨头并扔掉不对称的硬币。

实际上，可以将这个结果视为更强大的机会。 为了模拟作弊的骨骼，我们构建了一组不对称硬币，每个骨骼的每个面都一个，然后滚动一个诚实的骨骼来确定要扔哪个硬币。 , , , , .

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ 。 , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ 。
  2. $$$Coins$ $$$n$ , «» .
  3. $$$我$ 来自 $$$0$ 之前 $$$n - 1$ ：
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$我$ $$$[0, n)$ 。
     2. , $$$Coins[i]$ 。
     3. , $$$我$ 。

. $$$O（n）$ , $$$O（n）$ $$$Coins$ , $$$O（n）$ 。 , $$$O(1)$ 。 ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$我$ $$$\frac{p_i}{p_{max}}$ , -

$$ $$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ 。 ? $$$p_{max}$ 。 $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . 如果 $$$p_{max} = \frac{1}{n}$ , 1. . 如果 $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ 。 , «» $$$\frac{1}{n \cdot p_{max}}$ 。 , , «», $$$p_{max}$ 。 , , .

:

演算法
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ ， $$$\frac{1}{3}$ ， $$$\frac{1}{12}$ ， $$$\frac{1}{12}$ 。 , $$$\frac{1}{4}$ 。 , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ？ , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ 。 , :


, , $$$\frac{1}{2}$ 和 $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ？ , - , :


, , . , $$$\frac{1}{2}$ 和 $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ 。 $$$n$ 。 , alias , ( ). , . - - $$$我$ 。 $$$Prob[i]$ 。 , , $$$我$ , , $$$Alias[i]$ 。 alias :

别名表证明

现在我们需要正式证明创建表的能力 $$$别名$ 和 $$$概率$ 永远存在。 为了证明这始终是可能的，我们需要证明始终可以执行以下操作：

• 创建矩形 $$$（n \ cdot p_i）\乘以1$ 对于每个概率 $$$p_i$ ，
• 将它们水平切成小块，然后
• 分发给 $$$n$ 列
  
  • 这样每列的高度相等 $$$1$ ，
  • 没有列具有两个以上的矩形，并且
  • 脸部对应的矩形 $$$我$ 位于列中 $$$我$ 。

在继续证明这总是可能的之前，让我们看一个例子。 假设我们有四个概率 $$$\ frac {1} {2}$ ， $$$\ frac {1} {3}$ ， $$$\ frac {1} {12}$ ， $$$\ frac {1} {12}$ 。 这是一组四个概率（ $$$k = n = 4$ ），其总和等于 $$$1 = \ frac {4} {4}$ 。 尽管我们通过实验显示了如何填充上面的别名表，但是现在让我们更详细地看一下它的创建，并从一个完全空的表开始，然后开始填充它。 我们首先将所有这些概率缩放4倍，从而得出这样的概率和这样一个空表：


请注意，我们需要分配四个矩形中的两个（ $$$\ frac {1} {3}$ ， $$$\ frac {1} {3}$ ）小于1。这表示他们将无法完全填充该列，而无法填充其余的列，我们需要其他概率。 让我们采用两者之一（假设为黄色）并将其放置在相应的列中：


现在我们需要以某种方式覆盖该列顶部的差异。 为此，我们注意到两个尚未分布的矩形的高度都大于1（即 $$$2$ 和 $$$\ frac {4} {3}$ ） 让我们随机选择其中之一； 随它去吧 $$$\ frac {4} {3}$ 。 然后，我们将分配足够的 $$$\ frac {4} {3}$ 在专栏中填满； 结果我们参与 $$$\ frac {2} {3}$ 来自 $$$\ frac {4} {3}$ 如下图所示：


现在，让我们看看我们的电路是什么样的。 我们有三个矩形，其总面积为 $$$3$ ，以及三个空闲列，也就是说，看起来您可以在这三个列中分布这些矩形。 为此，我们将使用与以前相同的技巧。 请注意，至少有一个矩形，其高度小于 $$$1$ ，因此我们将以任意方式选择一个（例如，矩形 $$$\ frac {2} {3}$ ）并将其放在您的列中：


现在我们需要将该列填充到末尾，因此我们可以选择不小于1的概率，并用它来补充该列的其余部分。 在这里，我们只有一个选择（使用 $$$2$ ）， $$$\ frac {1} {3}$ 来自 $$$2$ 并放在该列的顶部：


现在它归结为两个矩形，其总面积为两个。 我们重复此过程，找到一些高度不大于1的矩形（这里是 $$$\ frac {1} {3}$ ），并将其放在此列中：


现在我们会发现一些不小于 $$$1$ 补充专栏。 我们唯一的选择是 $$$\ frac {5} {3}$ ：


现在我们只剩下一个矩形，它的面积是1。因此，我们可以简单地通过将矩形放在其自己的列中来完成创建：


瞧！ 我们填写了表格。

请注意，此表的设计基于通用模式：

• 我们找到一些高度不大于1的矩形，并将其放在自己的列中，在表格中进行设置 $$$概率$ 此矩形的高度。
• 我们找到一些高度不小于1的矩形，我们用它来填充列，并在表中进行设置 $$$别名$ 匹配此矩形代表的骨骼的面。

是否有可能证明这种构造在一般情况下总是可行的？ 也就是说，我们不是因为这样分配概率而“陷入困境”吗？ 幸运的是，有证据。 可以解释如下：我们缩放了所有概率，以使新概率的平均值等于1（因为最初它等于 $$$\ frac {1} {n}$ ，然后我们将所有内容乘以 $$$n$ ） 我们知道，所有标度概率的最小值不应大于平均值，并且所有标度概率的最大值不应小于平均值，因此，当我们从此处开始时，我们应始终至少有一个不大于1的元素（即所有定标概率中的最小者）和至少1个元素（即，最大定标概率）。 因此，我们可以将这些元素配对。 但是，如果我们将它们都删除，该怎么办？ 结果，当我们这样做时，我们从总数中删除了一个概率，并将缩放后的概率的总和减小了一个。 这意味着新的平均值未更改，因为平均缩放概率相等。 我们可以一遍又一遍地重复此过程，直到最终将所有元素配对。

我们可以按照以下定理将这个论证形式化：

定理：如果有的话 $$$k$ 单位宽度和高度的矩形 $$$h_0$ ， $$$h_1$ ，...， $$$h_ {k-1}$ 这样 $$$\ sum_ {i = 0} ^ {k-1} {h_i} = k$ ，总有一种方法可以分离矩形并将它们分布在 $$$k$ 列，每个列的高度为1，因此每列将包含不超过两个不同的矩形，并且 $$$我$ 此栏至少包含一部分 $$$我$ 矩形。

证明：通过归纳法。 在基本情况下，如果 $$$k = 1$ ，那么我们只有一个矩形，其高度应等于1。因此，我们可以将其放入 $$$0$ 第列。 因此，每列的高度为1，最多包含两个矩形， $$$0$ -第一栏至少包含一部分 $$$0$ 矩形。

对于归纳阶段，假设对于某些自然数 $$$k$ 该定理是有效的，并考虑任何 $$$k + 1$ 矩形宽 $$$1$ 和高度 $$$h_0$ ， $$$h_1$ ，...， $$$h_ {k}$ 这样 $$$\ sum_ {i = 0} ^ {k} {h_i} = k + 1$ 。 首先我们声称有一定的高度 $$$h_l$ 这样 $$$h_l \ le 1$ ，以及其他一些高度 $$$h_g$ （这样 $$$l \ ne$ ）这样 $$$h_g \ ge 1$ 。 为了验证这一点，让我们从相反的角度出发，并假设不存在这样的情况。 $$$h_l$ 与 $$$h_l \ le 1$ ; 这意味着 $$$h_i> 1$ 对于所有自然数 $$$我$ 在范围内 $$$0 \ le我\ le k$ 。 但是我们得到了 $$$k + 1 = \ sum_ {i = 0} ^ k {h_i}> \ sum_ {i = 0} ^ k {1} = k + 1$ 这显然是不可能的。 因此，存在某种索引 $$$l$ 这样 $$$h_l \ le 1$ 。 再一次，让我们从相反的角度出发，并假设没有其他高度 $$$h_g$ （与 $$$l \ ne$ ）这样 $$$h_g \ ge 1$ 。 然后事实证明彼此 $$$h_g <1$ ，即（通过类似的逻辑） $$$\ sum_ {i = 0} ^ {k} {h_i} <k + 1$ 而且我们已经矛盾了。 因此 $$$h_l \ le 1$ 和 $$$h_g \ ge 1$ 。

现在考虑以下构造。 放 $$$h_l$ 在列中 $$$l$ 并填充剩余的空间 $$$1-h_l$ 在 $$$l$ 该列是矩形的一部分 $$$h_g$ （因为 $$$0 \ le 1-h_l \ le 1$ 和 $$$h_g \ ge 1$ ） 因此，我们将完全填充该列。 现在我们有一套 $$$k$ 总数量等于的矩形的不同部分 $$$k$ ，因为我们从矩形中删除了总面积 $$$1$ ，最初的总数是 $$$k + 1$ 。 而且，我们完全填满了专栏 $$$l$ ，也就是说，我们不再需要在此处放置矩形的其他部分。 因此，通过归纳假设，我们可以分配剩余的 $$$k$ 在 $$$k$ 列，以便满足上述条件。 结合我们现在已经填写了这一列的事实 $$$l$ ，这意味着我们有一种方法可以填充所有列，使其符合约束条件。 这样就完成了归纳。

这证明了构造可能性，它表明我们不仅可以始终构建别名表，而且上述查找不超过一个高度并将其与高度至少为一个的矩形配对的算法始终是成功的。 由此，我们可以开始推导出越来越复杂的别名表计算算法。

别名表生成

使用上面的方法，我们可以得到一个很好的算法，可以使用别名方法来模拟欺骗骨骼的行为。 初始化包括重复扫描传入的概率以找到不大于1的值和至少1的值，然后将它们成对组合以填充列：

算法：朴素的别名方法

• 初始化 ：
  
  1. 乘以每个概率 $$$p_i$ 在 $$$n$ 。
  2. 创建数组 $$$别名$ 和 $$$概率$ 每个都有一个大小 $$$n$ 。
  3. 对于 $$$j = 1 \ mbox {to} n-1$ ：
     
     1. 找到概率 $$$p_l$ 满足条件 $$$p_l \ le 1$ 。
     2. 找到概率 $$$p_g$ （与 $$$l \ ne$ ）满足条件 $$$p_g \ ge 1$
     3. 我们设定 $$$概率[l] = p_l$ 。
     4. 我们设定 $$$别名[l] = g$ 。
     5. 删掉 $$$p_l$ 从初始概率列表中。
     6. 我们设定 $$$p_g：= p_g-（1-p_l）$ 。
     
     
  4. 让 $$$我$ 将是最后剩余的概率，其高度应为1。
  5. 我们设定 $$$概率[i] = 1$ 。
  
  
• 代 ：
  
  1. 我们从 $$$n$ 脸骨 叫脸 $$$我$ 。
  2. 投掷不对称硬币而被鹰击中 $$$概率[i]$ 。
  3. 如果鹰落在硬币上，请返回 $$$我$ 。
  4. 否则返回 $$$别名[i]$ 。

生成此算法的步骤与上述方法完全相同，并且需要时间 $$$\ Theta（1）$ 。 初始化步骤需要上述多次迭代。 首先，我们需要花时间 $$$\ Theta（n）$ 通过将每个概率缩放一个因子 $$$n$ 花时间 $$$O（n）$ 分配两个数组。 内循环正在运行 $$$\ Theta（n）$ 时间，并在每次迭代中完成工作 $$$O（n）$ 通过扫描数组，删除数组的元素之一并更新概率。 它给我们时间 $$$O（n ^ 2）$ 一般初始化。 如果我们在上下文中考虑此算法，则可以得到以下信息：

演算法	初始化时间		产生时间		忙碌的记忆
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$
不对称硬币的舒勒骨头	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$	$$$\ Theta（n）$
轮盘赌轮选择	$$$\ Theta（n）$		$$$\ Theta（\ log n）$		$$$\ Theta（n）$
最佳轮盘选择	$$$O（n ^ 2）$		$$$\ Theta（1）$	$$$O（\ log n）$	$$$\ Theta（n）$
诚信骨/非对称硬币	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$ （预期）	$$$\ Theta（n）$
天真的别名方法	$$$O（n ^ 2）$		$$$\ Theta（1）$		$$$\ Theta（n）$

与其他有效的模拟方法相比，这种幼稚的别名方法具有较高的初始化成本，但是可以非常有效地模拟骨骼滚动。 如果我们能够以某种方式降低初始化成本（例如， $$$O（n）$ ），那么此方法肯定会比此处使用的所有技术都要好。

降低初始化成本的一种简单方法是使用更合适的数据结构在执行期间保持高度。 在朴素的版本中，我们使用未排序的数组来存储所有概率，也就是说，找到两个必要概率需要时间 $$$O（n）$ 。 用于存储值的更合适的替代方法是平衡的二进制搜索树。 在这种情况下，我们可以找到值 $$$p_g$ 和 $$$p_l$ 及时地 $$$O（\ log n）$ 通过搜索树的最大值和最小值。 删掉 $$$p_l$ 可以及时完成 $$$O（\ log n）$ 和概率更新 $$$p_g$ 也可以在 $$$O（\ log n）$ 由于它很容易从树中移除并随后重新插入。 这为我们提供了以下算法：

算法：别名方法

• 初始化 ：
  
  1. 创建数组 $$$别名$ 和 $$$概率$ 每个大小 $$$n$ 。
  2. 创建一个平衡的二进制搜索树 $$$T$ 。
  3. 插入 $$$n \ cdot p_i$ 在 $$$T$ 千方百计 $$$我$ 。
  4. 对于 $$$j = 1 \ mbox {to} n-1$ ：
     
     1. 查找并删除其中的最小值 $$$T$ ; 叫他 $$$p_l$ 。
     2. 查找并删除其中的最大值 $$$T$ ; 叫他 $$$p_g$ 。
     3. 我们设定 $$$概率[l] = p_l$ 。
     4. 我们设定 $$$别名[l] = g$ 。
     5. 我们设定 $$$p_g：= p_g-（1-p_l）$ 。
     6. 新增 $$$p_g$ 到 $$$T$ 。
     
     
  5. 让 $$$我$ 将是最后剩余的概率，其权重应为1。
  6. 我们设定 $$$概率[i] = 1$ 。
  
  
• 代 ：
  
  1. 我们从 $$$n$ 脸骨 叫脸 $$$我$ 。
  2. 我们投掷不对称硬币，老鹰很有可能掉在上面 $$$概率[i]$ 。
  3. 如果鹰落在硬币上，请返回 $$$我$ 。
  4. 否则返回 $$$别名[i]$ 。

现在我们算法的初始化要快得多。 创作 $$$别名$ 和 $$$概率$ 还需要时间 $$$O（n）$ 在每个表上，并向BST添加概率 $$$T$ 需要时间 $$$\ Theta（n \ log n）$ 。 接下来我们执行 $$$\ Theta（n）$ 迭代以填充表，每个表都花费时间 $$$O（\ log n）$ 。 这给了我们总的初始化时间。 $$$O（n \ log n）$ ：

演算法	初始化时间		产生时间		忙碌的记忆
	最好的	最坏的	最好的	最坏的	最好的	最坏的
诚信骨共享骨	$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$	$$$\ Theta（1）$		$$$\ Theta（n）$	$$$O（\ prod_ {i = 0} ^ n {d_i}）$
不对称硬币的舒勒骨头	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$	$$$\ Theta（n）$
轮盘赌轮选择	$$$\ Theta（n）$		$$$\ Theta（\ log n）$		$$$\ Theta（n）$
最佳轮盘选择	$$$O（n ^ 2）$		$$$\ Theta（1）$	$$$O（\ log n）$	$$$\ Theta（n）$
诚信骨/非对称硬币	$$$\ Theta（n）$		$$$\ Theta（1）$	$$$\ Theta（n）$ （预期）	$$$\ Theta（n）$
天真的别名方法	$$$O（n ^ 2）$		$$$\ Theta（1）$		$$$\ Theta（n）$
别名方法	$$$O（n \ log n）$		$$$\ Theta（1）$		$$$\ Theta（n）$

但是，有一种算法可以更快地工作。 它非常简单，并且可能是实现别名方法的最简洁的算法。 该算法首先在Michael Woes的“用于生成具有给定分布的随机数的线性算法”一文中进行了描述，并成为实现别名方法的标准算法。

Woese算法基于两个工作列表的使用：一个包含高度小于1的元素，另一个包含高度至少为1的元素。该算法不断将每个工作列表的第一个元素成对耦合。 在每次迭代中，我们消耗“较小”值列表中的一个元素，并将该元素的其余部分从“较大”值列表中移到“较小”值的列表中。 该算法使用几个不变式：

• 小型工作清单中的所有项目均小于1。
• “大型”工作清单的所有元素至少为1。
• 工作清单中的项目总和始终等于项目总数。

为简化起见，每个列表都不存储概率本身，而是指向初始概率列表的特定指针，该指针指示链接指向欺骗骨骼的哪一面。 有了这些不变式，我们获得以下算法：

算法：（不稳定）Woe Alias方法

警告：此算法存在数值误差。 下面提供了一种数值上更稳定的算法。

• 初始化 ：
  
  1. 创建数组 $$$别名$ 和 $$$概率$ 每个大小 $$$n$ 。
  2. 创建两个工作清单 $$$小$ 和 $$$大$ 。
  3. 将每个概率乘以 $$$n$ 。
  4. 对于每个缩放的概率 $$$p_i$ ：
     
     1. 如果 $$$p_i <1$ 加 $$$我$ 到 $$$小$ 。
     2. 否则（ $$$p_i \ ge 1$ ）添加 $$$我$ 到 $$$大$ 。
     
     
  5. 再见清单 $$$小$ 不为空：
     
     1. 从中删除第一项 $$$小$ ; 叫他 $$$l$ 。
     2. 从中删除第一项 $$$大$ ; 叫他 $$$g$ 。
     3. 我们设定 $$$概率[l] = p_l$ 。
     4. 我们设定 $$$别名[l] = g$ 。
     5. 我们设定 $$$p_g：= p_g-（1-p_l）$ 。
     6. 如果 $$$p_g <1$ 加 $$$g$ 在 $$$小$ 。
     7. 否则（$ p_g \ ge 1 $）我们添加 $$$g$ 在 $$$大$ 。
     
     
  6. 再见清单 $$$大$ 不为空：
     
     1. 从中删除第一项 $$$大$ ; 叫他 $$$g$ 。
     2. 我们设定 $$$概率[g] = 1$ 。
     
     
  
  
• 代 ：
  
  1. 我们从 $$$n$ 脸骨 叫脸 $$$我$ 。
  2. 我们投掷不对称硬币，老鹰很有可能掉在上面 $$$概率[i]$ 。
  3. 如果鹰落在硬币上，请返回 $$$我$ 。
  4. 否则返回 $$$别名[i]$ 。

鉴于以上介绍的三个不变量，算法的第一部分（除最后一个循环外的所有内容）应该非常清楚：我们不断地将来自 $$$小$ 从大元素 $$$大$ ，然后将大项目的其余部分添加到相应的工作清单中。 该算法的最后一个周期需要说明。 用尽列表中的所有元素之后 $$$小$ 在列表中 $$$大$ 至少保留一个元素（因为每个元素都是 $$$小$ ，则元素的总和应小于剩余元素的数量，这违反了最后一个不变式的条件）。 自从每个elmenrt $$$大$ 不小于1，且金额 $$$k$ 中的项目 $$$大$ 应该相等 $$$k$ 然后每个元素 $$$大$ 必须等于1，否则总数将太大。 因此，最后一个周期将每个大元素的概率设置为1，以使包含该大元素的所有列均等于1。

在此算法中，工作清单的类型并不重要。 在Woof的原始文章中，栈被用作工作列表，因为可以使用数组有效地实现栈，但是如果需要，可以使用队列。 但是，为简单起见，我们将使用堆栈。

在继续分析算法之前，让我们使用一个示例分析其操作。 考虑一个使用七个概率的示例 $$$\ frac {1} {4}$ ， $$$\ frac {1} {5}$ ， $$$\ frac {1} {8}$ ， $$$\ frac {1} {8}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {10}$ 。 为了强调该算法不对概率进行排序并且不需要对其进行排序的事实，让我们以随机顺序排列它们 $$$\ frac {1} {8}$ ， $$$\ frac {1} {5}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {4}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {10}$ ， $$$\ frac {1} {8}$ 。 该算法首先将这些元素添加到两个工作堆栈中：


现在我们将放置栈顶 $$$小$ 通过将紫色矩形移动到最终位置来保持其位置：


现在我们使用栈顶 $$$大$ （绿松石矩形）填充其余的列。 由于 $$$\ frac {7} {4}-\ frac {1} {8} = \ frac {13} {8} \ ge 1$ 我们把绿松石块放在栈顶 $$$大$ ：


然后，我们重复此过程。 从堆栈顶部移动矩形 $$$小$ 在其列中，然后补充缺少的堆栈顶部 $$$大$ ：


再一次：


下次再次重复此过程时，我们发现尽管可以使用绿松石块填充表中的空白空间，结果绿松石块的高度将小于1。 因此，我们需要将绿松石块移动到小值堆栈的顶部：


现在在处理列表时 $$$小$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$n$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ ）
2. , , . , , $$$Large$ , $$$Small$ 。

, $$$Small$ $$$Large$ 。 , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ 。 -, , $$$1$ , , $$$1$ 。 , . :

: Alias-

• :
  
  1. $$$Alias$ 和 $$$Prob$ , $$$n$ 。
  2. , $$$Small$ 和 $$$Large$ 。
  3. $$$n$ 。
  4. $$$p_i$ ：
     
     1. 如果 $$$p_i < 1$ , $$$我$ 在 $$$Small$ 。
     2. ( $$$p_i \ge 1$ ) $$$我$ 在 $$$Large$ 。
     
     
  5. $$$Small$ 和 $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ 。
     2. $$$Large$ ; $$$g$ 。
     3. $$$Prob[l] = p_l$ 。
     4. $$$Alias[l] = g$ 。
     5. $$$p_g := (p_g + p_l) - 1$ 。 ( . )
     6. 如果 $$$p_g < 1$ , $$$g$ 在 $$$Small$ 。
     7. ( $$$p_g \ge 1$ ) $$$g$ 在 $$$Large$ 。
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ 。
     2. $$$Prob[g] = 1$ 。
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ 。
     2. $$$Prob[l] = 1$。
     
     
  
  
• :
  
  1. $$$n$- ; $$$我$。
  2. , $$$Prob[i]$。
  3. , $$$我$。
  4. $$$Alias[i]$。

, — . $$$\Theta(n)$, . $$$\Theta(1)$, , . $$$O（n）$, () , . $$$O（n）$, $$$Large$和 $$$Small$$$$O（n）$. $$$\Theta(n)$, ( ) :

演算法
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !