从N个元素中均匀随机选择M个元素-混淆

Question

我知道有人问过类似的问题

Choose m elements randomly from a vector containing n elements

Pick N items at random from sequence of unknown length

可是越看越糊涂

Uniformly and randomly choose M elements from N elements

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

我的直觉是

随机选择一个元素
拿出来
对其余元素重复该过程

我猜这个解决方案是错误的？ M 个选定元素的概率为 1/N、1/(N-1)、...、1/(N-M)、不 M/N , 我说的对吗?

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

对整个N个元素做一个洗牌
选出前M个。

但是我计算不出每个元素被选中的概率。

谁能证明这个解的概率确实是M/N？

当然我们也可以用Reservoir sampling，它的概率是M / N.

Answer 1

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

在您的第一个程序中，仅仅因为您只有 1/N 机会在第一轮中选择特定元素，并不意味着您不会在后续轮中选择它。该元素有 1/N 的机会成为结果中的第一个元素...但它有 M/N 的机会在 some 轮中被选中。这样就可以了。取M=2，N=4：一个元素被选中的几率是1/4 + (3/4)*(1/3) = 2/4.

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

Answer 2

元素被选中的概率：

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。

Answer 3

尽管 shuffle 方法有效，但还有另一种方法不需要修改原始数组。事实上，您甚至不需要知道总共有多少项。您可以从流中随机选择 M 个项目，而您唯一需要保存的数据是这 M 个项目的数组。

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

开始时没有 selected 项目，计数为 0。当第一个项目出现时，您增加计数。然后你在 0 到 count-1 范围内选择一个随机数。如果该值为 0，则您将当前项目设为 selected 项目。选择的第一个随机数必须是 0，因为您的范围是 0 到 0。

当您阅读每个项目时，您会增加计数，选择随机数，如果选择的随机数为 0，则使当前项目成为 selected 项目。它看起来像这样：

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

这是有效的，因为 select阅读当前项目的机会随着每个项目的阅读而减少。也就是说，第一项 select 的概率为 1/1。当第二个物品进来时，你有 1/2 的几率 select 它会取代第一个物品。当您收到第三件物品时，您有 1/3 的机会将当前 selected 物品替换为新物品。

当您到达流的末尾时，您将给予每个项目同等的机会 selected。

您可以很容易地将其扩展到多个项目。您首先 selecting 进来的前 M 个项目，然后将它们放在 selected 项目数组中。然后，每当有新项目出现时，您会在 0 和 count-1 之间选择一个随机数，如果该数字小于 M，则您会用新项目随机替换 selected 项目中的一个。它看起来像这样：

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

我在我的博客 Random selection 中写了更多关于这个的细节。

从N个元素中均匀随机选择M个元素-混淆

Uniformly and randomly choose M elements from N elements - confused

random

algorithm