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?