排列中逆序对的期望求解问题

问题描述 #

对于$1 < i,j <n$，在$1,2,...,n$的排列中，如果$i < j$且$j$在排列中出现在$i$之前，那么有序对$(i,j)$被称为一个逆序对。例如，在排列$3,5,1,4,2$中有6个逆序对：$(1,3), (1,5), (2,3), (2,4), (2,5)$和$(4,5)$。假设我们从$n!$个排列中随机选择一个排列$\rho$。

定义随机变量$X_{i,j}$：当$(i,j)$是$\rho$中的逆序对时，$X_{i,j}=1$；否则$X_{i,j}=0$。求$E(X_{i,j})$，即$X_{i,j}$的期望？

求排列$\rho$中逆序对的期望数量，将其表示为$n$的函数。

我的思路尝试 #

我一直在思考这个问题，首先注意到像$1,2,3,4,5$这样的有序排列中没有逆序对；而像$5,4,3,2,1$这样的逆序排列中，逆序对的数量是最多的。

对于$E(X_{i,j})$，我知道它等于$1 \times P(X_{i,j}=1) + 0 \times P(X_{i,j}=0)$，也就是等于$(i,j)$是逆序对的概率。

我也在想$n$个元素的排列中逆序对的可能数量，考虑位置和数值的约束：从位置角度看，最多的逆序对数量是$(n-1)+(n-2)+\dots+1 = \frac{n(n-1)}{2}$，但我现在有点卡壳了，不知道接下来怎么推。

问题解答 #

1. 单个随机变量$X_{i,j}$的期望$E(X_{i,j})$ #

其实不用想太复杂，对于任意一对满足$i<j$的元素，在随机排列里，要么$i$出现在$j$前面，要么$j$出现在$i$前面——这两种情况是完全等概率的，因为所有排列都是等可能被选中的，没有任何偏向性。

所以$(i,j)$成为逆序对的概率就是$\frac{1}{2}$，因此$E(X_{i,j}) = \frac{1}{2}$。

2. 排列中逆序对的期望数量 #

这里可以用期望的线性性来简化计算：不管随机变量之间是否独立，期望的和等于和的期望，这个性质真的超好用！

首先，我们先算出所有满足$i<j$的$(i,j)$对的总数，也就是组合数$\binom{n}{2} = \frac{n(n-1)}{2}$。每一对对应的$X_{i,j}$的期望都是$\frac{1}{2}$，那逆序对的期望数量$E[X]$（其中$X = \sum_{1 \leq i<j \leq n} X_{i,j}$）就是：
$$E[X] = \sum_{1 \leq i<j \leq n} E(X_{i,j}) = \binom{n}{2} \times \frac{1}{2} = \frac{n(n-1)}{4}$$

是不是比你之前想的要简单很多？

备注：内容来源于stack exchange，提问作者Node.JS