3
$\begingroup$

It is known that for a fixed x $\in \{0,1,...,N-1\}$, the length of the cycle of x in a random permutation in $S_N$ distributes uniformly in $\{1, . . . ,N\}$.

My question is regarding the length of x in a random derangement (permutation without any fixed point).

Does the length distributes uniformly in $\{2, . . . ,N\}$? If not - what is the distribution?

Any proof, proof sketch, reference or good explanation will be appreciated. I tried to google it, or to find relevant papers in google-scholar, but without success.

Thanks in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

The number of permutations where $x$ is in a cycle of length $k$ is $(N-1)!$. In order to have a derangement, $k$ must be at least 2 and the remaining $N-k$ elements must be "deranged". When $N-k$ is not too small, the fraction of derangements will be very close to $1/e$, so the cycle length in a derangement will be asymptotically uniformly distributed in the sense that if we divide by $N$, it converges in distribution to uniform on $[0,1]$. But for $k$ close to $N$, there will be irregularities, for instance the cycle length is never $N-1$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Is there any formula for the probability of x to be in a cycle of length k in a random derangement over N elements? $\endgroup$
    – Nate
    Commented May 13, 2013 at 9:49
  • $\begingroup$ The number $D_n$ of derangements of $n$ elements is $n!/e$ rounded up for even $n$, down for odd $n$. There are $(N-1)!/(N-k)!$ ways of choosing a cycle of length $k$ containing a prescribed element $x$, then $D_{N-k}$ ways of deranging the remaining elements. Divide by $D_N$ to get the probability. $\endgroup$
    – Johan Wästlund
    Commented May 13, 2013 at 10:59
  • $\begingroup$ From your answer I understand that the the probability for a cycle of length k is approximately: $(N-1)!/(N-k)! \cdot (N-k)!/e = (N-1)!/e$ (with additional division by $D_N$). But for $N>2$ there are only $N-2$ possible cycle lengths ($k \ne 1,N-1$), so the total sum of the probabilities is not $1$, because $(N-2)(N-1)!/e \ne D_N$. I might miss something. $\endgroup$
    – Nate
    Commented May 16, 2013 at 7:14
  • $\begingroup$ The probability of being in a cycle of length $k$ is $(N-1)!/(N-k)!\cdot D_{N-k}/D_N$ for $k=2,\dots, N$. For instance, when $N=5$ the probabilities for $k=2,3,4,5$ are $2/11, 3/11, 0, 6/11$, summing to 1. $\endgroup$
    – Johan Wästlund
    Commented May 16, 2013 at 8:55
  • $\begingroup$ OK. Thanks. My next challenge is to find the distance (exact or bounds) between this distribution to uniform distribution for values like $N=2^{16}$ or $N=2^{32}$. $\endgroup$
    – Nate
    Commented May 16, 2013 at 19:50

You must log in to answer this question.

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