根据逆权重从列表中选择一个随机元素

Question

我有一个加权元素列表，我想选择一个概率与其权重成反比的元素。

例如，在分别[a, b, c]具有权重的列表中[4, 3, 2]，我可以使用加权概率消除元素，直到得到一个包含 1 个元素（即所选元素）的列表。在该算法中，在第一次迭代中，元素a将以概率 被消除4/9。如果a在第一轮被淘汰，我们有一个[b, c]包含权重的数组[3, 2]。从那里开始，元素b将以概率 被消除3/5。如果b被消除，我们就选择了元素c。

在有3个元素的情况下，被选择的概率是和 都被消除的c概率。这等于then被消除的概率加上then被消除的概率或ababba

(
    // a eliminated first
    w(a) / (w(a) + w(b) + w(c)) *
    // b eliminated second
    w(b) / (w(b) + w(c))
) +
(
    // b eliminated first
    w(b) / (w(a) + w(b) + w(c)) *
    // a eliminated second
    w(a) / (w(a) + w(c))
)

有没有一种方法可以快速计算每个单独元素的概率，而不管列表中的元素数量如何，并确认概率之和为 1？或者是否有一个单独的算法可用于选择与其权重成反比的元素？

Answer 1

要以与某些权重成反比的概率进行采样，您可以等效地以与这些权重的倒数成正比的概率进行采样。因此，我们首先反转所有权重，对权重进行归一化，使它们之和为 1（形成概率分布），然后从该分布中正常采样。

下面是一些 Python 式的伪代码：

weights = [1.0 / w for w in weights]           # Invert all weights
sum_weights = sum(weights)
weights = [w / sum_weights for w in weights]   # Normalize weights
return numpy.random.choice(options, p=weights) # Sample

或者在 numpy 中：

weights = numpy.reciprocal(weights)            # Invert all weights
weights = weights / numpy.sum(weights)         # Normalize
return numpy.random.choice(options, p=weights) # Sample