Random quicksort is the quicksort where the pivot is chosen at random. Let $y_1, y_2, …, y_n$ be the elements in their final position in the sorted list. (As opposed to $x_1, x_2, …, x_n$ in the unsorted list.)
The question is what's the probability that some element $y_i$ will be compared to element $y_j$. I can't answer that one.
I can answer some easier ones.
I can see the probability that element $y_1$ and element $y_n$ will be compared. That only occurs if either one is chosen as a pivot as the first pivot chosen. So that's $2/n$.
I can see the probability that element $y_i$ and $y_{i+1}$ will be compared. That occurs eventually because the tendency for these two elements is go together in the same sublist. This implies eventually they'll have to be compared because either one will be a pivot while both are in the same sublist. So the probability of them being compared is 1.
Best Answer
Elements $y_i$ and $y_j$ remain in the same sublist as long as you choose pivots that are on the same side of them (both less or both greater). There comes a one point in the algorithm at which you choose a pivot that's either between them or one of them. If it's between them, they will never be compared. If it's one of them, they will be compared. At this point, all $j-i+1$ of these elements are candidates for the pivot, and they all have the same probability of being chosen. That's two favourable outcomes out of $j-i+1$ equiprobable outcomes, for a probability of $2/(j-i+1)$.