Expected number of swaps

An exciting math question asked in Tower Research Capital

Morty has an array of length n filled with distinct numbers in any random order. He gives the array to Rick who sorts it using bubblesort algorithm. Bubblesort takes an array {a1, a2, a3 .. an} of numbers and repeatedly swaps adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no remaining inversions.

What is the expected number of swaps performed by Rick?

---

Try to solve this problem yourself before moving on to the solution below

.
.
.

.

.

---

Solution

A pair (i,j) is an inversion in array D if D[i] > D[j] and i < j

For a permutation of length n, let I_ij if (𝑖,𝑗) is an inversion. Then
E[I_ij ] = 𝑃((𝑖,𝑗) is an inversion) = 1/2

This is easy to see by symmetry: for any pair (𝑖,𝑗) that's an inversion, (𝑗,𝑖) is not an inversion.

Now use the linearity of expectation to solve for all the pairs

\( \mathbb{E}[\sum_{i=1}^n \sum_{j>i}^n I_{ij}] = \sum_{i=1}^n \sum_{j>i}^n \frac{1}{2} = {{n}\choose{2}} \frac{1}{2} \)

Simple calculations give the result

\(Inversions = \frac{n(n-1)}{4}\)

Another solution
Every permutation 𝜋 with 𝑁 inversions can be read backwards to give a permutation with 𝑛C2−𝑁 inversions. This gives a 1-1 map between permutations with 𝑁 inversions and 𝑛C2−𝑁 inversions. Then by symmetry it's clear that the expected value is nC2 / 2.

.

.

😃 Over to you: Were you able to solve this?

---

👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.

👉 If you love reading this newsletter, feel free to share it with friends!