Neighboring number of a permutation

Question

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ as the minimum distance of $\pi$-neighbors, or more formally: $$N_n(\pi) = \min \big(\big\{|\pi(k)-\pi(k+1)|:k\in\{1,\ldots,n-1\}\big\}\cup \big\{|\pi(1) - \pi(n)|\big\}\big).$$

For $n>1$ let $E_n$ be the expected value of the neighboring number of a member of $S_n$.

Question. Do we have $\lim\sup_{n\to\infty}\frac{E_n}{n} > 0$?

Answer 1

$\newcommand{\e}{\varepsilon}$ For any fixed $\e>0$, permutations with $N_n(\pi)>\e n$ asymptotically have density zero. Indeed, consider values $\pi(1),\dots,\pi(k)$. There are $n$ choices for $\pi(1)$. For $\pi(2)$, we have at most $(1-\e)n$ choices, since it has to be at distance at least $\e n$ from $\pi(1)$. Similarly, for $\pi(3),\dots,\pi(k)$ we have at most $(1-\e)n$ choices. For remaining $\pi(j),j>k$ we just take the estimate $n-j+1$. It follows the ratio of permutations satisfying $N_n(\pi)>\e n$ is at most $$\frac{(1-\e)^{k-1}n^k}{n(n-1)\dots(n-k+1)}=\frac{(1-\e)^{k-1}}{(1-1/n)(1-2/n)\dots(1-k/n)}<\frac{(1-\e)^{k-1}}{(1-k/n)^k}.$$ Taking $k=\e n/2$ this bound goes to zero exponentially.

Since for large enough $n$ all but $\e n!$ permutations have $N_n(\pi)<\e n$ and remaining ones have $N_n(\pi)<n$, it follows $E_n\leq 2\e n$, so $E_n/n\to 0$.

Answer 2

Some quick simulation leads me to conjecture that $\lim_{n \to \infty} E_n$ exists and is around $1.15$.

The number of permutations in $S_n$ with $N_n(\pi) = 1$ is https://oeis.org/A129535. It appears again from numerical evidence that $\lim_{n \to \infty} P(N_n > 1) = e^{-2}$, where $N_n$ is chosen uniformly at random from $S_n$. This is consistent with heuristics. Namely, for $k = 1, 2, \ldots, n-1$, let $X_k = |\pi(k) - \pi(k+1)|$ be a random variable, where $\pi$ is a permutation on $[n]$ chosen uniformly at random. Then $P(X_k = 1) \approx 2/n$ and the $X_k$ are approximately independent, so $P(N_n > 1) = P(X_1 > 1, X_2 > 1, \ldots, X_{n-1} > 1) \approx (1-2/n)^{n-1} \approx e^{-2}$.

Furthermore $P(N_n > 2) = P(X_1 > 2, X_2> 2, \ldots, X_{n-2} > 2) \approx (1-4/n)^{n-1} \approx e^{-4}$ and similarly $P(N_n > k) \approx e^{-2k}$. So $E_n$ should be a geometric random variable with $p = 1 - e^{-2}$ and we should have $\lim_{n \to \infty} E_n = 1/(1-e^{-2}) \approx 1.1565$.