1
$\begingroup$

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all permutations (bijections) $\pi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. For any $\pi\in S_n$ we let the maximal displacement be defined by $$\text{maxd}(\pi)= \max\big\{|k - \pi(k)|: k\in \{1,\ldots,n\}\big\}.$$ The expected value of the maximal displacements of all $\pi\in S_n$ is $$E^{\max}_n = \frac{1}{n!}\sum_{\pi\in S_n} \text{maxd}(\pi).$$

What is the value of $\lim_{n\to\infty} \frac{E^{\max}_n}{n}$?

(Note. The answer to this question seems to imply that $\lim_{n\to\infty} E^{\min}_n = 0$ if we define $E^{\min}_n$ in an analogous manner to $E^{\max}_n$ above, but I'm not sure this holds.)

$\endgroup$
  • 6
    $\begingroup$ The limit is $1$ because for each of $1,2,...,m=O(1)$ there is a constant probability of being sent to $n-o(n)$ by $\pi$. $\endgroup$ – Boris Bukh Aug 25 '17 at 20:20
3
$\begingroup$

Fleshing out Boris Bukh's idea.

We can draw $\pi$ by first sending $1$ uniformly to somewhere in $\{1,\dots,n\}$, then sending $2$ uniformly to the remaining $n-1$ spots, and so on.

Consider a small but superconstant $m$, in particular $m = n^{2/3}$ works. The idea is that one of the first $m$ elements almost certainly goes to one of the last $m$ slots, which means that $\pi$ almost certainly has distance approximately $n-m = n(1-o(1))$.

For each $i=1,\dots,m$, consider its chance of staying in the first $n-m$ slots conditioned on this also happening for previous elements. There are exactly $n-m-i-1$ such slots available after placing the first $i-1$ elements, so \begin{align} \Pr[\pi(i) \leq n - m \mid (\forall j<i) ~ \pi(j) \leq n-m] &= \frac{n-m-i-1}{n} \\ &\leq \frac{n-m}{n} \\ &= 1 - \frac{m}{n} . \end{align} So \begin{align} \Pr[ \text{maxd}(\pi) \leq n - m ] &\leq \Pr[ (\forall i \leq m) ~ \pi(i) \leq n - m] \\ &\leq \left(1 - \frac{m}{n}\right)^m \\ &\leq e^{-m^2/n} \\ &\leq e^{-n^{1/3}}. \end{align}

Since $\text{maxd}(\pi) \geq n-m$ with probability at least $1-e^{-n^{1/3}}$, we have

$$ E^{\max}_n \geq (n-m)(1 - e^{-2n^{1/3}}) = n\left(1 - \frac{1}{n^{1/3}}\right) \left(1 - \frac{1}{e^{n^{1/3}}}\right) . $$

So $\lim_{n\to\infty} \frac{E^{\max}_n}{n} = 1$.

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