snippetMinor
How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Viewed 0 times
estimateassignmentsmontehowsatisfyusingmanycarloformulagiven
Problem
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:
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:
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
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
Solution
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}.
$$
$$
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}.
$$
Context
StackExchange Computer Science Q#85461, answer score: 2
Revisions (0)
No revisions yet.