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}$?
1
-
$\begingroup$ I would imagine that a Markov chain with rapid mixing might be useful here, though it would give only approximately uniform distribution. $\endgroup$– DmitryZSep 12, 2013 at 21:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Sep 13, 2013 at 18:29
-
$\begingroup$ 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. $\endgroup$– AatGSep 25, 2013 at 20:32
$\begingroup$
$\endgroup$
3
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.
answered Sep 13, 2013 at 11:51
-
$\begingroup$ Thanks, but I want to sample set partitions, not integer partitions. $\endgroup$– AatGSep 13, 2013 at 17:57
-
$\begingroup$ 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. $\endgroup$ Sep 13, 2013 at 21:41
-
2$\begingroup$ @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$). $\endgroup$ Sep 14, 2013 at 0:31