标题： 一个精确且高效的动态离散分布采样器 显示英文标题

标题： An Exact and Efficient Sampler for Dynamic Discrete Distributions

摘要： 从动态离散分布中采样涉及从一组带权重的元素中采样，这些元素可以在采样过程的任意阶段被添加或移除。 尽管对于静态集合来说效率很高，但别名方法在动态环境中变得不切实际，因为每次更新后都需要重新构造采样器，这会导致计算成本与分布大小成正比，使其不适合需要频繁插入、删除或调整权重的应用场景。 为了解决这一局限性，研究了不同的方法，例如树森林方法和BUCKET采样（BUS）方法。 然而，所有先前的方法都存在数值问题，这些问题可能使采样过程产生偏差。 在本文中，我们描述了EBUS（精确BUCKET采样），这是第一个具有$O(1)$采样和更新成本的精确算法。 该采样器可以通过具有有界精度和指数的基底$b$数字进行更新，并且可以精确且高效地采样其元素的分布。 我们还提供了使用IEEE 64位浮点数对该方法的最先进的实现，并通过实证表明它比先前的几种不精确方法的实现更有效。 显示英文摘要

摘要： Sampling from a dynamic discrete distribution involves sampling from a dynamic set of weighted elements, where elements can be added or removed at any stage of the sampling process. Although efficient for static sets, the Alias method becomes impractical in dynamic settings due to the need to reconstruct the sampler after each update, which incurs a computational cost proportional to the size of the distribution, making it unsuitable for applications requiring frequent insertions, deletions, or weight adjustments. To address this limitation, different approaches have been studied, such as the Forest of Trees method and the BUcket Sampling (BUS) method. However, all previous methods suffered from numerical issues which can bias the sampling process. In this paper, we describe EBUS (Exact BUcket Sampling), the first exact algorithm with $O(1)$ sampling and update cost. The sampler can be updated by base-$b$ numbers with bounded precision and exponent, and sample the distribution of its elements exactly and efficiently. We provide also a state of the art implementation of the method using IEEE 64-bit floating point numbers which we empirically show to be more efficient than several implementations of previous inexact methods.