使用最小的随机位数在范围内生成均匀随机整数。

Question

我需要使用难以获得的随机位生成在任意大范围内的无偏均匀分布整数，因此我希望平均使用尽可能少的随机位。

生成的数字应该在0到N-1之间，其中N是给定的范围。

我现在正在做的是：

1. 通过某种方式计算N中的位数B；在数学上，B = ceil(log(N)/log(2))。
2. 生成B个随机位。
3. 如果生成的随机位形成的整数小于N，则返回它们。否则，返回步骤2。

最好的情况是N是2的幂次方；那么你什么都不会拒绝。但最坏的情况是N是2的幂次方加1；在这种情况下，随着B的增长，你每次尝试都会趋近于拒绝概率为1/2。这让我觉得很浪费，所以我想知道是否有更好的算法可以平均使用更少的位。

例如，当生成的位数>= N时，如果我按预定义顺序排列位位置而不是拒绝它们，希望找到一个在范围内的这样的排列，并且只有在没有一个排列成功时才生成新的批次，那么结果是否均匀分布？

- Pedro Gimeno

---

知道以下信息会很有用：你需要多少个随机数？你感兴趣的N的范围是什么？可能允许的偏差程度是多少？1位的成本是多少？是否存在内存或运行时限制？ - Unlikus

你可能会在这里找到有用的答案：https://dev59.com/h2025IYBdhLWcg3wX03z - Mark Dickinson

注意，可以使用随机熵源来为生成器提供种子，该生成器使用各种技术生成比其熵更多的位。结果比伪随机更好，但比真正的随机差。许多操作系统提供对实现的访问。有关详细信息，请参见https://en.wikipedia.org/wiki//dev/random。 - btilly

Answer 1

这是一个基于 算术编码 的方法：

1. 从范围[0，N）开始

2. 生成随机位，并使用它们选择范围的上半部分或下半部分。例如：[0,5) => [5/2, 5)

3. 当整个范围适合一个整数步骤时，则停止并返回该整数。

注意，您必须使用分数。

使用此方法后，一旦范围变小到小于1，则必须使用另一位的概率始终≤50％，而且当您这样做时，只需使用一个位。所需的位数的预期最大值为 ceil(log(N))+1。

例如：[0,5) -> [0,5/2) -> [5/4, 10/4) => [15/8, 20/8) => [35/16,40/16)

我们在选择[15/8, 20/8)时运气不佳。另一个选择是[10/8, 15/8)，它被[1,2)覆盖。

然而，下一步解决了问题。因为2 <= 35/16 < 40/16 <= 3，所以2就是我们的答案。

- Matt Timmermans

---

你需要处理分数，但这些分数总是某个整数除以2的幂次方。而这个幂次方就是你生成的比特数。因此，只使用整数编写这个程序并不难。 - btilly

Answer 2

不，你的排列策略是有偏差的。想象一下你排列第一个和最后一个数字。现在你的数字更可能是奇数而不是偶数。我不能百分之百确定没有可以工作的排列策略，但我认为不会。

假设你需要多个随机数，你可以进行优化。

首先生成一个介于0和N^k-1之间的数字，并选择k使得N^k接近但小于二的幂次方。然后你可以从0到N中提取k个数字。 例如N = 17：你可以选择k=11 17^11 = 34271896307633 < 35184372088832 = 2^45

这种策略在N很大时不太可行，例如当N = 2^20+1时，你已经需要大约k为700,000。

- Unlikus