0

STLrandom_sample函数使用替换策略从给定的区间进行采样。为什么我们需要降低概率，我见过一个类似的算法而不降低替换概率。有什么区别。代码如下：

/*This is an excerpt from STL implementation*/
template <class InputIterator, class RandomAccessIterator, class Distance>
RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
                                         RandomAccessIterator out,
                                 const Distance n)
{
  Distance m = 0;
  Distance t = n;
  for ( ; first != last && m < n; ++m, ++first) //the strategy is also used in mahout
    out[m] = *first;//fill it

    while (first != last) {
        ++t;
        Distance M = lrand48() % t;
        if (M < n)
          out[M] = *first;//replace it with a decreasing probability
        ++first;
    }

  return out + m;
}
4

1 回答 1

1

很明显，必须以（“填充”阶段）n的概率选择第一个元素（实际上是第一个元素）。1为了保留在最终样本中，第一个元素需要在m-n可能的替换中幸存下来——这就是它在样本中的概率降低到的原因n/m。另一方面，最后一个元素只参与一次替换；因此，它应该以n/m从一开始的概率添加到样本中。

为简单起见，假设您只需要m使用此替换策略从 中选择一个元素（请注意，您事先并不知道是什么m：您只是迭代直到突然到达终点）。你取第一个元素，并保持它的概率为1（据你所知，这是唯一的元素）。然后你发现了第二个元素，你扔了一枚硬币，要么保留它，要么丢弃它，概率为1/2。此时，前两个元素中的每一个都有1/2可能被选中。

现在你看到了第三个元素，你保留它的概率为1/3。前两个元素中的每一个都有1/2可能参与这次遭遇并2/3幸存下来 - 总1/2 * 2/3 == 1/3概率仍然存在。因此，同样，前三个元素中的每一个都有1/3被选中的概率。

证明在t检查第一个元素之后，第一个t元素中的每一个都有1/t被选择的概率的归纳步骤留给读者作为练习。将证明扩展到大小样本也是如此n > 1。

于 2013-08-29T13:34:02.233 回答