# How can I generate random permutations of [n] with k cycles, where k is much larger than log n?

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 Sn 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 n1/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(n1/2-ε) cycles or Ω(n1/2+ε) cycles and shows that their cycle lengths are "Poisson distributed", but right around n1/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.

-

Youll find the answer on page 38 of my lecture notes East Side, West Side, which are a free download from my web site. It's a complete, short Maple program. The problem was originally solved in 1978 in Combinatorial Algorithms, by Albert Nijenhuis and myself.

Herb Wilf

-
Thanks for the pointer. The permutation version of the problem is on page 33, not 38. –  Michael Lugo Apr 19 '10 at 21:29

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

-
The algorithm you give in Section 6.5 looks like exactly what I need. –  Michael Lugo Oct 31 '09 at 12:15

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.

-
Thanks! At the very least this will give me something to play around with and generate conjectures. And this chain has the nice property that if all I care about is the cycle type of the result (which is true for the original purpose I want this for), all I need to do is keep track of the cycle type. Of course the mixing time is different for the Markov chain on cycle types (i. e. partitions of n) than the Markov chain on permutations themselves. –  Michael Lugo Oct 30 '09 at 0:48
If it mixes much faster for cycle types than for cycles, one idea would be to use this to generate a random cycle type with the correct probability and then fill in the elements in a random order (much easier) to get a random permutation with that cycle type. –  David Eppstein Dec 8 '09 at 21:53

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.

-

One can sample from the uniform distribution on permutations on $n$ elements with $k$ cycles in expected time $O(n\sqrt{k})$.

For large $n$ and $k$ this may be more feasible than the method Herb Wilf refers to in his answer, which, if I understand right, requires the generation of the Stirling cycle numbers $S(m,r)$ for $m\leq n$ and $r\leq k$.

The idea is as follows: consider a Poisson-Dirichlet($\theta$) partition of $[n]$. The blocks of such a partition have the distribution of the cycles of a random permutation of $[n]$ from the distribution which gives weight proportional to $\theta^r$ to any permutation with $r$ cycles. In particular, conditioned on the number of cycles, the permutation is uniformly distributed. (Once one has a partition into blocks corresponding to the cycles, one can just fill in the elements of $[n]$ into the positions in the cycles uniformly at random).

Choose $\theta$ in such a way that the mean number of cycles is around $k$. One can sample a PD($\theta$) partition of $[n]$ in time $O(n)$ (see below). Keep generating independent samples of the partition until you get one with exactly $k$ blocks. The variance of the number of cycles will be $O(k)$ (see below) and the probability that the number of cycles is precisely $k$ will be on the order of $1/\sqrt{k}$, so one will need to generate $O(\sqrt{k})$ such samples before happening upon one with precisely $m$ cycles.

So this is really not so far from what you suggested in the question (generate random permutations until you find one that fits) with the twist that instead of generating from the uniform distribution (which corresponds to PD(1)) you choose a better value of $\theta$ and generate from PD($\theta$).

Here are two nice ways to sample a PD($\theta$) partition of $[n]$:

(1) "Chinese restaurant process" of Dubins and Pitman. We add elements to the partition one by one. Element 1 starts in a block on its own. Thereafter, when we add element $r+1$, suppose there are currently $m$ blocks whose sizes are $n_1, n_2, ... n_m$. Add element $r+1$ to block $i$ with probability $n_i/(r+\theta)$, for $1\leq i\leq m$, and put element $r+1$ into a new block on its own with probability $\theta/(r+\theta)$.

(2) "Feller representation". Generate independent Bernoulli random variables $B_1, \dots, B_n$ with $P(B_i=1)=\theta/(i-1+\theta)$. Write a string of length $n$ divided up into blocks, with the rule that we start a new block before position $i$ whenever $B_i=1$. So for example if $n=10$ with $B_1=B_5=B_6=B_9=1$ and the other $B_i$ equal to 0, then the pattern is

(a b c d)(e)(f g h)(i j).

(Note that always $B_1=1$). Then assign the elements of $[n]$ to the positions in the blocks uniformly at random.

The expected number of blocks is $\sum_{i=1}^n \mathbb{E}B_i$, which is $\sum_{i=1}^n \theta/(i+\theta)$, which is approximately $\theta(\log n-\log \theta)$. If this is equal to $k$ with $1 << k << n$, then the number of blocks will be approximately normal with mean $k$ and variance $O(k)$.

For details of some of the things mentioned here to do with Poisson-Dirichlet partitions, random permutations etc, see e.g. Pitman's lecture notes from Saint-Flour: http://bibserver.berkeley.edu/csp/april05/bookcsp.pdf

-

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.

-
Consider the case where I want permutations of [4] with 2 cycles. There are eleven of these: three that are conjugate to (12)(34) and eight that are conjugate to (123)(4). I want to generate each one of these with the same probability, 1/11. The fact that 11 is prime shows that this won't work -- the probabilities that come from this model are going to be sums of products of fractions with 2, 3, or 4 in the denominator. (Actually finding those probabilities is not that hard but won't fit in this box.) –  Michael Lugo Oct 30 '09 at 12:05

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

-
Sure, but the cases I'm interested in are precisely those where there are too many cycle types for that to be practical. –  Michael Lugo Oct 30 '09 at 14:22

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.

-

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

-