3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".

A boring proof using induction is here.

For a constructive proof, you can follow the idea from here:

  1. Show that the maximum number of inversions is $\binom{n}{2}$.
  2. Observe that every permutation and its reverse pair up: their respective sets of inversions are complement to each other, so both together add $\binom{n}{2}$ inversions to the sum.
  3. Since this pairing neatly and uniquely covers all permutations, we get that the total number of inversions across all permutations is $\frac{n!}{2} \cdot \binom{n}{2}$.

The claim follows immediately.

$\endgroup$
6
$\begingroup$

For $i < j$ and a random permutation $A$, let $X_{ij}$ be the indicator variable for the event $A[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}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.