3
$\begingroup$

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

Question. Is there a positive real number $r$ such that $E_n \leq r$ for all $n>1$?

(Bonus question: What is the infimum of the values that $r$ can take?)

$\endgroup$
  • 3
    $\begingroup$ See oeis.org/A002493 for the number of permutations with minimal neighbor distance at least 2. Trackback findstat.org/St001344 $\endgroup$ – Martin Rubey Nov 9 '19 at 12:15
  • $\begingroup$ Thanks @MartinRubey! $\endgroup$ – Dominic van der Zypen Nov 9 '19 at 16:23
  • 1
    $\begingroup$ Possible duplicate of Neighboring number of a permutation $\endgroup$ – Sam Zbarsky Nov 12 '19 at 1:50
  • 1
    $\begingroup$ I don't think this is a duplicate. Sure, the setup is the same, but the final question is different. A positive answer to the question here would indeed give an answer to the other, older question, but not conversely. Also note that both questions were asked by the same person, too. $\endgroup$ – Max Horn Dec 12 '19 at 21:05
3
$\begingroup$

Here is a quick argument showing that $P(\mathbf{md}(\pi)>m)\le Ce^{-cm}$ though I'll not try to make the bounds sharp. Let us consider $n$ independent random variables $X_k$ uniformly distributed on $[0,1]$. The rearrangement $\pi$ will be determined from that model as $\pi(k)=\#\{i\in[n]:X_i\le X_k\}$. Clearly, we have all orderings of $X$ equally likely, so this, indeed, generates the uniform distribution on $S_n$.

Now take $\delta>0$. The event that there exists no $k\in[n-1]$ with $|X_k-X_{k+1}|\le\delta$ has probability at most $e^{-\delta(n-1)}$ (just go left to right and use the fact that every time you exclude an interval of length at least $\delta$). Now consider the event that $|X_k-X_{k+1}|\le\delta$ but $|\pi(k)-\pi(k+1)|>m$. It means that some $m$ of other $n-2$ variables $X_i$ managed to squeeze into the interval between $X_k$ and $X_{k+1}$. Now it is easy to estimate the probability of this event for fixed $k$ by $2\delta$ (the probability that $X_k$ and $X_{k+1}$ are $\delta$-close) times ${n-2\choose m}\delta^m\le\frac{(n-2)^me^m}{m^m}\delta^m$ (the union bound over the choices of $m$ other variables that want to squeeze in between). Taking the union bound over $k$, we get $$ P(\mathbf{md}(\pi)>m)\le e^{-(n-1)\delta}+(n-1)\delta \frac{(n-2)^me^m}{m^m}\delta^m. $$ Choosing $\delta=\frac{m}{2e(n-1)}$ finishes the story.

You can, probably, play this trick in a much more intelligent way and get the true asymptotics, but I leave the bonus question to someone else :-)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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