15
$\begingroup$

What is the probability that composing two random derangements yields another derangement?

A slightly more specific question: suppose we start with a given derangement and compose it with all derangements. What is the distribution of cycle structures?

Addendum: perhaps it would be worth explaining why this question popped up in the first place. I am interested (purely out of curiosity) in the expected number of "steps" it takes to reach the identity permutation where each step is composition with a random derangement. See here for a related question (the only different is starting with a random permutation).

If you like to have "context": this is like asking how many steps it takes for $n$ penguins/koalas/beings with terrible memory to find their room, which they will recognize upon being inside, but which is otherwise indistinguishable. That's why I originally began with an arbitrary permutation, in any case.

$\endgroup$
  • 2
    $\begingroup$ Derangement is a permutation without fixed points, right? $\endgroup$ – Fedor Petrov Nov 1 '16 at 6:17
21
$\begingroup$

An array of $k$ permutations of $n$ letters such that each pair are derangements of each other is a $k\times n$ Latin rectangle. If $L(k,n)$ is the number of $k\times n$ Latin rectangles, then the probability you ask for is $n!\, L(3,n)/L(2,n)^2$. The value of $L(2,n)$ is $n!$ times the number of derangements. The value of $L(3,n)$ doesn't have closed form but there are recurrences and summations; see here for a survey. The asymptotic value of $L(k,n)$ is $e^{-\binom k2} (n!)^k$ for fixed $k$, from which you can see that the asymptotic value of the probability is $e^{-1}$.

I don't know the answer to your second question, though I rather suspect that the average cycle structure of the product of two random derangements is quite similar to the cycle structure of an unrestricted random permutation.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ It's interesting that the asymptotic probability is the same as the asymptotic probability a random permutation is a derangement. Composing two random derangements does not give a random permutation though - the identity has probability $1/D_n$ of appearing. $\endgroup$ – cats Nov 1 '16 at 15:01
  • $\begingroup$ It seems to be minimised for $n=5$ at a probability of $\frac{69}{242} \approx 0.285$. $\endgroup$ – Henry Nov 1 '16 at 15:23
  • $\begingroup$ "though I rather suspect that the average cycle structure of the product of two random derangements is quite similar to the cycle structure of an unrestricted random permutation." - this would, to some extent, be checkable by simulation. (If I feel so inclined later I may elaborate on this comment.) $\endgroup$ – Michael Lugo Nov 21 '16 at 21:34

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.