The expected number of inversions--From Introduction to Algorithms by Cormen

Question

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. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.

---

The problem is from exercise 5.2-5 in Introduction to Algorithms by Cormen. Here is my recursive solution:

Suppose x(i) is the number of inversions in a[1..i], and E(i) is the expected value of x(i), then E(i+1) can be computed as following:
Image we have i+1 positions to place all the numbers, if we place i+1 on the first position, then x(i+1) = i + x(i); if we place i+1 on the second position, then x(i+1) = i-1 + x(i),..., so E(i+1) = 1/(i+1)* sum(k) + E(i), where k = [0,i]. Finally we get E(i+1) = i/2 + E(i).
Because we know that E(2) = 0.5, so recursively we get: E(n) = (n-1 + n-2 + ... + 2)/2 + 0.5 = n* (n-1)/4.

---

Although the deduction above seems to be right, but I am still not very sure of that. So I share it here.

If there is something wrong, please correct me.

Answer 1

All the solutions seem to be correct, but the problem says that we should use indicator random variables. So here is my solution using the same:

    Let Eij be the event that i < j and A[i] > A[j].

    Let Xij = I{Eij} = {1 if (i, j) is an inversion of A

                        0 if (i, j) is not an inversion of A}

    Let X = Σ(i=1 to n)Σ(j=1 to n)(Xij) = No. of inversions of A.

    E[X] = E[Σ(i=1 to n)Σ(j=1 to n)(Xij)]

         = Σ(i=1 to n)Σ(j=1 to n)(E[Xij])

         = Σ(i=1 to n)Σ(j=1 to n)(P(Eij))

         = Σ(i=1 to n)Σ(j=i + 1 to n)(P(Eij)) (as we must have i < j)

         = Σ(i=1 to n)Σ(j=i + 1 to n)(1/2) (we can choose the two numbers in
                                            C(n, 2) ways and arrange them
                                            as required. So P(Eij) = C(n, 2) / n(n-1))

         = Σ(i=1 to n)((n - i)/2)

         = n(n - 1)/4