# Compute the expected number of descents in a random permutations $\in$ $S_n$

Let $\sigma$ be a permutation of [n]. There is a descent at i, $1\leq i\leq n$, if $\sigma(i)>\sigma(i+1)$. Compute the expected number of descents in a random permutations $\in$ $S_n$

-
What are your thoughts? Can you say something about the relation between the expected number of descents and the expected number of ascents? What is the expected number of places where $\sigma$ changes ins some direction? – Henning Makholm Feb 4 '13 at 20:37
Linearity of expectation. Randomly choose a location, then compute the expectation. Then sum them up. – Kimmi Feb 4 '13 at 20:40
Sounds good. Which answer does that lead to? – Henning Makholm Feb 4 '13 at 20:43
Alternatively, you can pair up a permutation with another permutation so that the total 'descents' is a constant. – Thomas Andrews Feb 4 '13 at 20:43
Linearity of expectation works. Also works to say that there are $n-1$ places where $\sigma(i) \neq \sigma(i+1)$, and note that by symmetry you should expect equal numbers of ascents and descents. – mjqxxxx Feb 4 '13 at 21:08

There are $n-1$ places for comparison, either descents or ascents, and they are symmetric. So the expected number of descents in permutation is $\frac{n-1}{2}$

-

The correct answer is $\frac{n+1}{2}$.

Let $I_i$ be a random variable, indicating the i-th element in a permutation being the beginning of a descent.

$P(I_i)=\frac{1}{2}$, as any possible pair is either ascending or descending (for $i\ne 1$)

$P(I_i)=1$, as the first element is always a beginning.

$A=\sum_{i=1}^nI_i=1+\sum_{i=2}^nI_i$

$E(A)=1+\sum_{i=2}^n P(I_i) = \frac{n+1}{2}$

-