如何使用随机位来模拟公平的 26 面骰子？

Question

如何使用提供位（0 或 1）的随机数生成器来模拟公平的 26 面骰子？我想使用比特流来选择英文字母表中的字母，以便任何一个字母出现的几率与任何其他字母的几率相同（我知道真正的单词不是这样的，并且每个字母都有特定的频率分布）信，但在这里并不重要）。使用二进制 0/1 决策从 AZ 集中公平地挑选字母的最佳方法是什么？我可以想出几种将位映射到字母上的方法，但对我来说，它们不会有偏见并不明显。有已知的好方法吗？

Answer 1

如果您将自己限制在有限的位数，并且您的骰子有 26 个面，则该方法将始终存在偏差。您必须允许这样的可能性：您必须查看可能无限数量的位，以确保它是公正的。

一个简单的算法是在 0 和 2^n - 1 形式的下一个最大数字（本例中为 31）之间选择一个随机数。如果您随机选择的数字太大，请丢弃它并重新选择，直到获得范围内的数字。

显然，这不是最佳算法，因为您“浪费”了一些信息，但对于大多数用途来说它应该足够好了。如果骰子的面数刚好高于 2^m（对于某些 m），例如：33 面，则最为浪费。在这种情况下，几乎 50% 的情况下您将不得不丢弃该值。

Answer 2

这里的基本答案似乎是正确的 - 如果你的随机数 0..32 大于 25，则重新滚动。然而，您可以通过寻找 26 的倍数来叠加任意长结果的几率，这提供了较小的做多机会。

 32 -  26 =  6
 64 -  52 =  12
128 -  78 =  50

... 等等。我编写了一个 Python 脚本来计算出最多 32 位的最佳可用位数，并得到了这样的结果：

2^13 - 26 * 315 = 2
2^14 - 26 * 630 = 4

所以无论哪种方式，如果您使用 13 或 14 位，您都有 1 in 2^12 的机会重新滚动。在这种情况下，您的算法将是：

def random_character():
    r = 8190
    while r >= 8190:
        r = rand(13) # assuming rand generates an N bit integer
    return chr(r % 26 + ord('a'))

编辑：出于好奇，我将这些赔率与一些重要值进行了比较，以查看 13 是否确实是最佳数字（假设您可以在相同的情况下生成任意数量的位数，1 到 32）时间量 - 如果你不能，13 位看起来是最好的）。根据我（诚然是昏昏欲睡的）数学计算，如果你能像 16 位那样便宜地获得 32 位，那就选择它吧。否则，赞成13。

2^8 through 2^12: by definition, no better than 1/2^12 odds
2^16: diff is 16, so 1/2^11
2^17: diff is 6, so slightly under 1/2^14
2^18: diff is 12, so slightly under 1/2^12
2^19: diff is 24, so slightly under 1/2^14
2^20: diff is 22, so slightly under 1/2^15
2^21: diff is 18, so slightly under 1/2^16
2^22: diff is 10, so slightly under 1/2^18
2^23: diff is 20, so slightly under 1/2^18
2^24: diff is 14, so slightly under 1/2^20
2^25: diff is 2, so 1/2^24
2^26: diff is 4, so 1/2^24
2^27: diff is 8, so 1/2^24
2^28: diff is 16, so 1/2^24
2^29: diff is 6, so slightly under 1/2^26
2^30: diff is 12, so slightly under 1/2^26
2^31: diff is 24, so slightly under 1/2^26
2^32: diff is 22, so slightly under 1/2^27

Answer 3

对于您的情况，最简单的方法是抛出 5 位，这会给出 32 (0-31) 个等概率结果。如果你得到的值超出了你的范围（大于 25），你会再次尝试（再一次......）

在这种情况下，每个字母的平均“硬币”（位）数将是

 5 x 32 / 26  = 6.15

（作为参考，请参阅几何分布）

Answer 4

一个简单的实现是使用固定位数（例如，4 个字节来获取整数）来组合随机位以获得小数或整数值。将结果除以所提供位数的最大可能值，我认为这应该给你一个均匀分布在 0-1 范围内的小数。 （本质上是一个 rand() 函数）。然后执行 26*rand()

Answer 5

26 二进制为 11010。
如果超过 26，则生成 5 位：

1. 返回值 mod 26（将倾向于较低的值）
2. 丢弃结果并再次进行（有可能永远不会结束）

或概括它：
生成 (以 2 为底的 log n) + 1 位。如果它们超过 n，则返回值 mod n，或丢弃 &再去吧。