How many ranked items in a jumbled list outrank any later item?

Question

We may represent the items by the first $n$ positive integers. Let $\Sigma(n)$ be the set of $n!$ permutations on this set. For any $\sigma\in\Sigma(n)$, let$$m_\sigma:=\operatorname{card}\{k\in\{1,...,n\}:\sigma(k)>\sigma(k+j)\text{ for }j=1,...,n-k\};$$that is, $m_\sigma$ counts the entries in the $\sigma$-permuted list $(\sigma(1),...,\sigma(n))$ that exceed any later entry. Define$$\mu_n:=\sum_{\sigma\in\Sigma(n)}\frac{m_\sigma}{n!},$$namely the expected value of $m_\sigma$ over all $\sigma\in\Sigma(n)$. We seek the asymptotic limit for big $n$:$$\mu:=\lim_{n\to\infty}\mu_n.$$I calculated $\mu_1=1$, $\mu_2=\frac32$, $\mu_3=\frac{11}6$, $\mu_4=\frac{49}{24}$, and $\mu_5=\frac{271}{120}$ (in decreasing order of certainty as to accuracy) without spotting a general method. However, such a method may well exist—perhaps akin to that used to solve the well-known secretary problem (which can be searched for on this site or more generally).

Answer 1

I think an easier way to look at this problem is: let $p_{k, n}$, for $1 \leq k \leq n$, denote the probability that, in a randomly chosen permutation from $S_n$, the $k$th entry exceeds all later entries. Then, by linearity of expectation, $\mu_n = \sum_k p_{k,n}$. Can you find an expression for $p_{k,n}$?