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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Derangement is a permutation without fixed points, right? $\endgroup$
    – Fedor Petrov
    Commented Nov 1, 2016 at 6:17

1 Answer 1

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

Improve this answer
$\endgroup$
3
  • 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
    Commented Nov 1, 2016 at 15:01
  • $\begingroup$ It seems to be minimised for $n=5$ at a probability of $\frac{69}{242} \approx 0.285$. $\endgroup$
    – Henry
    Commented Nov 1, 2016 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
    Commented Nov 21, 2016 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .