An analysis of a simple algorithm for random derangements

We consider the uniform generation of random derangements, i.e., permutations without any fixed point. By using a rejection algorithm, we improve the straight-forward method of generating a random permutation until a derangement is obtained. This and our procedure are both linear with respect to the number of calls to the random generator, but we obtain an improvement of more than 36%. By using probability generating functions we perform an exact average analysis of the algorithm, showing that our approach is rather general and can be used to analyze random generation procedures based on the same rejection technique. Moreover, emphasis is given to combinatorial sums and a new interpretation of a known infinite lower triangular array is found.