Expected value of maximal distance between neighbors in permutations

Question

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?

Answer 1

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$.