Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
Is there any formula for the probability of x to be in a cycle of length k in a random derangement over N elements? –  Nate May 13 '13 at 9:49
    
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. –  Johan Wästlund May 13 '13 at 10:59
    
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. –  Nate May 16 '13 at 7:14
    
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. –  Johan Wästlund May 16 '13 at 8:55
    
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}$. –  Nate May 16 '13 at 19:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.