看到一道随机数生成的算法题

windream1991 发表于 2015-3-2 14:08
就输出而言，这两者似乎没什么差别。我觉得原题的意思就是，输入为一组频率分布以及要抽取的个数k，输出 ...

就你的描述来看，应该不是。原题的意思应当是让你“产生一组分布满足{0.5, 0.3, 0.2}的随机变量”。换句话说，无论用什么手段，只要达到这个目的即可。“模拟不放回随机抽样的过程”只是达到这个效果的一种方法而已。日常生活中常常使用不放回抽样，因为在日常生活中这样做便于实现。但是对于我们这个算法来说，反而是“放回抽样”实现起来简单。所以，为什么不模拟“放回抽样”呢？

除非是另外一种题，就比如说reservior sampling问题。确实给定了你一个数组，让你从其中随机抽出一个指定长度的subset。这种情况下，“放回”和“不放回”的区别才变得非常关键。在我们这个问题中，“放回”和“不放回”最后会产生同等的效果，只是后者更麻烦而已。

stellari 发表于 2015-3-2 14:49
就你的描述来看，应该不是。原题的意思应当是让你“产生一组分布满足{0.5, 0.3, 0.2}的随机变量”。换句 ...

有道理，放回确实要比不放回简单