水库采样无法理解概率
Reservoir Sampling unable to understand probability
明确以下是问题：
给定一个不确定长度的输入流，你如何 return 该流的随机成员（每个成员的概率相等），前提是你不能存储超过一个常数的输入，你只能通过一次输入
这个问题的解决方案似乎是 Reservoir Sampling，如下所述。
“首先，您想创建一个包含 1,000 个元素的容器（数组），并用流中的前 1,000 个元素填充它。这样，如果您恰好有 1,000 个元素，则该算法有效。这是基本情况。
接下来，您要处理第 i 个元素（从 i = 1,001 开始），以便在处理该步骤结束时，从您看到的 i 个元素中随机抽取您容器中的 1,000 个元素迄今为止。你怎么能这样做？从 i = 1,001 开始。在第 1001 步之后，元素 1,001（或与此相关的任何元素）出现在 1,000 个元素集合中的概率是多少？答案很简单：1,000/1,001."
我无法理解最后一句话"The answer is easy: 1,000/1,001"。在 1001 个元素的数组中找到 1 个元素的概率不应该是 1/1001 而不是 1000/1001 吗？样本 space 是否等于 1001 并且有利的结果数是否等于 1？
共有 1,001 个元素。其中 1,000 个在样本中。一个在样本之外。因此，特定元素是外部元素的概率是 1,001 中的 1，而它是样本内部千个元素之一的概率是 1,001 中的 1,000。
我觉得下面的论点更清楚。设 S 为前 1000 个元素的集合；让 e 表示流中的最后一个元素（例如第 1001 个）。一组 1001 个元素有 {1001 choose 1000}=1001 个可能的大小为 1000 个子集，并且您希望所有这些子集都具有相同的概率存储在数据结构中（每次新元素到达时都应保持不变）。
包含 e 的 1001 个元素的 size-1000 个子集的数量是多少？好吧，由于 e 是固定的，我们还有 1000 个元素可供选择，我们将选择 999 个元素，因此有 {1000 choose 999} = 1000 个这样的子集。
e 在 S 中的概率因此应该是：{1000 choose 999} / {1001 choose 1000} = 1000/1001（即包含 e 的大小为 1000 的子集的数量除以数量所有大小的 1000 个子集）。
我用 {n choose k} 表示 binomial coefficient。
明确以下是问题：
给定一个不确定长度的输入流，你如何 return 该流的随机成员（每个成员的概率相等），前提是你不能存储超过一个常数的输入，你只能通过一次输入
这个问题的解决方案似乎是 Reservoir Sampling，如下所述。 “首先，您想创建一个包含 1,000 个元素的容器（数组），并用流中的前 1,000 个元素填充它。这样，如果您恰好有 1,000 个元素，则该算法有效。这是基本情况。
接下来，您要处理第 i 个元素（从 i = 1,001 开始），以便在处理该步骤结束时，从您看到的 i 个元素中随机抽取您容器中的 1,000 个元素迄今为止。你怎么能这样做？从 i = 1,001 开始。在第 1001 步之后，元素 1,001（或与此相关的任何元素）出现在 1,000 个元素集合中的概率是多少？答案很简单：1,000/1,001."
我无法理解最后一句话"The answer is easy: 1,000/1,001"。在 1001 个元素的数组中找到 1 个元素的概率不应该是 1/1001 而不是 1000/1001 吗？样本 space 是否等于 1001 并且有利的结果数是否等于 1？
共有 1,001 个元素。其中 1,000 个在样本中。一个在样本之外。因此，特定元素是外部元素的概率是 1,001 中的 1，而它是样本内部千个元素之一的概率是 1,001 中的 1,000。
我觉得下面的论点更清楚。设 S 为前 1000 个元素的集合；让 e 表示流中的最后一个元素（例如第 1001 个）。一组 1001 个元素有 {1001 choose 1000}=1001 个可能的大小为 1000 个子集，并且您希望所有这些子集都具有相同的概率存储在数据结构中（每次新元素到达时都应保持不变）。
包含 e 的 1001 个元素的 size-1000 个子集的数量是多少？好吧，由于 e 是固定的，我们还有 1000 个元素可供选择，我们将选择 999 个元素，因此有 {1000 choose 999} = 1000 个这样的子集。
e 在 S 中的概率因此应该是：{1000 choose 999} / {1001 choose 1000} = 1000/1001（即包含 e 的大小为 1000 的子集的数量除以数量所有大小的 1000 个子集）。
我用 {n choose k} 表示 binomial coefficient。