Article contents
Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
Published online by Cambridge University Press: 14 July 2016
Abstract
We investigate the limit distributions associated with cost measures in Sattolo's algorithm for generating random cyclic permutations. The number of moves made by an element turns out to be a mixture of 1 and 1 plus a geometric distribution with parameter ½, where the mixing probability is the limiting ratio of the rank of the element being moved to the size of the permutation. On the other hand, the raw distance traveled by an element to its final destination does not converge in distribution without norming. Linearly scaled, the distance converges to a mixture of a uniform and a shifted product of a pair of independent uniforms. The results are obtained via randomization as a transform, followed by derandomization as an inverse transform. The work extends analysis by Prodinger.
MSC classification
- Type
- Short Communications
- Information
- Copyright
- Copyright © Applied Probability Trust 2003
References
- 3
- Cited by