1

在第 126 页，第 12.2 节：

该算法按顺序考虑整数 0、1、2、...、n-1，并通过适当的随机测试选择每个整数。通过按顺序访问整数，我们保证输出将被排序。

为了理解选择标准，让我们考虑 m=2 和 n=5 的示例。我们应该选择概率为 2/5 的第一个整数 0；一个程序通过类似的语句来实现它

if (bigrand() % 5) < 2

我的问题是，为什么选择第一个整数的概率是 2/5，而不是 1/5？从5个数字中随机选择一个数字的概率不应该是1/5吗？

这里真是一头雾水。希望有人可以在这里提供一些澄清。

谢谢！

4

2 回答 2

1

从5个数字中随机选择一个数字的概率不应该是1/5吗？

这是设计采样算法的一种方法，但这种方法的工作方式不同。它依次考虑每个元素并决定该元素是否是样本的一部分。这是 m=2 和 n=4 的决策树（确定性决策被抑制）。

                            take 0?
               _____yes_____       _____no_____
              /                                \
             /                                take 1?
          take 1?                         yes/       \no
        yes/   \no                          /         \
          /     \                        take 2?     {2,3}
       {0,1}   take 2?                 yes/   \no
             yes/   \no                  /     \
               /     \                {1,2}   {1,3}
            {0,2}   {0,3}

在根上，3/6 的后代结果包括 0，并且以 2/4 = 1/2 的概率取 0。如果我们取 0，那么只有 1/3 的结果包含 1。如果我们不取 0，那么 2/3 的结果包含 1。在每一步，每个决策的概率与相应子树中结果的数量成正比，确保大小为 m 的统一随机子集。

于 2012-06-19T04:32:46.033 回答
1

假设您正在挑选一个有序对。那么第一个数字是该对中的第一个数字的概率为 1/5，同样，第一个数字是该对中的第二个数字的概率为 1/5。（它永远不会同时是这对中的第一个和第二个数字。）

因此，它有 5 次中有 2 次机会出现在有序对中的某个位置。

选择一个随机的无序对与选择一个有序对然后忘记顺序是一样的。因此，它也有 5 次中有 2 次机会成为无序对。

于 2012-06-19T04:37:00.087 回答