Given a disordered list a of size n, and an ordering on the items of a, is there a relationship between the probability that two items are correctly ordered ($P(a_i \leq a_j)$ given $0 < i < j \leq n$) and the probability that any one item is correctly positioned ($P(a_i = s_i)$ where $s_i$ is a correctly sorted version of $a_i$?)
Intuitively, for distinct items:
- If the list is shuffled then 50% of pairs of items are correctly relatively ordered, and $1/n$ items is correctly positioned.
- If the list is in order, then 100% of pairs are correctly ordered, and 100% of items are correctly positioned.
- If the list is reversed, then 0% of pairs are correctly ordered, and at most one item is in the correct position (0% in the limit of a long list).
Things get hairier when items can compare equally, but I'm okay with only worrying about distinct items.
what is the probability $a_i$ is in its correct position after sorting if we have no other information? $\frac{1}{n}$
What is the probability $a_i$ is ints correct position if we know $a_i$ is in its correct position with respect to $a_j$. How many sortings are there where $a_i$ is in its correct position with respect to $a_j$? exactly half of all sortings so $\frac{n!}{2}$
How many of these leave $a_i$ in its correct spot? We do the case when $i>j$, but the other case is similar. First place $a_i$ in its position. Then place $a_j$ in any of the $i-1$ positions we can put it in so it appears before $a_i$, finally arrange the remaining $(n-2)!$ items.
So the probability when $a_i>a_j$ is $\frac{(i-1)(n-2)!}{\frac{n!}{2}}=\frac{2(i-1)(n-2)!}{n!}$
The probability when $a_i<a_j$ is $\frac{2(n-i)(n-2)!}{n!}$