Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?

share|improve this question
    
I would imagine that a Markov chain with rapid mixing might be useful here, though it would give only approximately uniform distribution. –  DmitryZ Sep 12 '13 at 21:24

2 Answers 2

up vote 6 down vote accepted

The sets you're interested in are counted by Stirling Numbers of the Second Kind, which satisfy the recursion $$\left\{{n \atop k}\right \}=\left\{{n-1 \atop k-1}\right \}+k \left\{{n-1 \atop k}\right \}$$ Here the first term represents those partitions where $n$ is its own set, and the remaining term represents inserting $n$ into a partition of $\{1, \dots, n-1\}$. This recursion can also be used to generate a set partition recursively:

With probability $\left\{{n-1 \atop k-1}\right \}/\left\{{n \atop k}\right \}$ put $n$ in its own set, and make the rest a partition of $n-1$ elements into $k-1$ sets chosen uniformly at random. Otherwise generate a uniform random partition of $n-1$ elements into $k$ sets, and insert $n$ into a set uniformly chosen from those sets.

The algorithm would run in time on the order of $nk$, with the main overhead being computing (or looking up) all of the Stirling Numbers up to $\left\{{n \atop k}\right \}$ at the start of the algorithm.

share|improve this answer
    
Thanks. This seems reasonable. –  Alex Gittens Sep 15 '13 at 3:31
    
Hmmm. Efficiency issues aside, this algorithm isn't practical for large n and k unless you're using a CAS that can compute the requisite Stirling numbers and then compute the quotient to reasonable accuracy. –  Alex Gittens Sep 25 '13 at 20:32

K.C. Locey, Random integer partitions with restricted numbers of parts

An algorithm is presented to generate uniform random samples of integer partitions for a total $Q$ with $N$ parts from the set of all $P(Q, N)$ partitions.

This algorithm was developed by Ken Locey in response to a 2010 question on StackOverflow.

share|improve this answer
    
Thanks, but I want to sample set partitions, not integer partitions. –  Alex Gittens Sep 13 '13 at 17:57
    
If $N=a_1+\dots + a_k$ is a random integer partition, and $x_1,x_2,\dots,x_N$ is a random permutation, then $\{ \{ x_1,\dots,x_{a_1}\}, \{x_{a_1+1},\dots,x_{a_1+a_2} \}, \dots \}$ is a random set partition. It isn't clear to me that it won't be uniformly random. –  Kevin O'Bryant Sep 13 '13 at 21:41
2  
@KevinO'Bryant it can't be uniformly random, because otherwise we would have $P(n)|B_n$ ($P(n)$ being the number of partitions and $B_n$ the Bell numbers, i.e. the number of set partitions), and it's easy to see this doesn't hold - in fact, it already breaks down for $n=3$ when there are $3$ partitions ($3$, $2+1$, $1+1+1$) and $5$ set partitions ($123$, $1|23$, $2|13$, $3|12$, $1|2|3$). –  Steven Stadnicki Sep 14 '13 at 0:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.