如何用抛硬币生成0到N范围内随机数及所需抛投次数计算

我们通常用拒绝采样法实现这类高效随机数生成，计算逻辑如下：

算法核心流程 #

• 先计算最小正整数k，满足2^k ≥ N+1，即k = ⌈log₂(N+1)⌉，等价于N+1的二进制位长度
• 单次尝试操作：连续抛k次硬币，正面记为1、反面记为0，拼接得到k位二进制数x，取值范围为0 ≤ x ≤ 2^k - 1
• 结果判定：如果x ≤ N，直接返回x作为最终随机数R；如果x > N，丢弃本次结果，重复上述单次尝试操作，直到得到符合要求的x

期望抛硬币次数推导 #

• 单次尝试成功的概率p = (N+1)/2^k，因为k是满足条件的最小值，因此p≥0.5
• 期望尝试次数为几何分布期望：1/p = 2^k/(N+1)
• 最终期望抛硬币总次数 = 单次尝试抛硬币次数 × 期望尝试次数 = ⌈log₂(N+1)⌉ * 2^⌈log₂(N+1)⌉ / (N+1)

常见场景示例 #

• 当N = 2^m -1（即N+1是2的整数次幂）时，2^k = N+1，p=1无需重试，期望抛硬币次数就是k = log₂(N+1)，和信息论下界完全一致
• 当N=5时，N+1=6，k=3，p=6/8=0.75，期望抛硬币次数为3 * 8/6 = 4次

内容的提问来源于stack exchange，提问作者Krisi3