algorithm - 将随机范围从 0-2 缩小到 0-1

Question

随机生成器从列表中生成值：0、1、2（所有三个值的概率相等）。

如何从生成器的不超过十次使用中以相等的概率获得随机数 0 或 1。

标签： algorithmrandom

Answer 1

您的最终目标是仅在给定一个 3 面骰子的情况下，使用固定数量的 3 面骰子掷出一个 2 面骰子。

但是，无论您滚动多少次，这都是不可能的，因为 2 不能整除 3（并且两者都是素数）。您可以在这里做的最好的事情是继续拒绝 2（并且连续获得n 2 的概率是 1/3^ n，该概率随着n的增加而迅速缩小）。

更一般地说，不可能使用 p 面骰子使用固定数量的 p 面骰子来滚动k 面骰子，除非“每个素数除k也除p ”（参见“模拟骰子”中的引理 3用骰子“B. Kloeckner。

另请参阅以下问题：

• 将随机范围从 1-5 扩展到 1-7
• 均匀分布的随机数从一个范围到另一个范围的节俭转换
• 从 U(1,3) 生成 U(1,5) 的最佳方法？