On the analysis of an algorithm to generate a random cyclic permutation

This item was put here on January 17, 2000. Sattolo has presented an algorithm to generate cyclic permutations at random. In this note the two parameters ``number of moves'' and ``distance'' are analyzed.

Added April 2002. Hosam Mahmoud has done some additional analysis and found in that way that the formula for the variance in Theorem 2 was wrong. I checked my computations, and expectation and second factorial moment was right, but the variance was indeed wrong. Very stupid; I don't know how it happened. Anyway, it has been corrected now.

This paper is available in the Tex, Dvi, and PostScript format.

(Back to List of Papers)