返回资讯中心
外部精选
软件工程
#开发者实时流

系统编程中实用的概率法则:重试与期望值的误区

来源标题:Some Useful Probability Facts for Systems Programming (2020)

文章整理了系统编程中常用的概率经验法则,指出期望值只是平均值,不能保证结果。以游戏中1/10掉落率为例,玩家打10场并不必然获得道具,实际概率需通过计算得出。这些法则适用于操作系统、网络服务及游戏设计等场景。

Hacker News 最新tomcatfish2026/11/9 · 8 天前30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

概率问题在系统编程中经常出现,我这里用这个词是宽泛地指从操作系统编程和网络,到构建大型在线服务,再到创建游戏中的虚拟世界等一切领域。下面是一组粗略但实用的概率经验法则,它们彼此密切相关,在设计系统时有很多实际应用。

重试在系统编程中无处不在。例如,假设你在为一个角色扮演游戏设计世界。当某个森林里的怪物被击败时,它们有很小的几率掉落某种特殊物品。假设这个几率是 (\frac{1}{10})。基础概率告诉我们,玩家平均需要获胜 10 次才能获得一件特殊物品。但在概率论中,“期望值”只是一种平均值,并不能保证玩家即使赢了 10 场就一定能拿到物品。

玩家在 10 场战斗后至少获得一件特殊物品的几率是多少?我们不妨让计算机计算一下:在成功概率为 (\frac{1}{N}) 的情况下,尝试 (N) 次至少成功一次的概率,取一系列 (N) 值。

从图上直观来看,当 (N) 大于约 3 时,概率大致保持不变。事实上,它收敛于 (1 - e^{-1}),其中 (e) 是欧拉常数,2.718281828459……这个数(以及 (e^{-1}))在工程中极为常见,下面是一张实用数值表:

所以,如果你不需要精确答案(通常也不需要),你可以简单地说:如果掉落概率是 (\frac{1}{10}),大多数玩家会在 10 场战斗内获得特殊物品,但(差不多)有三分之一不会。

由于怪物战斗在统计上是独立的,我们可以粗略估计,大约每 9 个玩家中仍有 1 个在 20 场战斗后还没有特殊物品。另外,大约 60% 的玩家在 5 场战斗后还没有,因为 (0.6 \times 0.6 = 0.36),所以 60% 接近 36.7% 的平方根。

如果你有 (\frac{1}{N}) 的成功概率,那么尝试 (N) 次后你更有可能已经成功,但概率只有大约三分之二(或者你对 (1 - e^{-1}) 的最喜欢的近似值)。只要 (N) 至少为 3,(N) 的值对近似值影响不大。

证明如下:玩家在所有 (10) 场战斗后都没拿到特殊物品的几率是 ((\frac{9}{10})^{10} = .349),所以至少拿到一件的几率是 (1 - .349 = .651)。更一般地,至少成功一次的几率是 (1 - (1 - \frac{1}{N})^N),它收敛于 (1 - e^{-1})(根据 (e) 的某个定义)。

顺便说一句,这条规则对于桌游中的快速心算也很有用。假设玩家需要从掷 8 个六面骰中至少得到一个 6。失败的几率是多少?前 6 个骰子大约是 (\frac{1}{3}),剩下两个是 (\frac{5}{6} \times \frac{5}{6}),所以总共大约是 (\frac{1}{3} \times \frac{25}{36} \approx \frac{8}{36} \approx \frac{1}{4})。计算器给出的结果是 ((\frac{5}{6})^8 = .233),所以粗略近似对于游戏来说已经足够好了。

假设你随机地(独立地、一次一个)把 (N) 个球扔进 (N) 个桶里。平均而言,略多于三分之一((e^{-1}))的桶会是空的,略多于三分之一(又是 (e^{-1}))会恰好有一个球,剩下的约四分之一((1 - 2e^{-1}))会包含多个球。

球与桶的抽象模型有很多具体的工程应用。例如,假设你有一个负载均衡器,随机地将请求分配给 12 个后端。如果在某个时间窗口内来了 12 个请求,平均而言大约有 4 个后端会空闲,只有约 4 个会有均衡的单个请求负载,剩下的(平均)3 或 4 个会承受更高的负载。当然,这些都是平均值,实际中会有波动。

另一个例子,如果一个哈希表有 (N) 个槽位,那么如果你把 (N) 个不同的值放进去,大约三分之一的槽位仍然是空的,大约四分之一的槽位会有冲突。

如果一个在线服务平均每 20 天发生一次生产事故,那么(假设事故之间不相关)略多于三分之一的 20 天周期会完全平静,略多于三分之一会有“理想的”单次事故,而四分之一的 20 天周期会压力更大。在现实世界中,生产事故的聚集程度甚至更高,因为它们并不总是独立的。

这条经验法则也暗示了为什么水平扩展的数据库往往会有热分片和冷分片,以及为什么低业务量的企业(如咨询公司)会遭受客户需求“饥一顿饱一顿”模式的困扰。

随机分配比我们直觉预期的要不平衡得多。一个著名的例子来自二战:战争后期,德国向伦敦发射了数千枚 V-1 和 V-2 飞弹。从海峡对岸用火箭击中一座城市已经需要将 1940 年代的技术推向新极限,但几位英国分析师查看了炸弹损坏地图后得出结论,认为德国人不知何故在瞄准伦敦的特定区域,这意味着令人难以置信的技术进步水平。然而,在 1946 年,一位精算师做了恰当的统计分析,指出:不,炸弹损坏的聚集只是随机 chance 下你会预期到的结果。(该分析基于泊松分布,而 (N) 个球和 (N) 个桶的规则中的比率可以通过 (\lambda = \frac{N}{N} = 1) 的泊松分布计算出来。)

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →