Context: this is just a problem I thought of for fun.

Let $\Sigma_n$ be the symmetric group on $\{1,2,\ldots n\}$. We define a random variable $X$ on $\Sigma_n$ by:

$$X(f)=\mbox{max}\{k\mid\forall j\leq k, f(j)\geq j\}.$$

In other words, $X(f)$ is the largest $k$ such that, in the graph of $f$, the points $(1,f(1))$, $(2,f(2))$, $\cdots$, $(k,f(k))$ all lie on or above the diagonal. My question is: What is $E[X]$? Is there even a "nice" way of finding or expressing it? If not, is there a way of estimating $E[X]$?


1 Answer 1


Sure, use the formula $$\mathbb E[X] = \sum_{k \ge 1} \Pr[X \ge k].$$ For a fixed $k$, $X \ge k$ if and only if $f(j) \ge j$ for all $j \le k$. There are $(n-k+1)^k \cdot (n-k)!$ permutations $f$ that satisfy this:

  • We can choose $f(k) \in \{k, k+1, k+2, \dots, n\}$ in $n-k+1$ ways.
  • Having done so, we can choose $f(k-1) \in \{k-1, k, k+1, \dots, n\} \setminus \{f(k)\}$ in $n-k+1$ ways.
  • Working backwards, we have $n-k+1$ choices for each of $f(k-2), f(k-3), \dots, f(1)$.
  • Finally, we don't care what $f(k+1), \dots, f(n)$ are, but there's $(n-k)!$ ways to arrange them at the end.

This gives us $$\mathbb E[X] = \sum_{k=1}^n \frac{(n-k+1)^k\,(n-k)!}{n!}$$ which does not appear to simplify well, but you can probably argue that it's $\mathcal O(\sqrt n)$ based on the fact that the $k^{\text{th}}$ term is approximately $1$ when $k \ll \sqrt n$ and very close to $0$ when $k \gg \sqrt n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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