从直方图/频率哈希表中随机采样

Question

我目前正在尝试提出一种半体面(考虑复杂性、统计属性和常识(的采样算法。

数据当前包含在哈希表中，其中每个键都是一个项目，键的值是项目在原始分布中的频率。

如果一个人想从这样的直方图中采样，如果他想保留项目的原始概率并将它们转移到样本中，他将如何去做？

此外，我们要求有一个标志，指示示例中是否允许重复项。在不允许重复的情况下，我想出的最好的办法是应用上面段落中的算法，并在采样后从哈希表中删除该项目。这样，至少在剩余项目中保留相对概率。但是，我不确定这是否是统计上公认的做法。

是否有普遍接受的算法来执行此操作？如果它有帮助，我们需要在Common Lisp中实现它。

Answer 1

这是答案的一部分。它使用列表而不是哈希表：

(defun random-item-with-prob (prob-item-pairs) 
"The argument PROB-ITEM-PAIRS is ((p_1 item_1) (p_2 item_2) ... 
(p_n item_n)). The function returns one of the items according to the
probabilities. "
(loop with p = (random 1.0)
with x = 0
for pair in prob-item-pairs
do
(if (< p (+ (first pair) x)) 
(return (second pair))
(incf x (first pair)))))

对于问题的第二部分：如果您想根据频率进行采样，这意味着您关心数据的分布。删除项目(或不允许重复项(会在采样过程中更改分布。如果您确实想这样做，您可以重复调用上一个函数，删除重复项，直到获得所需的样本大小。