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