# Neighboring number of a permutation

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

$$\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), it follows $$E_n\leq 2\e n$$, so $$E_n/n\to 0$$.
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$$.
• Wow that's amazing - I would never have thought that $(E_n)_{n\in\mathbb{N}}$ is bounded! Jan 10, 2019 at 7:51