I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number of monotone increasing Boolean functions on $n$ bits), so I don't expect a method to be very efficient, but I'm interested in a nontrivial method: not generating all of them and sampling from them and not rejection sampling.

Antichains are sets of incomparable points in a poset. The approach that seems to make sense to me would be sampling antichains in the Boolean cube: every monotone increasing Boolean function $f$ is defined by its minimal incomparable $1$s, which we will call $\partial f$ in this thread, and every set of incomparable bitstrings correspond to a monotone increasing (and decreasing) Boolean function. I've attempted to sample these, but all of my methods are not uniform, biased towards unbalanced functions.

Any thoughts on this would be appreciated; I am not necessarily expecting a full solution to be found in this thread.


In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system model (Section 3.1). Then, they further illustrate how to map their spin system model to the problem of uniformly sampling from the order ideals of a poset which, in turn, is equivalent to sampling from the antichains of that poset (Section 3.2).

  1. Propp, James Gary, and David Bruce Wilson. "Exact sampling with coupled Markov chains and applications to statistical mechanics." Random Structures & Algorithms 9.1‐2 (1996): 223-252.
| cite | improve this answer | |

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.