I am trying to solve the following problem:
Let $\sigma: [n] \longrightarrow [n]$ be a random permutation in $S_n$, the set of all permutations, and let $d(\sigma)$ be the number of descents of $\sigma$ defined by the cardinality of the set $\{ i \in [n-1] \;| \;\sigma(i+1) < \sigma(i)\}$. Give a closed form expression for the variance of $d(\sigma)$.
My approach thus far: Let $X$ be the random variable denoting the number of descents, and let us express it as the sum of indiator random variables. That is, $X = X_1 + X_2 + … + X_{n-1}$. We have that
\begin{align*}
\mathbb{V}(X) &= \mathbb{E}(X^2) – \mathbb{E}(X)^2 \\
&= \mathbb{E}(XX) – \mathbb{E}(X)^2 \\
&= \sum_{i=1, j=1}^{n-1} \mathbb{E}(X_iX_j) – \left( \sum_{i=1}^{n-1}\mathbb{E} (X_i)\sum_{j=1}^{n-1} \mathbb{E}(X_j)\right) \\
&= \sum_{i=1, j=1}^{n-1} \mathbb{E}(X_i X_j) – \mathbb{E}(X_i)\mathbb{E}(X_j)
\end{align*}
It looks like we obtain a sum of covariances for muliple pairs of $X_i$'s. Nonetheless, this is where I got stuck because I am not sure how to proceed from here. It would be easier if the $X_i$'s were independent and identically distributed, but it is not the case. I would truly appreciate any help on computing this variance!
Best Answer
For each $i\in[n-1]$ let $X_i=1 \iff \sigma(i+1)>\sigma(i)$ and $X_i=0$ otherwise. Put $$X=X_1 + \dots + X_{n-1}$$ As you said, $X$ counts the number of descents in your random permutation. We need to compute $V(X)$ which we'll express as $$V(X)=\sum_{k=1}^{n-1}V(X_k)+2\sum_{i<j}\text{cov}(X_i,X_j)$$ Notice $V(X_1)=V(X_i)$ and $\text{cov}(X_1,X_2)=\text{cov}(X_i,X_{i+1})$. Moreover $\text{cov}(X_1,X_3)=\text{cov}(X_i,X_j)$ for $i,j\in[n-1]$ such that $j-i>1$. Since there are $n-1$ terms in the first sum and $n-2$ out of ${n-1 \choose 2}$ terms of the form $\text{cov}(X_i,X_{i+1})$ in the second sum, we can further simply $V(X)$ into the following expression: $$V(X)=(n-1)V(X_1)+2(n-2)\text{cov}(X_1,X_2)+(n-2)(n-3)\text{cov}(X_1,X_3)$$ With a little counting we see that $$P(X_1=1)=\frac{{n \choose 2}(n-2)!}{n!}=\frac{1}{2} \\ P(X_1=1,X_2=1)=\frac{{n \choose 3}(n-3)!}{n!}=\frac{1}{6} \\ P(X_1=1,X_3=1)=\frac{{n \choose 2}{n-2 \choose 2}(n-4)!}{n!}=\frac{1}{4}$$ Using these values we obtain $V(X_1)=\frac{1}{4},\text{cov}(X_1,X_2)=-\frac{1}{12},$ and $\text{cov}(X_1,X_3)=0$. Putting everything together, we finally get $V(X)=\frac{n+1}{12}$.