Question
Suppose we receive numbers $1, 2, 3, 4, 5, 6$ in a random order. Define an inversion as an ordered pair of numbers $(i, j)$ such that $i < j$ but $j$ comes before $i$ in the random order.
For example, if we receive the numbers $3, 5, 1, 4, 2, 6$, then the inversions would be: $(1,3), (2,5), (2,3), (2,4), (2,5), (4,5)$.
(a) How many different ways can we order the numbers $1 $ to $6$?
(b) Fix two numbers, $i$ and $j$. What is the probability that $i$ comes before $j$?
(c) What is the expected number of inversions in a random order?
I am having particular trouble with (c), but I've included how I approached the other components as well.
My solutions:
(a) Given that order matters here, the number of ways to order 1 through 6 is simply $6!$.
(b) I actually wrote out six boxes, $1...6$ and wrote out the ways that $i$ could come before $j$. For example, there are $5$ boxes that $j$ could fill when we have the following: $i,O,O,O,O,O$, where $O$ represents an empty spot that $j$ may occupy. Doing so I find 15 ways that $i$ can come before $j$. There are an equal number of ways that $j$ can come before $i$. So the probability is $\frac{15}{30} = \frac{1}{2}$.
(c) My intuition here is to find the expected value, $E[X_k]$, that any given $i$ is less than $j$, but such that $j$ comes before $i$. Given the linearity of expectations, I could then extrapolate for all six integers, giving us $6*E[X_k]$, or written more formally, $\sum_{k=1}^6 E[X_k]$.
In part (b) I found that the probability that $i$ comes before $j$ is $\frac{1}{2}$, which would also equal the probability that $j$ comes before $i$. This probability would need to be multiplied by the number of integers that come before a number $i$, but that number changes depending on where $i$ sits in the list of $6$. I'm not exactly sure where to go from here (I also attempted this problem with an indicator function, again to no avail).
You need to look at pairs of numbers, not individual numbers. For each pair $\langle i,j\rangle$ with $1\le i<j\le 6$ let $X_{i,j}$ be the random variable that is $1$ if $j$ comes before $i$ and $0$ otherwise. From (b) you know that $\Bbb E[X_{i,j}]=\frac12$. The random variable that you want is $X=\sum_{1\le i<j\le 6}X_{i,j}$, and by linearity of expectation we have
$$\Bbb E[X]=\sum_{1\le i<j\le 6}\Bbb E[X_{i,j}]=\sum_{1\le i<j\le 6}\frac12\;,$$
which is ... ?