2
$\begingroup$

The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.

Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an inversion of $A$. Suppose that the elements of $A$ form a uniform random permutation of $<1,...,n>$. Use indicator random variables to compute the expected number of inversions.

The solution from https://walkccc.github.io/CLRS/Chap05/5.2/ says:

Let $X_{ij}$ be an indicator random variable for the event where the pair $A[i], A[j]$ for $i < j$ is inverted. We have $\Pr\{X_{ij} = 1\} = \frac{1}{2} $, because given two distinct random numbers, the probability that the first is bigger than the second is $\frac{1}{2}$.

I would like to ask what is the rationale for $\Pr\{X_{ij} = 1\} = \frac{1}{2}$. I know that there can be only 2 outcomes, either be $X_{ij} =1$ or $X_{ij}=0$. Also, $\Pr\{X_{ij} = 1\}+\Pr\{X_{ij} = 0\}=1$.

After looking at the answer, it kind of make sense, but I would like to ask if there is a more "systematic" way to derive/justify this probability. Note that I am being very vague about the meaning of systematic because I simply would like to have a more reliable way of deriving this probability rather than only relying on intuition.

$\endgroup$
2
$\begingroup$

For a permutation $\pi$, let $\pi(i\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\;j)(i\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\{\pi,\pi(i\;j)\}$.

Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\;j)$. In exactly one of these cases, the pair $(i,j)$ is an inversion. Therefore the pair $(i,j)$ is an inversion for exactly $n!/2$ of the permutations, i.e., with probability exactly $1/2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.