algorithm - 组合随机样本

Question

我有一组元素U（最初未知大小），我想生成一个随机样本n << | 你| 元素。流采样适用于此。

当我将U细分为几个子集并随机抽取每个子集的样本（每个样本包含k <= n元素，但通常是k = n）时，问题就出现了。我也知道每个子集中有多少元素。我想知道如何将这些样本（最好一次合并两个样本）组合成一个大小为n的样本。

或者换一种说法，给定不同的集合A和B以及随机样本a和b，我想让c ⊆ a ∪ b，这样c是A ∪ B的随机样本，我可以指定c的大小（通常 | c | 的大小与 | a |)大致相同。

Answer 1

就好像您仍在从U采样一样。要选择一个样本，首先选择它应该来自的子集S_i 。与相对S_i大小成比例地执行此操作。因此，如果S_1是U的 20%，您从S_1中选择样本的概率为 20%。选择子集后，您可以从该子集中获取任何一个样本，并将其用于最终样本。如果k值小于n ，这可能会遇到问题，但如果通常k = n，这对您来说可能不是问题。

把它放在你的A和B公式中，建立c如下：一个|/| A ∪ B | 从a中获取下一个样本；有概率| 乙|/| A ∪ B | = 1 - (| A |/| A ∪ B |) 从b中获取下一个样本。（如上所述，如果 | a | 不大于n * (| A |/| A ∪ B |) （以及 | b的等价物），这可能会遇到问题|)，但如果是这种情况，我不清楚您是否可以做您想做的事情。）这使您可以一次构建样本两个子集。

Answer 2

如果 |A|==|B| 和|a|==|b|，那么你完全不用担心。只需从 aUb 进行定期赎金采样。