预期的反转次数 - 从Cormen的算法简介

Question

设A [1 .. n]是n distinct个数的数组.如果i <j且A [i]> A [j],那么对(i,j)被称为A的反转.(有关反演的更多信息,请参阅问题2-4.)假设选择A的每个元素从1到n的范围内随机,独立地和均匀地.使用指标随机变量来计算预期的反转次数.

---

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

假设x(i)是[1..i]中的反转次数,而E(i)是x(i)的期望值,那么E(i + 1)可以如下计算:
我们有的图像i+1如果我们将i + 1置于第一个位置,则放置所有数字的位置,然后x(i + 1)= i + x(i); 如果我们将i + 1放在第二个位置,那么x(i + 1)= i-1 + x(i),...,所以E(i + 1)= 1 /(i + 1)*sum( k)+ E(i),其中k = [0,i].最后我们得到E(i + 1)= i/2 + E(i).
因为我们知道E(2)= 0.5,所以递归得到: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

Answer 2

另一种解决方案甚至更简单,即IMO,尽管它不使用"指标随机变量".

由于所有数字都是不同的,因此每对元素都是反转(i < j带A[i] > A[j])或非反转(i < j带A[i] < A[j]).换句话说,每对数字都是有序或无序的.

因此,对于任何给定的排列,反转的总数加上非反转的数量只是对的总数,或者n*(n-1)/2.

通过"小于"和"大于"的对称性,预期的反转次数等于预期的非反转次数.

由于它们的总和的期望是n*(n-1)/2(所有排列都是恒定的),并且它们是相等的,它们各自是它的一半n*(n-1)/4.

[更新1]

显然,我的"少于'和'大于'的对称性"声明需要一些阐述.

对于A1到1范围内的任何数字数组n,定义~A为从中减去每个数字时得到的数组n+1.例如,如果A是[2,3,1],则~A是[2,1,3].

现在,观察对于任何一对数字A都是有序的,相应的元素~A是乱序的.(易于显示,因为否定两个数字会交换它们的顺序.)此映射明确显示了在此上下文中小于和大于之间的对称性(对偶性).

因此,对于任何A,反转的数量等于非反转的数量~A.但是对于每一种可能A,只有一个对应~A; 当数均匀选择,既A和~A是等可能的.因此,在反转的预期数量A等于预期数量的倒在~A,因为这些预期被计算在完全相同的空间.

因此,预期的反转次数A等于预期的非反转次数.这些期望的总和是对和的期望,即,常数n*(n-1)/2或对的总数.

[更新2]

一个更简单的对称性:对于任何数组A的n元素,定义~A为相同的元素,但以相反的顺序.在关联位置的元素i中A的位置元素n+1-i中~A.(也就是说,在反转数组中将每个元素与自身相关联.)

现在,任何反转A都与非反转相关联~A,就像上面的Update 1中的结构一样.所以同样的论点适用:倒数A的数量等于倒数的数量~A; 两个A和~A是等可能的序列; 等等

这里的直觉点是"小于"和"大于"运算符只是彼此的镜像,您可以通过否定参数(如Update 1中)或通过交换它们来看到(如Update中所示) 2).因此,预期的反转次数和非反转次数是相同的,因为您无法判断是否通过镜像查看任何特定阵列.

Answer 3

我认为这是对的，但我认为证明它的正确方法是使用条件期望：

对于所有 X 和 Y，我们有： E[X] =E [E [X|Y]]

那么在你的情况下：

E(i+1) = E[x(i+1)] = E[E[x(i+1) | x(i)]] = E[SUM(k)/(1+i) + x(i)] = i/2 + E[x(i)] = i/2 + E(i)

关于第二个声明：

如果 ：

E(n) = n* (n-1)/4。

那么 E(n+1) = (n+1)*n/4 = (n-1)*n/4 + 2*n/4 = (n-1)*n/4 + n/2 = E( n) +n/2

所以n*(n-1)/4。验证所有 n >=2 的递归关系，并验证 n=2 的递归关系

所以 E(n) = n*(n-1)/4

希望我理解你的问题并且有帮助