For any positive integer $n$, let $[n]:=\{1,\ldots,n\}$. Let $S\_n$ denote the set of permutations (bijections) $\pi:[n]\to [n]$. For any $n>1$ and $\pi\in S\_n$ we let the *minimal neighbor distance* be defined by $$\text{md}(\pi) = \min \big(\{
|\pi(k) - \pi(k+1)|: k\in [n-1]\}\cup \{|\pi(n)-\pi(1)|\}\big).$$
For $n>1$ denote by $E\_n$ the expected value of $\text{md}(\pi)$ where $\pi$ ranges over $S\_n$.


**Question.** Is there a positive real number $r$ such that $E\_n \leq r$ for all $n>1$? 


(Bonus question: What is the infimum of the values that $r$ can take?)



Minimal neighbor distance in permutations
Here is a quick argument showing that $P(\mathbf{md}(\pi)>m)\le Ce^{-cm}$ though I'll not try to make the bounds sharp. Let us consider $n$ independent random variables $X\_k$ uniformly distributed on $[0,1]$. The rearrangement $\pi$ will be determined from that model as $\pi(k)=\#\{i\in[n]:X\_i\le X\_k\}$. Clearly, we have all orderings of $X$ equally likely, so this, indeed, generates the uniform distribution on $S\_n$.


Now take $\delta>0$. The event that there exists no $k\in[n-1]$ with $|X\_k-X\_{k+1}|\le\delta$ has probability at most $e^{-\delta(n-1)}$ (just go left to right and use the fact that every time you exclude an interval of length at least $\delta$). Now consider the event that $|X\_k-X\_{k+1}|\le\delta$ but $|\pi(k)-\pi(k+1)|>m$. It means that some $m$ of other $n-2$ variables $X\_i$ managed to squeeze into the interval between $X\_k$ and $X\_{k+1}$. Now it is easy to estimate the probability of this event for fixed $k$ by $2\delta$ (the probability that $X\_k$ and $X\_{k+1}$ are $\delta$-close) times ${n-2\choose m}\delta^m\le\frac{(n-2)^me^m}{m^m}\delta^m$ (the union bound over the choices of $m$ other variables that want to squeeze in between). Taking the union bound over $k$, we get 
$$
P(\mathbf{md}(\pi)>m)\le e^{-(n-1)\delta}+(n-1)\delta \frac{(n-2)^me^m}{m^m}\delta^m.
$$
Choosing $\delta=\frac{m}{2e(n-1)}$ finishes the story.


You can, probably, play this trick in a much more intelligent way and get the true asymptotics, but I leave the bonus question to someone else :-)


