我有一个概率列表$p_k$，每个对应于伯努利分布。这些价值观$p_k$都很小（比如说 0.1% 或更少）。我想准备一个数据结构，允许快速采样每个伯努利分布并返回返回 1 而不是 0 的稀疏集。

天真地，这个采样任务的预期运行时间成本是$O(N)$在哪里$N$是概率的数量。我希望生成另一组稀疏样本的预期运行时间改为$\tilde{O}(pN)$在哪里$p$是最大概率$p_k$.

我知道可以做这种事情，只是不记得方法的名称。该方法涉及将概率转换为指数分布中的跨度，在跨度上创建搜索树，然后使用树快速识别来自该指数分布的样本落在内部的跨度（它告诉您稀疏样本中的下一个值） ，然后在经过着陆的跨度上递归。

（另一种方法是将概率分组为大小组$1/p$，预先计算在对组内的所有元素进行抽样时出现的 True 数量的概率分布，然后使用别名抽样来抽取多少个样本而无需重复提取 [也使用别名抽样]。）

如果在 scipy 等通用 python 库中提供了实现这种加速的方法，那将特别有用。