我正在阅读 M.Mitzenmacher 和 E.Upfal 的“概率与计算”。我在理解如何计算两个元素的比较概率时遇到问题。
输入：数字的排序列表 (y1,y2,...,yN)。我们正在寻找枢轴元素（随机）。问题：比较两个元素 yi 和 yj (j>i) 的概率是多少？
答案（来自书本）：如果 yi 或 yj 将在序列 (yi,yi+1,...,yj-1,yj) 的第一次抽奖中被选为枢轴，则将比较 yi 和 yj。所以概率是：2/(j-i+1)。
对我来说，问题是最初的主张：例如，从整个列表中的第一次抽签中选择 yi 将导致与 yj 的比较（反之亦然），概率为 2/n。
因此，相反，“反向”声明是正确的——在 yi 或 yj 之前不能选择 (yi+1,...,yj-1) 元素，但“池”大小不固定（在第一次抽奖中）它肯定是 N，但第二个它更小）。
有人可以解释一下作者是如何得出如此简单的结论的吗？
Edit1：一些好人完善了我的帖子，谢谢:-)。
Edit2：列表最初是排序的。
快速排序通过将每个元素与枢轴进行比较来工作：大于枢轴的那些放在枢轴的右侧，而不大的放在左侧（或者如果您想要降序排序，则相反，没关系） .
在每一步，枢轴都是从一个序列中选择的(yi, yi+1, ..., yj)。这个序列有多少个元素？j - i + 1（我认为您有错字，不可能y - i + 1）。
所以从这个列表中选择两个特定元素之一的概率显然是2 / (j - i + 1)。
对我来说，问题是最初的主张：例如，从整个列表中的第一次抽签中选择 yi 将导致与 yj 的比较（反之亦然），概率为 2/n。
拾取yi将导致它仅与其他j - i元素进行比较。你从哪里来n的？请记住，您的列表仅从yi到yj！
编辑：
再次阅读这个问题，我确实觉得它有点模棱两可。在递归的第一步比较两个元素的概率确实2 / n如你所说，因为iandj是1and n。在未知的递归步骤中比较两个元素的概率就是我上面解释的。
作者给出的答案是正确的，尽管我仍然不明白他们是如何轻松快速地得出结论的。
用 L=j-i+1 表示。j 和 i 的实际值在这里无关紧要，重要的是 L。我们还用 P(N,L) 表示从大小为 N 的有序数字序列中比较 yi 和 yj 元素的概率。
事实：
这个总和看起来很难看，但经过两次测试后，似乎 P(N,L) 可能等于 2/L。让我们来看看：
由于 L=j-i+1，我们得到 2/(j-i+1)。