Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top