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 *maximal neighbor distance* be defined by $$\text{mnd}(\pi) = \max \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{mnd}(\pi)$ where $\pi$ ranges over $S\_n$.


Is $\lim\_{n\to\infty} \frac{E\_n}{n}$ defined, and if yes, what is its value?



Expected value of maximal distance between neighbors in permutations
It is 1. 


We will assume $n$ is large enough for this proof. Take all events $A\_{k,i,j}=\{\pi(k)=i,\pi(k+1)=j\}$ for $k\le n$, $i< n^{2/3}$, $j>n-n^{2/3}$. Clearly if any of these events occurs, then $E\_n>n-2n^{2/3}$. Thus we define the random variable
$$
B=\sum\_{k,i,j} 1\_{A\_{k,i,j}}
$$
and we want to show that $B>0$ with high probability. We can show this with the Chebyshev inequality.


First, by linearity of expectation
$$
\mathbb{E}(B)=\sum\_{k,i,j} \mathbb P(A\_{k,i,j})\ge (n-1)\cdot (n^{2/3}-1)\cdot (n^{2/3}-1)\frac{1}{n^2}= n^{1/3}(1-o(1))
$$


Then, we compute
$$
\mathbb{E}(B^2)= \mathbb{E}\left(\sum\_{k\_1,i\_1,j\_1}\sum\_{k\_2,i\_2,j\_2}\mathbb P(A\_{k\_1,i\_1,j\_1}\cap A\_{k\_2,i\_2,j\_2}) \right)
$$
The sum splits into three cases. In the first case, $k\_1=k\_2, i\_1=i\_2, j\_1=j\_2$. Then $P(A\_{k\_1,i\_1,j\_1}\cap A\_{k\_2,i\_2,j\_2})=P(A\_{k\_1,i\_1,j\_1})=\frac{1}{n^2}(1+o(1))$.


In the second case, at least one of these pairs are equal, but not all three are equal. Then $P(A\_{k\_1,i\_1,j\_1}\cap A\_{k\_2,i\_2,j\_2})=0$.


In the second case, none of the three pairs are equal. Then $P(A\_{k\_1,i\_1,j\_1}\cap A\_{k\_2,i\_2,j\_2})\le\frac{1}{n(n-1)(n-2)(n-3)}\le\frac{1}{n^4}(1+o(1))$. Thus
$$
\mathbb{E}(B^2)\le n\cdot n^{2/3}\cdot n^{2/3}\left(\frac{1}{n^2}\right)(1+o(1))+(n\cdot n^{2/3}\cdot n^{2/3})^2\left(\frac{1}{n^4}\right)(1+o(1))\le n^{2/3}(1+o(1))
$$
Thus
$$
\text{Var}(B)=\mathbb{E}(B^2)-(\mathbb{E}(B))^2=o(n^{2/3}).
$$
Then, by Chebyshev's inequality,
$$
\mathbb{P}(B=0)\le \frac{\text{Var}(B)}{(\mathbb{E}(B))^2}\to 0
$$
a $n\to\infty$. Thus, with probability going to $1$, $\text{mnd}(\pi)>n-n^{2/3}$, so $E\_n\to 1$.


