algorithm - 倒置的预期次数--来自Cormen的算法导论

Question

令 A[1 .. n] 为 n 个不同 数字的数组。如果 i < j 且 A[i] > A[j]，则 (i, j) 对称为 A 的反演。(有关反演的更多信息，请参见问题 2-4。)假设选择 A 的每个元素从 1 到 n 的范围内随机地、独立地、均匀地分布。使用指标随机变量计算预期的反转次数。

---

问题出自 Cormen 的算法导论 中的练习 5.2-5。这是我的递归解决方案:

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.

---

虽然上面的推断似乎是对的，但我还是不太确定。所以我在这里分享。

如有不妥之处，欢迎指正。

Answer 1

所有的解决方案似乎都是正确的，但问题是我们应该使用指标随机变量。所以这是我使用相同的解决方案:

    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