我正在阅读M.Mitzenmacher和E.Upfal的" 概率与计算 ".我在理解如何计算两个元素的比较概率时遇到问题.
输入:数字的排序列表(y1,y2,...,yN).我们正在寻找枢轴元素(随机).问题:两个元素yi和yj(j> i)的概率是多少？
答案(来自书): yi和yj将被比较,如果yi或yj将被选为第一次从序列中绘制的枢轴(yi,yi + 1,...,yj-1,yj).所以可能性是:2 /(j-i + 1).
对我来说问题是最初的主张:例如,在整个列表的第一次抽奖中拾取yi将导致与yj的比较(反之亦然),概率为2/n.
因此,相反"反向"声明是正确的 - 在yi或yj之前不能选择(yi + 1,...,yj-1)元素,但"池"大小不固定(在第一次绘制中)它肯定是N,但在第二个它更小).
有人可以解释作者如何提出这样一个简化的结论吗？
Edit1:一些好心灵打磨了我的帖子,谢谢:-).
Edit2:列表最初排序.