<p>In [1], the paper where Propp &amp; 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). </p>

<ol>
<li>Propp, James Gary, and David Bruce Wilson. "<a href="http://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/propp_wilson.pdf" rel="noreferrer">Exact sampling with coupled Markov chains and applications to statistical mechanics.</a>" Random Structures &amp; Algorithms 9.1‐2 (1996): 223-252.</li>
</ol>

CC BY-SA 4.0
2019-05-21T23:18:07.400Z
2019-05-21T23:18:07.400Z
mhum
<p>I'm interested in sampling monotone increasing Boolean functions on <span class="math-container">$n$</span> input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers (<span class="math-container">$D_n = $</span> the number of monotone increasing Boolean functions on <span class="math-container">$n$</span> 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.</p>

<p>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 <span class="math-container">$f$</span> is defined by its minimal incomparable <span class="math-container">$1$</span>s, which we will call <span class="math-container">$\partial f$</span> 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.</p>

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

CC BY-SA 4.0
2023-12-10T05:40:10.303Z
I don't understand it well enough to summarize it in an answer, but Section 4.2 of [Minimizing the Average Query Complexity of Learning Monotone Boolean Functions by Torvik and Triantaphyllou (2002)](https://www.csc.lsu.edu/trianta/Journal_PAPERS1/INFORMS2002PaperonMonotoneBooleanFunctionsByTRIANTA1.pdf) addresses this problem.
Jeffrey Bosboom
<boolean-functions><sample-complexity><monotone>
Sampling monotone Boolean functions
Samuel Schlesinger
# Sampling monotone Boolean functions

(Asked by: username_0 on 2019-05-21)

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.

**Tags:** boolean-functions, sample-complexity, monotone

> **Comments:**
> **username_1**: I don't understand it well enough to summarize it in an answer, but Section 4.2 of [Minimizing the Average Query Complexity of Learning Monotone Boolean Functions by Torvik and Triantaphyllou (2002)](https://www.csc.lsu.edu/trianta/Journal_PAPERS1/INFORMS2002PaperonMonotoneBooleanFunctionsByTRIANTA1.pdf) addresses this problem.  

---

## 1 answers

### Answer by username_2 on 2019-05-21. Score: 12 | Accepted answer

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.](http://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/propp_wilson.pdf)" Random Structures & Algorithms 9.1‐2 (1996): 223-252.


---

