From: Maciej Pilichowski on

I am reading "Probability and Computing" by M.Mitzenmacher and E.Upfal
[1]. I am having problems understanding how the probability of
comparison of two elements is calculated.

Input: the sorted list (y1,y2,...,yN) of numbers. We are looking for
pivot element (chosen randomly). Question: what is probability that
two elements yi and yj (j>i) will be compared?

Answer (from book) [2]: yi and yj will be compared if either yi or yj
will be selected as pivot in first draw from sequence
(yi,yi+1,...,yj-1,yj). So the probablity is: 2/(j-i+1).

The problem for me is the initial claim: for example, picking up yi in
the first draw from the whole list will cause the comparison with yj
(and vice-versa) and the probability is 2/n.

So, rather the "reverse" claim is true -- none of the (yi+1,...,yj-1)
elements can be selected before yi or yj, but the "pool" size is not
fixed (in first draw it is N for sure, but on the second it is

Could someone please explain how the authors come up with such a
simplified conclusion?



page 37
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
From: Maciej Pilichowski on
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.