Combinatorial Bernoulli Factories with Polynomially Many Coins
1. 一句话总结 论文提出了一种统一的组合 Bernoulli 工厂算法,可将未知偏置硬币精确转换为仿射切片多面体的随机顶点,在保持 \(\mathbb E[V]=x\) 的同时…
标题
连硬币概率未知,也能组合出精准随机结果
🪙 这篇论文解决了一个反常识问题:每枚硬币的正面概率可能不同,甚至连这个概率都不知道,怎么还能得到“长期平均刚好符合要求”的随机结果?
🧩 作者把目标表示成“多面体顶点”。白话说,就是一组受总量、容量等条件限制的可行方案,顶点是边界上的组合。比如分配活动名额,既不能超量,也要满足比例要求,新方法能让随机方案保持精确期望。
⏱️ 难点不只是快,而是不能靠“疯狂重复直到碰巧抽中”。此前方案在匹配问题上可能需要指数级的翻币量;新方法把它降为多项式。论文给出的完美匹配上界包含 n 的8次方和精度修正项,其中 n 是问题规模。简单说,维度升高时,不必再用指数级的笨办法。
🏙️ 这和生活的连接点是抽奖分组、名额分配和任务调度。比如活动名额该以什么概率分给参与者,不该靠“多跑几轮大概修一下”,而要让所有可能结果的平均分配量,刚好等于目标比例。这里的“精准”指数学上的无偏,不是每次都抽中同一个人,也不保证单次结果一定符合直觉。
🔬 不过,它目前更像随机算法里的底层零件,论文还没有大规模系统实验或硬件验证,离手机里的现成应用仍有距离。你最想先看到它用在哪:抽奖分组、活动名额,还是AI任务调度?
标签
#随机算法 #精确采样 #概率校准 #随机舍入 #多面体 #资源分配 #任务调度 #组合优化 #机制设计
原文来源
- https://arxiv.org/abs/2611.17223v1
来源类型:arXiv 预印本 · 日期:2026-11-12
边界声明 · 这项研究不能证明什么
本文为一手来源的中文编辑导读,结论的适用范围与证据强度以来源原文为准;不构成医疗、投资或其他决策建议。
AIGC 内容说明
本文由 AI 辅助起草,经今山海编辑部人工核对事实、来源与边界后发布。修订与更正将在本页留痕。