为了明确以下是问题：
给定一个不确定长度的输入流，你如何返回该流的随机成员（每个成员的概率相等），因为你不允许存储超过恒定数量的输入，并且你只能通过输入一次
这个问题的解决方案似乎是 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 吗？
有 1,001 个元素。其中有 1,000 个在样本中。一种是在样本之外。因此，特定元素是外部元素的概率是 1,001 分之一，而它是样本内的一千个元素之一的概率是 1,000 分之 1,001。
我发现下面的论点更清楚。设S为第一个1000元素的集合；让e表示流中的最后一个元素（例如第 1001 个）。一组 1001 个元素可能有{1001 choose 1000}=1001大小为 1000 个的子集，并且您希望所有这些子集都具有相同的存储在数据结构中的概率（每次新元素到达时，此不变量都应保持）。
包含 1001 个元素的 size-1000 个子集的数量是多少e？好吧，既然e是固定的，我们还有1000元素可供选择，我们将选择 999 个元素，因此有{1000 choose 999} = 1000这样的子集。
因此，其中的概率应该是：（e即包含的大小为 1000 的子集的数量除以所有大小为 1000 的子集的数量）。S{1000 choose 999} / {1001 choose 1000} = 1000/1001e
用{n choose k}I 表示二项式系数。