algorithm - 水库采样无法理解概率

Question

明确以下是问题:

给定一个不确定长度的输入流，你如何返回该流的随机成员(每个成员的概率相等)，假设你不能存储超过恒定数量的输入，并且你可以只通过输入一次

这个问题的解决方案似乎是 Reservoir Sampling，如下所述。“首先，您想创建一个包含 1,000 个元素的容器(数组)，并用流中的前 1,000 个元素填充它。这样，如果您恰好有 1,000 个元素，该算法就可以工作。这是基本情况。

接下来，您要处理第 i 个元素(从 i = 1,001 开始)，这样在处理该步骤结束时，您的容器中的 1,000 个元素会从您目前看到的 i 个元素中随机抽样.你怎么能这样做？从 i = 1,001 开始。在第 1001 步之后，元素 1,001(或与此相关的任何元素)出现在 1,000 个元素集合中的概率是多少？答案很简单:1,000/1,001。”

我无法理解最后一句话“答案很简单:1,000/1,001”。在 1001 个元素的数组中找到 1 个元素的概率不应该是 1/1001 而不是 1000/1001 吗？样本空间不是等于 1001，结果的有利数量等于 1 吗？

Answer 1

有 1,001 个元素。其中 1,000 个在样本中。一个在样本之外。因此，特定元素是样本外部元素的概率是 1,001 中的 1，而它是样本内部的千种元素之一的概率是 1,001 中的 1,000。