patternMinor
Deriving the average number of inversions across all permutations
Viewed 0 times
numbertheinversionsderivingallaverageacrosspermutations
Problem
In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:
$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A) \tag{1},$$
where $A$ is an array, $\mathbb{E}[C_{\text{swaps}}]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$.
Then (1) is equal to the following equation:
$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$
But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?
$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A) \tag{1},$$
where $A$ is an array, $\mathbb{E}[C_{\text{swaps}}]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$.
Then (1) is equal to the following equation:
$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$
But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?
Solution
For $i A[j]$. Clearly $\Pr[X_{ij} = 1] = 1/2$ and so $E[X_{ij}] = 1/2$. The total number of inversions is $\sum_{i<j} X_{ij}$, and so the average number of inversions is
$$
E\left[\sum_{i<j} X_{ij}\right] = \sum_{i<j} E[X_{ij}] = \sum_{i<j} \frac{1}{2} = \frac{1}{2} \binom{n}{2}.
$$
$$
E\left[\sum_{i<j} X_{ij}\right] = \sum_{i<j} E[X_{ij}] = \sum_{i<j} \frac{1}{2} = \frac{1}{2} \binom{n}{2}.
$$
Context
StackExchange Computer Science Q#63682, answer score: 7
Revisions (0)
No revisions yet.