Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is $${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be $$P(assignment~is~unsatisfiable) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.

Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is $${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be $$P(\mathit{assignment~is~unsatisfiable}) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.