Expected value of maximal displacement in permutations of $\{1,\ldots,n\}$

Question

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all permutations (bijections) $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. For any $\pi\in S_n$ we let the maximal displacement be defined by $$\text{maxd}(\pi)= \max\big\{|k - \pi(k)|: k\in \{1,\ldots,n\}\big\}.$$ The expected value of the maximal displacements of all $\pi\in S_n$ is $$E^{\max}_n = \frac{1}{n!}\sum_{\pi\in S_n} \text{maxd}(\pi).$$

What is the value of $\lim_{n\to\infty} \frac{E^{\max}_n}{n}$?

(Note. The answer to this question seems to imply that $\lim_{n\to\infty} E^{\min}_n = 0$ if we define $E^{\min}_n$ in an analogous manner to $E^{\max}_n$ above, but I'm not sure this holds.)

Answer 1

Fleshing out Boris Bukh's idea.

We can draw $\pi$ by first sending $1$ uniformly to somewhere in $\{1,\dots,n\}$, then sending $2$ uniformly to the remaining $n-1$ spots, and so on.

Consider a small but superconstant $m$, in particular $m = n^{2/3}$ works. The idea is that one of the first $m$ elements almost certainly goes to one of the last $m$ slots, which means that $\pi$ almost certainly has distance approximately $n-m = n(1-o(1))$.

For each $i=1,\dots,m$, consider its chance of staying in the first $n-m$ slots conditioned on this also happening for previous elements. There are exactly $n-m-i-1$ such slots available after placing the first $i-1$ elements, so \begin{align} \Pr[\pi(i) \leq n - m \mid (\forall j<i) ~ \pi(j) \leq n-m] &= \frac{n-m-i-1}{n} \\ &\leq \frac{n-m}{n} \\ &= 1 - \frac{m}{n} . \end{align} So \begin{align} \Pr[ \text{maxd}(\pi) \leq n - m ] &\leq \Pr[ (\forall i \leq m) ~ \pi(i) \leq n - m] \\ &\leq \left(1 - \frac{m}{n}\right)^m \\ &\leq e^{-m^2/n} \\ &\leq e^{-n^{1/3}}. \end{align}

Since $\text{maxd}(\pi) \geq n-m$ with probability at least $1-e^{-n^{1/3}}$, we have

$$ E^{\max}_n \geq (n-m)(1 - e^{-2n^{1/3}}) = n\left(1 - \frac{1}{n^{1/3}}\right) \left(1 - \frac{1}{e^{n^{1/3}}}\right) . $$

So $\lim_{n\to\infty} \frac{E^{\max}_n}{n} = 1$.