Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
3  
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
1  
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

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.