Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
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}$

share|cite|improve this answer

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.


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.