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

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
4
$\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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow that's amazing - I would never have thought that $(E_n)_{n\in\mathbb{N}}$ is bounded! $\endgroup$ Commented Jan 10, 2019 at 7:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.