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?


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.