在线一代统一样品

Question

一个来源提供了$ x_1，x_2， dots $的项目流。在每个步骤$ n $下，我们要保存一个随机样本$ s_n subseteq {（x_i，i）| 1 le i le i le n } $ size $ k $，即$ s_n $应该是均匀选择的来自所有$ tbinom {n} {k} $的样本，可能由可见项目组成。因此，在每个步骤中，$ n ge k $我们必须决定是否将下一个项目添加到$ s $。如果是这样，我们还必须确定从$ S $中删除的当前项目。

陈述该问题的算法。证明其正确性。

Answer 1

由于这个问题的可疑性质，我只提供提示。

您是否尝试过明显的？使用概率$ frac {1} {n} $，将新元素添加到示例中。如果添加它，请随机选择样品中的一个元素之一，然后将其丢弃。听起来很公平，不是吗？

为了证明，您必须进行归纳。在步骤中，您假设$ s_ {n-1} $确实是统一的样本。从此以及您选择是否包括$ x_n $以及要删除的元素的方式，您必须获得$ s_n $也是统一的样本。

如果您可以证明上述想法正确，请尝试。如果不是这样，请找出问题所在并解决问题。看 这个答案 与此技术的详细应用相似的问题。

Answer 2

解决问题的最佳算法是储层抽样算法。读 这个