从N个元素中随机均匀地选择M个元素 - 困惑

Question

我知道类似的问题已经被问过了，比如：

从包含n个元素的向量中随机选择m个元素

从未知长度的序列中随机选择n个项目

但是我看得越多就越糊涂。

均匀地和随机地从N个元素中选择M个元素

所以我需要从N个元素中选出M个。并且我还需要使每个元素被选择的概率均匀分布：M/N

我的直觉是

1. 随机选择一个元素
2. 将其取出
3. 在剩下的元素中重复这个过程

我猜这个解决方案是错误的？对于被选中的M个元素的概率是1/N，1/(N-1)，...，1/(N-M)，而不是M/N，我正确吗？

---

一种可能正确的解决方案是

1. 对整个N个元素进行洗牌
2. 选择前M个。

但我无法弄清楚每个元素被选中的概率。

有人能证明这个解决方案的概率确实是M/N吗？

---

当然，我们也可以使用蓄水池抽样算法，其概率为M/N。

- Jackson Tale

Answer 1

元素被选中的概率：

First: 1/N;
Second: 1/(N-1) * (1 - 1/N) = 1/N
...

其中(1-1/N)表示第二个项目在第一步未被选中的概率，这是它在第二步被选中的条件。在这里1/N是某个元素在第一步被选择的概率，而(1-1/N)则表示第二步选择的元素可供第二步选择的概率。

Third: 1/(N-2) * (1 - 1/N - 1/N) = 1/N

此处 (1 - 1/N - 1/N) 代表元素在第三步可选的概率。

简而言之，对于任何一个元素，在每一步中被选中的概率均为 1/N。

- Igor

Answer 2

我认为你的困惑可能在于你没有区分选择序列和选择集合之间的区别。

在你的第一个过程中，仅因为你在第一轮只有1/N的机会选择特定的元素，并不意味着你在随后的回合中不会选择它。该元素有1/N的机会成为结果中的第一个元素...但是它在某些回合中被选中的机会是M/N。所以这个方法可行。取M=2，N=4：元素被选中的概率为1/4 + (3/4)*(1/3) = 2/4。

至于你的第二个过程，在洗牌后，每个元素在数组中的位置是均匀分布的，因此它的位置等于或小于M（因此被选择）的概率是M/N。所以这也是可行的。

- Sneftel

---

我另一个困惑是术语“uniformly”。我应该期望每个元素有1/N的选择机会还是M/N的选择机会？ - Jackson Tale

元素 A 在第 i 轮中被选中的概率为 1/N，而在 任何 一轮中被选中的总概率为 M/N。 - Sneftel

啊，好的。你的意思是A有1/N的机会成为第一位，对于第二位，它也有1/(N-1) * (N-1)/N = 1/N的机会，因为(N-1)/N是它不被选为第一位的概率。以此类推，A有M/N的机会成为任何一个选择。正确吗？ - Jackson Tale

是的。随着回合数的增加，分数变得更长，但数学仍然成立。 - Sneftel

Answer 3

虽然洗牌方法可行，但还有一种不需要修改原始数组的方法。实际上，您甚至不需要知道总共有多少项。您可以从流中随机选择M个项目，而您唯一需要保存的数据就是这些M个项目的数组。

基本思想是从未知长度的流中选择单个项目的算法的扩展。同样，您不知道流中有多少项。因此，您始终有一个选定的项目，但您可能随时更改所选的项目。

您开始没有选择的项目，并且计数为0。当第一个项目进来时，您增加计数。然后，您在范围0到计数-1之间选择一个随机数。如果值为0，则将当前项目设置为所选项目。第一个随机数必须为0，因为您的范围是0到0。

当您阅读每个项目时，您会增加计数，选择随机数字，并在选择的随机数字为0时将当前项目设置为所选项目。它看起来像这样：

selected_item = none
count = 0
for each item
    count = count + 1
    if (random(count) == 0)
        selected_item = current_item

这种方法的原理是，随着每个项目的阅读，选择当前项目的机会逐渐减小。也就是说，第一个项目被选中的概率为1/1。当第二个项目出现时，你有1/2的机会选择它来替换第一个项目。当你收到第三个项目时，你有1/3的机会用新项目替换当前选定的项目。

当你到达流的末尾时，每个项目都有同等的机会被选中。

你可以很容易地将其扩展到多个项目。你首先选择前M个到达的项目，并将它们放入已选项目数组中。然后，每当一个新项目出现时，你从0到计数-1之间选择一个随机数，如果这个数字小于M，那么你随机替换其中一个已选项目为新项目。代码如下：

selected_items = array of M items
count = 0
for each item
    if (count < M)
        selected_items[count] = current_item
    else
        if (random(count) < M)
            // pick a random number from 0 to M-1
            // and replace that item with the new item
            ix = random(M)
            selected_items[ix] = current_item

我在我的博客《随机选择》中详细地阐述了这一点。

- Jim Mischel

---

博客文章链接已损坏。 - Alexander Pavlov