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

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

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

Answer 2

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 3

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 4

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

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

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 7

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 8

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 9

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.