Question

I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from S_n are both asymptotically log n, and the distribution is asymptotically normal.

I want to know what a typical permutation of [n] with k(n) cycles "looks like" (in terms of cycle structure), where k(n)/(log n) → ∞ as n → ∞. The special case I have in mind is permutations of [n] with n^1/2 cycles, since I've come across such permutations in another context, but I'm also curious about the more general problem. In order to do this I would like an algorithm that generates permutations of n with k cycles uniformly at random -- that is, it generates each one with probability 1/S(n,k) where S(n,k) is a Stirling number of the first kind -- so that I can experiment on them. (I'd be willing to settle for a Markov chain that converges to this distribution if it does so reasonably quickly.)

Unfortunately the only way I know to do this is to take a permutation of [n] uniformly at random (this is easy) and then throw it out if it doesn't have k cycles. If k is far from log(n) this is very inefficient, since those permutations are rare.

A few references I've come across that are related: This paper of Granville looks at permutations with o(n^1/2-ε) cycles or Ω(n^1/2+ε) cycles and shows that their cycle lengths are "Poisson distributed", but right around n^1/2 is a transitional zone. And this paper of Kazimirov studies "the asymptotic behavior of various statistics" under the distribution I've claimed, but I haven't read it yet because I can't read Russian and I'm waiting for the English translation. Finally, the algorithm I'm looking for might be in one of the fascicles of volume 4 of Knuth, but our library doesn't have them.

Answer 1

Various algorithms for the unbiased generation of random permutations of certain types (such as permutations into k cycles) are given in this thesis submitted just yesterday: http://www.jjj.de/pub/ Hope this helps, jj

Answer 2

One Markov chain that works: Pick uniformly two cycles A,B, and repartition their union uniformly into two new cycles. This is reversible, hence the uniform measure is stationary.

It would be interesting to know how fast this mixes.

Answer 3

Knowing next to nothing about randomness, this is how I'd go about picking a random permutation of [k] with exactly n cycles:

1) Pick n elements of k, removing each element from the pool you pick out of. 2) For the remaining elements, pick out an element at random, then pick an index i from [n] at random. Append the element to the cycle at i.

Alas, I don't really know how to analyze probabilities for this setup, nor to check what kind of distribution it gives.

Answer 4

I'm not sure this will help you, but you can compute the relative probabilities of the cycle types via Ewens's sampling formula (with θ=1).

Answer 5

Another Markov chain which converges to the uniform distribution is a variation on the "random to random" shuffling: pick a random element, take it out of the permutation and then stick it back in a random place, unless the random element you picked was a unicycle in which case you have to put it back as a unicycle to preserve the number of cycles.

This probably converges much more slowly than Omer's chain (at least for k << n), but it does have the advantage that, unless I'm mistaken, one can use path coupling to bound the mixing time by something like n^2 log n. If I had to guess I'd say the real mixing time is n log n. Luckily, I don't.

Perhaps path coupling could work for Omer's chain as well.

Answer 6

Look at the following paper: Moni Naor, Omer Reingold: Constructing Pseudo-Random Permutations with a Prescribed Structure. J. Cryptology 15(2): 97-102 (2002) You can find it on Moni's site.

Answer 7

Naor and Reingold's paper, mentioned in this answer, only explains how to construct a random permutation with a fixed prescribed structure from a given random permuation P.

This is done by taking the simplest possible permutation with the structure you wish to get, and conjugating it by P.

This reduces the problem to choosing a k-cycles cycle structure with the correct distribution, which does not seem to be easier to me.