编程珠玑P124页 12.5 第二题

Question

看答案没看懂，答案上说从0~n-1范围内选择m个整数，可以先在该范围内随机选择一个数i，然后输出i,i+1,...,i+m-1（可能绕回到0）。这一方法选中每个整数的概率都是m/n,但特定子集的选中概率明显偏大。

比如说：有个集合{0 1 2 3}，我们从中选择元素为2个的子集，即为{0,1} {1,2} {2,3} {3,0}，为什么有的子集概率会偏大呢？

Answer 1

• 每个元素的选择概率都是m/n，好理解：对于包含m个元素的子集，任意元素i(0<=i<=n-1)出现的频次可以有m次，而在集合中每个元素被选中的概率是1/n，所以子集中每个元素的选择概率就是m*(1/n)=m/n
• 特定子集的选择概率明显偏大，可以这样理解：对于答案给出的算法，任意一个子集的选择概率其实等同于子集中第一个元素的选择概率，因为一旦第一个元素选定后，后续的m-1个元素就唯一确定了。所以每个元素连续的子集的选择概率等同于其第一个元素的选择概率为1/n，而元素不连续的子集根本无法选取到，则其选择概率为0。所以特定子集的选择概率当然明显偏大。对于你的例子：{0,1}, {1,2}, {2,3}, {3,0}的选择概率都是1/4，而{0,2}, {1,3}的选择概率为0

Answer 2

哪个数字出现概率不是2/4？