6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow that's amazing - I would never have thought that $(E_n)_{n\in\mathbb{N}}$ is bounded! $\endgroup$ – Dominic van der Zypen Jan 10 at 7:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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