Computing a Conditional Expectation

108 Views Asked by At

Let $\pi$ be a permutation of ${1,\ldots ,n}.$ The pair $(i,j)$ with $i<j$ is an inversion if $\pi(i)>\pi(j).$ Denote the number of inversions by $\text{Inv}$. Let $M=(M_{i,j})$ be a $n\times n$ matrix defined by $$M_{i,j}=\begin{cases}-1,&\text{if }\,\,i<j\\[0.2cm]\phantom{+}0,&\text{if }\,\,i=j\\[0.2cm]\phantom{+}1,&\text{if }\,\,i>j\end{cases}$$ If we define $X(\pi):=\sum_{i<j}M_{\pi(i),\pi(j)}$, I can show that $X(\pi)=2\times\text{Inv} - \frac{n(n-1)}{2}.$ Define $W:=\frac{X}{\text{Var}X}$. Choose $I$ uniformly at random between $1$ and $n$ and define $\pi'$ to be the composition $(I,I+1,\ldots ,n)\pi$, where $(I,I+1,\ldots ,n)$ is the cycle $I\to I+1\to \cdots \to n\to I$, and permutation is from left to right. Finally, define $W':=W(\pi)$.

I am trying to follow the proof of the following from https://projecteuclid.org/download/pdf_1/euclid.lnms/1196283800, where $E^W(\cdot)=E(\cdot\vert W)$.

enter image description here

How is the first equation in the proof established? In particular, I don't see where the -2 and $1/n$ are coming from. I'm not sure how to compute the conditional expectation of $W'$.