# Expected value question regarding bijections of $\{1,2,\ldots,n\}$

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

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$.