How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

Question

Admittedly, homework.

For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this formula, for example $C_1=x_1\wedge \neg x_3\wedge x_4$

The tasks is to do this in a little bit more sophisticated way than to choose a random assignment, see if it satisfies the formula, repeat N times. More specifically the tasks tells us to:

• Uniformly at random choose a clause $C_i$ in $\phi$.
• Set the values of the variables in $C_i$ so that $C_i$ is satisfied.
• Set the values of the remaining variables randomly.
• In this way sample only satisfying assignments and sample all of them.

I fail to understand: ALL OF THEM? If I want to sample ALL satisfying assignments then I'm not sampling, but rather I'm counting?

Further the task asks:

• For a given assignment $p_i$ what is the probability of sampling $p_i$? That's an easy question: $\frac1{2^{n-m}}$ where $n$ is the number or distinct variables in $\phi$ and $m$ is the number of variables in $C_i$. Or am I wrong?
• How you can use the result of the previous question (the previous question was to sample trivially as I described above) to construct an estimate for the number of satisfying assignments? I don't know.

Well, I can check if this random assignment satisfies any other clauses than $C_i$. But how can I use the result?

My Googling yielded this page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ But this is even more confusing for me. Instead of choosing the clause $C_i$ uniformly, the site tells us to "pick up a clause $C_i$ with probability $P_i=\frac{\left|S_i\right|}{\sum_{j=1}{l}\left|S_j\right|}$, where $S_i$ is the collection of assignments satisfying $C_i$ and $l$ is the amount of clauses in $\phi$ and then pick up an assignment from $S_i$." But then we are told to "Check whether this assignment satisfies $\phi$. Finally, count the number of satisfying samples; denote the count by $M$". This is nonsense, each assignment that satisfies clause $C_i$ for any $i$ must necessary satisfy the whole formula?

Admittedly, this basic course on probability and statistics is the first course where I feel like a total idiot.

Any tips? I'm loosing hopes to be able to figure this out on my own.

Finally, I'm not sure, is this question more appropriate on scicomp.stackexchange.com?

Answer 1

Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is $$ p(\alpha) = \frac{2^{-n}}{m} \sum_{j\colon \alpha \text{ satisfies } C_j} 2^{|C_j|}. $$ Let $A$ be a random satisfying assignment chosen according to the algorithm, and let $X = 1/p(A)$. Then $$ E[X] = \sum_{\alpha \text{ satisfying}} \frac{\Pr[A=\alpha]}{p(\alpha)} = \sum_{\alpha \text{ satisfying}} = \text{# satisfying assignments}. $$