For any positive integer $n\in\mathbb{N}$ let $S\_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S\_n$ define the *neighboring number* $N\_n(\pi)$ as the minimum distance of $\pi$-neighbors, or more formally: $$N\_n(\pi) = \min \big(\big\{|\pi(k)-\pi(k+1)|:k\in\{1,\ldots,n-1\}\big\}\cup \big\{|\pi(1) - \pi(n)|\big\}\big).$$


For $n>1$ let $E\_n$ be the expected value of the neighboring number of a member of $S\_n$.


**Question.** Do we have $\lim\sup\_{n\to\infty}\frac{E\_n}{n} > 0$?



Neighboring number of a permutation
$\newcommand{\e}{\varepsilon}$
For any fixed $\e>0$, permutations with $N\_n(\pi)>\e n$ asymptotically have density zero. Indeed, consider values $\pi(1),\dots,\pi(k)$. There are $n$ choices for $\pi(1)$. For $\pi(2)$, we have at most $(1-\e)n$ choices, since it has to be at distance at least $\e n$ from $\pi(1)$. Similarly, for $\pi(3),\dots,\pi(k)$ we have at most $(1-\e)n$ choices. For remaining $\pi(j),j>k$ we just take the estimate $n-j+1$. It follows the ratio of permutations satisfying $N\_n(\pi)>\e n$ is at most
$$\frac{(1-\e)^{k-1}n^k}{n(n-1)\dots(n-k+1)}=\frac{(1-\e)^{k-1}}{(1-1/n)(1-2/n)\dots(1-k/n)}<\frac{(1-\e)^{k-1}}{(1-k/n)^k}.$$
Taking $k=\e n/2$ this bound goes to zero exponentially.


Since for large enough $n$ all but $\e n!$ permutations have $N\_n(\pi)<\e n$ and remaining ones have $N\_n(\pi)<n$, it follows $E\_n\leq 2\e n$, so $E\_n/n\to 0$. 


