Skip to main content
1 of 3

Minimal neighbor distance 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 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$.

Is there $r\in \mathbb{R}$ such that $E_n \leq r$ for all $n>1$? If so, the smallest possible value for $r$ would be interesting (but is not needed for acceptance of answer.)