5
$\begingroup$

In this blogpost, the writer states "It’s easy to sample uniformly from the set of partitions of a set: you pick a number of bins using an appropriate exponential distribution, then randomly i.i.d. toss each element of the set into one of those bins." What i this "appropriate exponential distribution" that is mentioned?

I've written an algorithm which uniformly distributes elements of a set (of size $n$) into $n$ bins. Of course, this will generate all partitions of a set (given enough simulations), but it will not do so uniformly. In the blogpost, the writer suggests that choosing the number of bins using an exponential distribution would correct this problem. Is this the case, and if so, what is the distribution?

Thanks.

$\endgroup$
4
$\begingroup$

The "appropriate exponential distribution" for the number of bins $K$ is not exponential by any means. It actually is the discrete distribution of parameter $n$ given by

$$\Pr(K=k)\ \propto\ \frac{k^n}{k!}\tag{1.4}$$

for $k=1, 2, \ldots.$

Figure showing barplots for n=2, 10, 50

In the original paper, A. J. Stam argued as follows. When a partition $\pi$ consists of $|\pi|\ge 1$ nonempty subsets of $\{1,2,\ldots,n\},$ the conditional probability of realizing $\pi$ under this sample scheme after randomly choosing $K=k$ bins is

$$\Pr(\pi\mid K=k) = k^{(|\pi|)}k^{-n} = \frac{k(k-1)\cdots(k-|\pi|+1)}{k^n}.\tag{1.5}$$

(The equation numbering is Stam's, but I have slightly changed the notation of the variables.)

Let's justify this formula. The denominator counts the number of sequences of bin choices: each random toss can land in one of the $k$ bins and all $n$ tosses are independent. Thus each sequence of tosses has chance $k^{-n}.$ However, two sequences of tosses determine the same partition when the bins for one can be re-ordered to correspond to the bins of the other. If we order the bins so that the first partition occupies bins $1,2,\ldots, |\pi|,$ then the possible equivalent re-orderings are determined by putting bin $1$ at one of the $k$ positions, bin $2$ at one of the $k-1$ remaining positions, and so on, until we have repositioned bin $|\pi|.$ Thus, any partition $\pi$ of $|\pi|$ pieces created by tossing $n$ numbers into $k$ bins shows up multiple times as counted by the numerator of $(1.5).$

In conjunction with $(1.4),$ the unconditional probability may be found by summing over all possible values of $K.$ Evidently values $K=0, 1, \ldots, |\pi|-1$ cannot give $\pi,$ justifying the change in the summation index in the penultimate step:

$$\begin{aligned} \Pr(\pi) &= \sum_{k=0}^\infty\Pr(\pi\mid K=k)\Pr(K=k) \\ &\propto\sum_{k=0}^\infty\frac{k(k-1)\cdots(k-|\pi|+1)}{k^n}\,\frac{k^n}{k!}\\ &= \sum_{k=|\pi|}^\infty\frac{1}{(k-|\pi|)!} = \sum_{i=0}^\infty \frac{1}{i!} = e. \end{aligned}$$

Because this probability does not depend on $\pi,$ the distribution is uniform, QED.


As a consequence of this argument we recover Dobinski's formula for the number of partitions $T_n$ of $\{1,2,\ldots, n\},$ because it must be the normalizing constant of this distribution, whence (employing $(1.4)$)

$$T_n = \Pr(\pi)^{-1} = \left(\frac{e}{\sum_{k=1}^\infty \Pr(K=k)}\right)^{-1} = \frac{1}{e}\sum_{k=1} \frac{k^n}{k!}.\tag{1.1}$$

For ways to sample from discrete distributions like $(1.4),$ see our thread on this topic. The alias method is efficient.

$\endgroup$
  • $\begingroup$ Thanks very much, that clarifies a lot. So, am I understanding this right: when I generate a uniformly random partition of my set, I can sample from $(1,4)$ to obtain weights that I can use to decide on the number of bins that would give me what I want? I apologize if I've totally missed the mark, I'm not well-versed in all of this. $\endgroup$ – iaskdumbstuff Nov 24 '20 at 20:14
  • 1
    $\begingroup$ That sounds right. Just generate a value $k$ according to the probabilities given in $(1.4)$ and randomly toss all $n$ numbers into $k$ bins to create a partition. For each new partition repeat from the beginning by generating a new $k$ etc. In practice there are relatively few $k$ that will show up. For instance, with $n=10^6,$ only about $1000$ different values of $K$ have any realistic chance to appear (centered near $87,847$), even in long simulations. That makes this process fairly efficient. $\endgroup$ – whuber Nov 24 '20 at 21:58
  • $\begingroup$ @Ben I wish it were that easy :-). Look harder at the graphics: those are not Poisson distributions. (Their variances are far too small.) $\endgroup$ – whuber Nov 24 '20 at 22:01
  • 1
    $\begingroup$ Yes, you are mistaken in that you need to extend the distribution all the way out to $\infty:$ you can't just stop at $n.$ By including the higher values of $n,$ you will increase the chances of partitions into more pieces. $\endgroup$ – whuber Nov 25 '20 at 14:08
  • 1
    $\begingroup$ BTW, to make sure my advice is good I implemented this sampling procedure in R and tested it for values of $n=2,3,4,5,6,7,8,9.$ In each test I generated an average of 10 or more instances of each partition (and checked that every possible partition was generated at least once) and evaluated the $\chi^2$ statistic; they all passed repeatedly. $\endgroup$ – whuber Nov 25 '20 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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