9
$\begingroup$

I stumbled upon this most interesting problem whose solution has so far escaped me and I think that it'd be very fascinating to see how it may be precisely dealt with.

It runs as follows,

If some series of $n$ terms is deranged, how can we first calculate the probability that no term shall stand next to a term it was next to originally, and further, if $n$ happens to be infinite, how can we prove that the probability is $e^{-2}$?

$\endgroup$
  • 1
    $\begingroup$ Can you define "deranged"? $\endgroup$ – Michael Lugo Jun 4 '17 at 22:25
  • 4
    $\begingroup$ A derangement is a permutation with no fixed points. $\endgroup$ – Thompson Jun 4 '17 at 23:57
  • 2
    $\begingroup$ Calculate the answers for $n=4,5,6$ and then look it up in the Encyclopedia of Integer Sequences. $\endgroup$ – Gerry Myerson Jun 5 '17 at 7:00
  • 1
    $\begingroup$ Here is an OEIS result for the 'no adjacent pair is again adjacent' rule only. A002464 $\endgroup$ – Sangchul Lee Jun 5 '17 at 14:15
  • $\begingroup$ It certainly looks to be a very hard task in rigorously proving the conditions of this problem. $\endgroup$ – Kalis Jun 5 '17 at 14:24
3
$\begingroup$

The limiting ratio is not hard to derive via the method of moments.

In a random permutation $\sigma$ of $\{1,2,\dots,n\}$ (not necessarily a derangement), let $X_n$ be

  • the total number of integers $i$, $1 \le i \le n$, such that $\sigma(i) = i$, plus
  • the total number of integers $i$, $1 \le i \le n-1$, such that $\sigma(i+1) = \sigma(i)+1$, plus
  • the total number of integers $i$, $1 \le i \le n-1$, such that $\sigma(i) = \sigma(i+1)+1$.

We'll show that for any fixed $k$, we have $\lim_{n \to \infty} \mathbb E[\binom{X_n}{k}] = \frac{3^k}{k!}.$ If a random variable $X$ is Poisson with mean $3$, we also have $\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$. The Poisson distribution is determined by its moments, so it follows that $X_n$ converges in distribution to $X$, and in particular $\lim_{n \to \infty} \Pr[X_n = 0] = e^{-3}$.

To see this, note that $X_n$ is the sum of $3n-2$ indicator variables corresponding to each of the events (listed above) that $X_n$ counts, so $\binom{X_n}{k}$ counts the number of size-$k$ sets of events that occur. The calculation is difficult to do exactly but more or less straightforward asymptotically. Out of the $\binom{3n-2}{k}$ choices of $k$ events, $(1-o(1))\binom{3n-2}{k}$ never involve the same value $\sigma(i)$ more than once, so the probability that they occur is $(1+o(1))n^{-k}$. These contribute $(1+o(1))\frac{3^k}{k!}$ to the expected value $\mathbb E[\binom{X}{k}]$, which is all that we wanted.

So it remains to reassure ourselves that the contribution from all other choices of $k$ events is insignificant in the limit. Muddying the picture, some groups of $j \le k$ events that overlap have a significantly higher probability than a group of $j$ nonoverlapping events. For example, the events that $\sigma(3)=3$, that $\sigma(4)=4$, and that $\sigma(4)=\sigma(3)+1$ have this property.

However, we can never win this way, because there are $O(n)$ ways to pick that a group of $j$ overlapping events (with a constant factor depending on $k$) but a $O(n^{-2})$ chance that all of the events occur (since at least two values of $\sigma$ are involved). So for any possible overlapping structure, the contribution to $\mathbb E[\binom{X}{k}]$ is $O(n^{-1})$, and there is a constant number (depending only on $k$) of overlapping structures.

As a result, we can ignore all overlaps, conclude that $\lim_{n\to\infty}\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$, and deduce that $\lim_{n\to\infty} \Pr[X_n = 0] = e^{-3}$. Therefore $$\lim_{n\to\infty} \Pr[X_n = 0 \mid \text{$\sigma$ is a derangement}] = \lim_{n\to\infty} \frac{\Pr[X_n=0]}{\Pr[\text{$\sigma$ is a derangement}]} = \frac{e^{-3}}{e^{-1}} = e^{-2}.$$

$\endgroup$
  • 2
    $\begingroup$ This may be fallacious, can someone with similar expertise confirm it? $\endgroup$ – Kalis Jun 5 '17 at 19:17
  • 2
    $\begingroup$ @Kalis is there a particular part of my argument that you don't believe? $\endgroup$ – Misha Lavrov Jun 5 '17 at 19:37
  • $\begingroup$ Although some details are left to readers, this is an excellent argument to the second part of OP's question. Glad to see this pretty argument. (+1) $\endgroup$ – Sangchul Lee Jun 6 '17 at 2:30

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.