Consider random permutations of $1,2,\ldots,n$ and let $R=1,\ldots,n-1$ be the number of runs in the permuted sequence. For example, if $n=6$, the sequence $$ 6\quad2\quad4\quad5\quad3\quad1 $$ corresponds to the sequence $-,+,+,-,-$ and consist of three runs.

The expected value and the variance of the number of runs are given by $$ \operatorname ER=\frac{2n-1}3 \qquad\text{and}\qquad \operatorname{Var}R=\frac{16n-29}{90}. $$ How is the expression for the variance of $R$ derived?

There is a number of places on the Internet where these expression are given without a derivation (for example, here). The derivation of the expected value is given in this answer, but there is no derivation of the variance. It seems that we need to calculate the second moment of the sum of the indicators (defined as in this answer) but I am struggling to compute the expected value $\operatorname E[I_iI_j]$ with $i\ne j$. $I_i$ and $I_j$ do not seem to be independent so this complicates things but I might be missing something.

Any help is much appreciated!


1 Answer 1


Indicators whose positions don’t overlap are independent (since all $6$ permutations of three values being equiprobable is a local fact that doesn’t depend on which other values are taken at other positions), so we only have to consider a few local correlations.

For the variance, we can ignore the first and last indicators that have constant values $1$ and $0$, respectively. There are $n-2$ remaining indicators, and for each distance $k$ there are $n-2-k$ pairs at that distance.

At distance $k=0$, we have $\mathsf E[I_iI_i]=\mathsf E[I_i]=\frac23$.

At distance $k=1$, we have

$$\mathsf E[I_iI_{i+1}]=\mathsf P(y_{i-1}\lt y_i\gt y_{i+1}\lt y_{i+1})+\mathsf P(y_{i-1}\gt y_i\lt y_{i+1}\gt y_{i+1})=\frac5{12}\;.$$

(You can check that each of the two conditions is satisfied by $5$ out of the $24$ equiprobable permutations.)

At distance $k=2$, we have

\begin{eqnarray} \mathsf E[I_iI_{i+2}] &=&\mathsf P(y_{i-1}\lt y_i\gt y_{i+1}\lt y_{i+1}\gt y_{i+2})+\mathsf P(y_{i-1}\lt y_i\gt y_{i+1}\gt y_{i+1}\lt y_{i+2})+{}\\&&\mathsf P(y_{i-1}\gt y_i\lt y_{i+1}\lt y_{i+1}\gt y_{i+2})+\mathsf P(y_{i-1}\gt y_i\lt y_{i+1}\gt y_{i+1}\lt y_{i+2}) \\[4pt] &=&\frac{16+11+11+16}{5!} \\ &=&\frac9{20}\;. \end{eqnarray}

(Here I used a computer – not because it can’t be done by hand; it just seemed too error-prone.)

At distance $k\gt2$ we have

$$\mathsf E[I_iI_{i+k}]=\mathsf E[I_i]\mathsf E[I_{i+k}]=\frac49\;.$$

So adding it all up, we have

\begin{eqnarray} \mathsf E\left[\left(\sum_iI_i\right)^2\right] &=& \mathsf E\left[\sum_{ij}I_iI_j\right] \\ &=&(n-2)\cdot\frac23+2(n-3)\cdot\frac5{12}+2(n-4)\cdot\frac9{20}\\&&+\left((n-2)^2-(n-2)-2(n-3)-2(n-4)\right)\cdot\frac49 \\ &=& \frac49n^2-\frac85n+\frac{131}{90}\;, \end{eqnarray}

so the variance is

$$ \frac49n^2-\frac85n+\frac{131}{90}-\left(\frac{2(n-2)}3\right)^2=\frac{16n-29}{90}\;. $$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .