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](https://mathoverflow.net/questions/275731/asymptotic-behaviour-of-fixed-points-in-permutations) 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.)



Expected value of maximal displacement in permutations of $\{1,\ldots,n\}$
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$.


