# Expected value of maximal distance between neighbors in permutations

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?

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

• Thanks @SamZbarsky for taking the time and making the effort to write this up so beautifully! Nov 7, 2019 at 15:58